3
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Are the examples on the wikipedia page not something you can use? $\endgroup$ Commented Dec 31, 2013 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$ Commented Dec 31, 2013 at 15:59
  • $\begingroup$ Ah wait, I thought I saw a different one in the list. Yeah, you're right. $\endgroup$ Commented Dec 31, 2013 at 16:14

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.