2
$\begingroup$

I'm solving a problem whose structure involves a large number of implied bound (redundant) constraints.

Consider the linear constraint (from T. Achterberg thesis, p.109) :

\begin{equation} x_1 + x_2 + x_3 + x_4 + x_5 - 5y \leq 0 \end{equation}

with binary variables $ x_j, y \in \{0, 1\}, \, j = 1, \dots, 5 $. The constraint encodes the implications $ y = 0 \Longrightarrow x_j = 0 $ for all $ j = 1, \dots, 5 $. However, the direct representation of these implications as a system of linear inequalities \begin{equation} x_j - y \leq 0 \quad \text{for all } j = 1, \dots, 5 \end{equation} yields a strictly stronger LP relaxation. For example, the fractional basic solution $ x_1 = \dots = x_4 = 1, x_5 = 0, y = 0.8 $ is feasible for the aggregated inequality but violates the system.

It further reads

The main disadvantage of the system is that it [...] usually slows down the LP solving. Therefore, the common approach is to initially use the aggregated inequality and let violated inequalities of the system be separated as implied bound cuts.

I have provided the implied bound cut in aggregated form and ran my B&C with different implied bound cut parameter values (Gurobi 11.0), then tested that against the model with the aggregated form, whilst also separating the disaggregated cuts when violated (as described above). The latter is significantly better.

Is this intended behavior? How can I make full use of what's implemented in solvers for my case?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

I regularly try both on models. Sometimes the aggregated form is faster, sometimes the disaggregated form is faster. Depends on the model, may depend on the size of the instance. The lesson to be learned is always experiment. Modelling is a black art. Sometimes it's very black. And when comparing make accurate comparisons by running across different random seeds to account for performance variability. How can I make accurate comparisons?

Improve this answer
$\endgroup$
3
  • $\begingroup$ I did some experimenting on a few test subsets to identify good combinations, which was insightful. Consistently, the best was as described in the thesis: having the aggregated eq. in the initial model and adding any disaggregated ones whenever violated. However, what I'm really interested in is understanding how we might leverage what's already built into solvers to effectively separate these cuts. For example, is there a specific format for writing an inequality to be recognized as an implied bound cut by the constraint handler? Thank you for your guidance! $\endgroup$
    – kgom
    Commented Nov 10 at 14:41
  • 1
    $\begingroup$ You could try adding these cuts using the Lazy attribute (gurobi.com/documentation/current/refman/lazy.html), rather than separating. And if you haven't tried it already then you see how adding the disaggregated form goes as constraints (and omitting the aggregated form). I'm not sure what you mean by your last question. If you submit a constraint in the aggregated form, Gurobi will recognise that it can create implied bound cuts - you don't have to do it yourself. How aggressively it applies them is controlled by the parameter you mentioned. $\endgroup$
    – Riley
    Commented Nov 10 at 22:25
  • $\begingroup$ That answers my question! Thank you $\endgroup$
    – kgom
    Commented Nov 11 at 7:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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