I am trying to understand an algorithm in a paper by Crévits et al. (2012)1 (see algorithm 2, the cuts I'm referring to are from the reduced costs). It uses a series of successive cuts on a linear relaxation of a problem. But it also uses a variable fixation rule. I'm not sure whether to adjust or remove the cut (constraint) under certain circumstances where the fixation is contrary to the values that made the constraint in the first place.

For example say you have a new cut (constraint) as follows:

$$5.5x_1 + 2.3x_2 + 6.4x_3 + 7.3x_4 + 8.1x_5 + 4.9x_6 \le s - r$$

Where $s$ is the value of a previous relaxation and $r$ is the value of a previous incumbent (both calculated at the time the cut was made).

And there are also these constraints in the original ILP problem and the LP relaxation:

\begin{align}x_1 + x_2 + x_3&= 1\\x_4 + x_5 + x_6 &= 1\end{align}

Say later a fixation is found where $x_3=0$, but is contrary to what was used to calculate $s$ i.e. $x_3=1$ when calculating $s$. What then to do with the cut (constraint)?

I understand that if the fixation value is in accordance with the RHS then the column can be removed from the LHS and the value adjusted on the RHS, assuming the fixation is at $1$, otherwise the fixation is at $0$ and the column can just be removed with the RHS left unchanged.


[1] Crévits, I., Hanafi, S., Mansi, R., Wilbaut, C. (2012). Iterative semi-continuous relaxation heuristics for the multiple-choice multidimensional knapsack problem. Computers and Operations Research. 39(1):32-41.


Your Answer

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

Browse other questions tagged or ask your own question.