In integer programming problem, we often want to relax the integer programming problem to linear programming problem. So we want to find the integer hull of the problem. The number of inequalities to define this integer hull is exponential in general, but are there some conditions in which the number of inequalities to define the integer hull is relative small, say, polynomial to the number of constraints? Are there any research about this?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
"Is there research on this". Well, a great share of the operation research consists in finding linear (or, now, semidefinite or other convex cone) relaxations of combinatorial problems, such that the linear relaxation matches or nearly matches the exact integer hull; so if it nearly matches, then one can perhaps prove some results such as "the optimum in the relaxation does not approximate the exact optimum by more than factor X".
An interesting approach is to lift the problem to a higher dimension. In general, the projection of a polyhedron to lower dimension may have many more constraints than the original, thus the converse (expressing a polyhedron as a projection of a higher dimension polyhedron) may be interesting so as to lower the number of constraints. This led to the family of methods known as "lift and project".
