## Integer programming

Posted on: June 26th, 2013 by

3 objects A,B and C together cost 50 cents.
B costs more than 3 times as much as A, but no more than 4 times as much.
C costs more than 6 times as much as A, but no more than 3 times as much as B.
The costs are all integers.
What are the smallest and largest prices that B can take?

This is an example of integer programming. The general problem is in fact NP-complete.

Integer programming problems can be solved by a cutting plane method which involves iteratively executing
1) Solving the linear programming problem to find v*
2) If the solution is not an integer solution, add a new constraint so that all integer feasible points of the original problem satisfy the new constraint, but the solution v* does not satisfy the additional constraint. Go back to step 1.

This can potentially take forever to solve. However, in combination with some heuristics, one can obtain a reasonably fast algorithm to solve integer programs. Here is a link to the wikipedia article on cutting plane method.