Heuristics (and/or checklists) to decide if the problem at hand is really a Linear Program.
Here's my attempt at answering, and I have also tried to outline how I'd approach this problem.
Questions that indicate that a given problem is suitable to be formulated as an LP/IP:
- Are there decisions that need to be taken regularly, at different time intervals?
- Are there a number of resources (workers, machines, vehicles) that need to be assigned tasks? (hours, jobs, destinations)
- Is this a routing problem, where different "points" have to be visited?
- Is this a location or a "layout" problem? (Whole class of Stock-cutting problems fall into this group)
Answering yes to these questions means that an LP formulation might work.
Commonly encountered LP's include: Resource allocation.: (Assignment, Transportation, Trans-shipment, knapsack) ,Portfolio Allocation, Job Scheduling, and network flow problems.
Here's a good list of LP Applications for anyone new to LPs or IPs.
That said, there are literally 1000s of different types of problems that can be formulated as LP/IP. The people I've worked with (researchers, colleagues) develop an intuition. They are good at recognizing that a problem is a certain type of an Integer Program, even if they don't remember the details, which they can then look up.
Why this question is tricky to answer:
There are many reasons why it is not always straightforward to know if an LP formulation will cut it.
- There is a lot of "art" (subjectivity) in the approach to modeling/formulation.
- Experience helps a lot. People get good at recognizing that this problem can be "likened" to another known formulation
- Even if a problem is not a straight LP, there are many clever master-slave techniques (sub-problems), or nesting techniques that make the overall formulation work.
- What looks like multiple objectives can be combined into one objective function, with an appropriate set of weights attached.
- Experienced modelers employ decomposition and constraint-relaxation techniques and later compensate for it.
How to Proceed to get the basic formulation done?
The following has always steered me in the right direction. I typically start by listing the Decision Variables, Constraints, and the Objective Function. I then usually iterate among these three to make sure that everything "fits."
So, if you have a problem at hand, ask yourself:
- What are the Decision Variables (DV)? I find that this is always a good place to start the process of formulation. How many types of DV's are there? (Which resource gets which task, and when should it start?)
- What are the Constraints?
Some constraints are very readily visible. Others take a little bit of teasing out. The constraints have to be written in terms of your decision variables, and any constants/limits that are imposed.
- What is the Objective Function?
What are the quantities that need to be maximized or minimized? Note: Sometimes, it is not clear what the objective function is. That is okay, because it could well be a constraint-satisfaction problem.
A couple of quick Sanity Checks once you think your LP formulation is done:
- I always try to see if a trivial solution (all 0s or all big
numbers) is not part of the solution set. If yes, then the
formulation is most probably not correct. Some constraint is
missing.
- Make sure that each and every constraint is "related"' to
the Decision Variables. (I occasionally find constraints that are
just "hanging out there." This means that a "bookkeeping constraint"
has been missed.)
In my experience, people who keep at it almost always develop the needed intuition. Hope this helps.
