15
$\begingroup$

Let us suppose we have an optimization problem which we have modeled as an ILP. Suppose we solve this problem using some set of constraints which restricts the search space. Let us suppose we model the same problem with the same objective function as an ILP but with some other set of constraints which produces a much larger search space. Which ILP could work faster, the one with the larger search space or the smaller search space? Is the same true for LP solvers?

$\endgroup$
  • 2
    $\begingroup$ I guess that by “search space” you mean “LP relaxation”, correct? Indeed, the search space (set of feasible solutions) does not depend on the formulation $\endgroup$ – Matteo Fischetti Aug 31 '19 at 13:24
11
$\begingroup$

When the solvers in question do not add cutting planes to further reduce the search space, the larger search space model typically produces feasible solutions more quickly, but its faster to prove optimality for the smaller search space model.

Given that all modern codes use cutting planes, its difficult to predict performance, as always.

| improve this answer | |
$\endgroup$
7
$\begingroup$

The geometry of a polyhedron obtained by relaxing the integer variables is proposed as a complexity measure for IPs. This idea is based on the concept of ill-conditioning, something like the intrinsic difficulty of the problem. For instance, if you compare a solution space which is a thin polyhedron with a few integer points on it, it is more difficult to solve than a fat polyhedron with many integer points.

About the size of the problem (number of variables (columns) and number of constraints (rows)), Van Roy and Wolsey1 mentioned that: "in contrast with LP, size is a poor indicator of difficulty. We believe that size is perhaps an even less reliable measure for mixed-integer programs than it is for pure integer programs."

For two-dimensional Knapsack problem, Hill, Raymond R., and Charles H. Reilly2, investigated the effect of various factors such as, the population correlation structure among coefficients, the level of constraint slackness, and the type of correlation, to evaluate the influence of these problem parameters on performance of branch-and-bound and heuristic solution procedures. Population correlation structure, and in particular the interconstraint component of the correlation structure, is found to be a significant factor influencing the performance of both the algorithm and the heuristic.

These are some of the research directions that I think will help you find your answer. But unfortunately, there is not an exact answer to this question AFAIK.

[1] Van Roy, Tony J., and Laurence A. Wolsey. "Solving mixed integer programming problems using automatic reformulation." Operations Research 35.1 (1987): 45-57.

[2] Hill, Raymond R., and Charles H. Reilly. "The effects of coefficient correlation structure in two-dimensional knapsack problems on solution procedure performance." Management Science 46.2 (2000): 302-317.

| improve this answer | |
$\endgroup$
6
$\begingroup$

With the exception of special cases and ill-posed problems, the answer is that no-one can really know until we start solving the problem. We know that this is related to the shape of the polyhedron, but performance is highly dependent on the exact formulation and the solvers' implementation.

ILP solvers use two main techniques to reduce the solution space:

  1. Integer cuts
  2. Constraint propagation

Both can reduce the solution space massively, to the point that a smaller feasible space might be much harder to solve than a larger one if the above techniques are not very effective for that problem.

The other side of the coin is the ILP heuristics. Because ILPs are solved using branch and bound (BnB). If the heuristics find the global solution very quickly BnB will usually be much faster. Unfortunately, this is largely a matter of luck (because heuristics are just that - heuristics).

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.