Are linear variables tight when having an incumbent integer solution?
AnsweredHello all,
I am implementing a logic based Bender's decomposition. Since the master is difficult to solve, I use an Epsilon based approach, stoping to solve subproblems when a "good quality" solution is found. Now, I am wondering if the linear variables have optimal/tight values in such a case?!
To illustrate, think of a problem like:
min \(ax + by\)
s.t. \(x \in {0,1}\)
\(y \geq 0\)
\(y \geq dx\)
So if I find a solution that is feasible but not optimal, are the value of the y variables guaranteed to be tight, i.e., as small as possible, given the integer solution of the x variables?
Hope, someone can help. If the question is unclear, feel free to ask.
Cheers,
Nico

To clarify, are you asking the following: If Gurobi finds a feasible solution \( (\hat{x}, \hat{y}) \) to the above problem, is it guaranteed that \( \hat{y}_i = \max\{0, d \hat{x}_i\} \) for all \( i \)? I'm assuming \( d \) is a scalar and \( b \geq 0 \) (the latter must hold or the problem is unbounded).
If so, then no. This is only guaranteed at an optimal solution (assuming \( b > 0 \)). However, for this specific problem, you can trivially improve a feasible solution by setting \( \hat{y}_i := \max\{0, d \hat{x}_i\} \) for all \( i \). Additionally, although the \( y \) variables are not guaranteed to be tight against their constraints at a feasible solution found by Gurobi, I would be surprised if they weren't for this problem.

Ok , thank you. Yes, you understood the question correctly. Of course \(b \geq 0\) and yes \(d\) is a scalar.
For that trivial case, I could indeed use the max function. However, my problem is actually more complicated than this. I was just simplifying to explain the problem more easily. But when even this simple case is not guaranteed to be optimal, my actual case will not be either.
Overall your last sentence explains my observation as well: Mostly, the continuous variables seems to be tight/optimal. However, in some cases this is not true. For those cases, I was not sure if it is due to a bug in my code or due to the fact that the solution is not optimal and therefore my question.
But now it is clear. Thank you again.
Please sign in to leave a comment.
Comments
2 comments