Many interesting combinatorial problems - graph coloring, maximal matching, set cover, and knapsack among others - can be reformulated as integer linear programs. One thing that all of these reformulations have in common is that they are so called 0-1 integer programs. That is, the variables in the program recieve values in $\{0,1\}$.

I'm preparing for a class I'm teaching on linear programming, and so I'd like to give a variety of interesting examples of integer programming.

My question is: Is there an interesing combinatorial problem that can be restated as an integer linear program where the values of the variables are not necessarily 0-1?

  • $\begingroup$ Are the examples on the wikipedia page not something you can use? $\endgroup$ – Dennis Meng Dec 31 '13 at 15:55
  • 1
    $\begingroup$ Do you mean the Wikipedia page on integer programming? The examples given there are set packing, traveling salesman, SAT and vertex cover - all of which are restated as 0-1 integer linear programs. $\endgroup$ – Zur Luria Dec 31 '13 at 15:59
  • $\begingroup$ Ah wait, I thought I saw a different one in the list. Yeah, you're right. $\endgroup$ – Dennis Meng Dec 31 '13 at 16:14

There are many formulations of, e.g., graph coloring problems (e.g. see here), some of which are integer linear programming formulations where general integer variables are used. You may want to show several approaches and compare/contrast them to give students deeper insight into the importance of formulation.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.