# Non 0-1 integer programming

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?

• Are the examples on the wikipedia page not something you can use? – Dennis Meng Dec 31 '13 at 15:55
• 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. – Zur Luria Dec 31 '13 at 15:59
• Ah wait, I thought I saw a different one in the list. Yeah, you're right. – Dennis Meng Dec 31 '13 at 16:14