Resources to learn about modeling within the scope of Linear/Integer programming?

Question

I'm currently taking a course in OR, and I'm facing some major difficulties trying to formulate my LP/IP problems. I understand most of the topics just fine, but I just get lost trying to formulate problems on my own when we're given a case study. Can anyone recommend a good resource to learn how to model problems on my own? Basically stuff like knapsack, bin packing, transportation, assignment, set coverage, etc..

Thank you!

Answer 1

There are a number of books, including "Model Building in Mathematical Programming" by H. P. Williams and "Applications of Optimization with XpressMP" by Guéret et al., that provide lots of examples of LPs and integer programs for practical problems.

An approach I used to suggest to my students is the following.

• First, figure out what decisions need to be made. (It might help to ask yourself "what would I have to tell a hard-working but not very bright assistant to get things done?".) Each decision becomes a variable.
• Next, ask yourself what criterion you would use to decide the best solution (maximize profit, minimize cost, maximize cost if you are the government, ...) and turn that criterion into an expression involving the variables. That's your objective function. In doing this, you might discover you need some "auxiliary" variables, representing things that are not direct decisions but are consequence of decisions that show up in the objective function. For instance, in a production problem, you won't necessarily think of end-of-period inventory as a direct decision -- you decide what to make, and then inventory just happens -- but you may need to know what it is to account for it in a profit or cost function.
• Now ask yourself what limits your decisions, i.e., what stops you from doing anything you feel like doing. So production decisions may be limited by capacity and by required output (demand), staffing decisions may be limited by available staff and by requirements to fill certain positions, etc. Each of those needs to be expressed in terms of your variables, becoming constraints.
• Lastly, if you have any "auxiliary" variables, make sure that you include constraints that define them in terms of the decision variables. For instance, in a production problem where you decide how much stuff to make per period, inventory at the end of a period is starting inventory plus production volume minus shipments.