Are linear variables tight when having an incumbent integer solution?

Answered

Comments

2 comments

  • Eli Towle

    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.

    0
    Comment actions Permalink
  • Nico André Schmid

    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.

    0
    Comment actions Permalink

Please sign in to leave a comment.

Powered by Zendesk