Integer Program - LP relaxation for convex objective function
AnsweredIs there any way to bound for each decision variable the difference of the optimal solution of the integer program and the linear program relaxation solution, in case of convex functions?
-
-
Gurobi Staff
Hi Nick
Do you want to do the following?
- Assume \(x^{'}\) is a relaxation solution of \(x\)
- \(x^{*}\) is a optimal solution of \(x\)
- Then, \(x^{'} - d \leq x^{*} \leq x^{'} + d\)
If so, you can solve the problem as LP first, and the results can be used to add constraints to the model. Then you can solve it again as MIP.
Thanks,
Ryuta0 -
-
Hi Ryuta,
Thank you for answering. What i am trying to figure out is, if \(x^*\) is the optimal solution of an integer program with a convex objective function, does there exist a standard relation like the one you provided for the optimal solution of the relaxed problem? For example, let \(x^*\) be the optimal solution of the integer program, and \(x'\) the optimal solution of the relaxed problem. Is it correct that:
\(|x^*-x'| \le 1\).
Thank you,
Nikos
0 -
-
-
Hi Nick,
If I understand correctly, you don't want to use the information available from the LP solution to provide constraints for MIP, you want to know whether such a relationship equation between the LP and MIP solutions holds in general. Generally speaking, I don't think such a relational equation exists. For example, the equation you gave means that there is a MIP solution in the Rounding of the LP solution. There are counterexamples to this as follows:
\[\begin{align} \min -x -y \\ \text{s.t. } -47x +48 y &\leq0 \\ 47x -28 y &\leq 94 \\ x,y &\geq 0\end{align}\]where x and y are interger. The LP solution for this problem is (\(x^{'},y^{'}\))=(4.8,4.7) and the MIP solution is (\(x^{*},y^{*}\))=(3,2). A more specific example would make this difference even greater.
Thanks,
Ryuta0 -
-
-
I got more specific example:
\[\begin{align} \min -x -y \\ \text{s.t. } y &\leq 0.9 \\ y - ax &\geq 0 \\ x,y &\geq 0\end{align}\]
where x and y are interger. For this problem, the only integer solution is (\(x^{*},y^{*}\))=(0,0). For constant \(a\) greater than 0, the LP solution \(x\) can be infinitely large by making \(a\) closer to 0. In other words, in this case, the difference between the MIP and LP solutions for \(x\) cannot be bounded.Thus your relational equation does not seem to hold for the general problem.
0 -
-
Ok, let us consider that $x \in {0,1,\dots, W\}, the acceptable values for the integer variables ($W$ may be equal to $\infty$). The relaxation mechanism transforms the aforementioned set into a convex region, $ 0 \ le x \le W$. Under these assumptions, and in addition when trying to minimize a convex function, does a relationship like the one i mentioned in the previous comment exist?
0 -
-
-
My understanding is that my one previous comment is a counterexample. -x -y is a convex function, the range of integer values that x can take is \({0,1,\dots, \lfloor \frac{0.9}{a}}\rfloor\)(only x=0 satisfies the integer property of y), LP solution is \(x=\frac{0.9}{a}\).
Or maybe I'm misunderstanding something. Could you provide some more explanation and example?Thanks,
Ryuta0 -
Please sign in to leave a comment.
Comments
6 comments