Representations of Unbounded Optimizations as Integer Programs.

摘要

Any optimization problem in a finite structure can be represented as an integer or mixed-integer program in integral quantities. It is shown that when an optimization problem on an unbounded structure has such a representation, it is 'very close' to a linear programming problem, in the specific sense described in the following results. It is also shown that, if an optimization problem has such a representation, no more than (n + 2) equality constraints need be used, where n is the number of variables of the problem.