11
$\begingroup$

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.


Reference

[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.

$\endgroup$
0
2
$\begingroup$

There are two main reasons to add cuts. First, to tighten the relaxation, i.e., make the domain smaller whilst preserving the global solution. Second, to kick a known (or predicted) solution out of the problem. This is common in e.g. feasibility pumps, where we want to avoid cycling of solutions, or when we want to break symmetry. We can also generate cuts for conflict analysis but that's a bit more convoluted.

To answer your question directly, it depends on context. In general, the new variable fixing would result in the problem being infeasible in that node, which is usually what we want (e.g., this node can't produce a better value than our current one). However, this is only true if the cut is supposed to be globally valid. If the cut is only supposed to be valid in a specific neighbourhood, it should be removed instead, unless your node is in the same branch as the node used to generate the local cut.

$\endgroup$

Your Answer

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

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