21
$\begingroup$

How can we measure the tightness of a linear programming relaxation for a mixed integer linear program without using the objective value? I would like to get a measure in terms of the feasible set and independent of the objective function. This is due to the reason that I believe the tightness based on objective value is not informative enough and any change to the objective function might dramatically change the tightness. I believe there should be a different measure that is not affected by the change in the objective function. I am interested in both theoretical and computational answers. This is more of like a question out of curiosity.

$\endgroup$
4
  • $\begingroup$ I edited your title a bit; feel free to "roll back" if it's not OK. $\endgroup$ Jun 18, 2019 at 2:33
  • 1
    $\begingroup$ can you give us a little more context? Is this of purely theoretical interest or is there a computational question behind this? $\endgroup$ Jun 18, 2019 at 22:34
  • $\begingroup$ Like Marco, I would be interested in additional background to the question. It sounds like you are not interested in tightness with respect to a particular objective. Is this because you are more interested in a feasible solution than an optimal one? $\endgroup$
    – Mark H
    Jun 19, 2019 at 0:40
  • 2
    $\begingroup$ This question got me thinking about why we are so interested in the quality of LP relaxations compared to the optimal integer solution. As we rely on b&b methods to get optimality, it might be suitable to somehow (I don't know..) find a minimum number of branching steps if one would branch by simple setting single integer variables to 0 and 1. Of course, an obvious bound will be the number of 1's in the integer optimal solution.. Related: given an optimal solution, how many relaxations of the variables would are allowed to let the LP solution be optimal or integral. $\endgroup$ Jun 20, 2019 at 10:12

5 Answers 5

11
$\begingroup$

If the integer feasible set is finite and the LP polyhedron is bounded (a polytope), you could compare the volumes of the integer hull and this polytope.

$\endgroup$
1
6
$\begingroup$

If (for small dimensions) it is feasible to enumerate the vertices of the polyhedron of the relaxation, as well as the actual feasible set, one could try to find a vertex with the highest distance to the feasible set.

I guess this is equivalent to finding the "worst" objective function and could probably be posed as a bilevel problem with LP subproblem.

$\endgroup$
1
  • 2
    $\begingroup$ If you are going to enumerate vertices, maybe the percentage that are fractional is a useful metric. $\endgroup$
    – RobPratt
    Jun 20, 2019 at 17:42
5
$\begingroup$

Let us say that we have two MILP formulations $A$ and $B$ on the same variables, each with the corresponding LP relaxations defining polyhedra $P_A$ and $P_B$, respectively. We say that $A$ is stronger than $B$ if every point of $P_A$ is also contained in $P_B$ whereas some points of $P_B$ are not contained in $P_A$.

For example, you may prove the first direction by showing that the constraints of $A$ imply the constraints of $B$ by Farkas lemma, and then prove the second direction by finding a point that is separated by some constraint of $A$ and not separated by any constraint of $B$.

In the case that the formulations are on different variables but we can find a mapping between how MILP solutions are represented in A and B, then we can still check if each solution in $P_A$ maps to a solution in $P_B$ and vice-versa.

$\endgroup$
5
$\begingroup$

Another way of looking at this is to construct randomized-rounding algorithms from both relaxations, and select the relaxation which yields a randomized rounding algorithm with the best approximation guarantee.

For instance, in max-cut we can construct an LP relaxation which provides a $0.5$ approximation ratio, or an SDP relaxation which provides a $0.878$ approximation ratio, so the SDP relaxation is a better option (provided you can solve it).

Admittedly, constructing randomized rounding methods might be more effort than its worth, but quite a bit of work has already been done in this area, so you can often get the relevant approximation ratios via a literature search.

N.b. randomized rounding algorithms are typically agnostic to the objective function used, so i'm going to claim that this counts as not using an objective function ;)

$\endgroup$
1
$\begingroup$

Assuming you have two closed polytopes, we can compare the volumes of the two polytopes as Rob Pratt mentioned. Unfortunately this is NP-hard as we need to identify all the vertices.

A more tractable (heuristic) metric would be to measure the distance between every constraint and its relaxation (e.g. at the midpoints or some arbitrary vertex) and get a point-system based measure of tightness. This is of course a heuristic, but it can give you some measure of what's happening and how your overall tightness improves over time. This is much more tractable than calculating the volumes as it has linear complexity with respect to the number of your constraints.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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