1
$\begingroup$

I'm currently working on a model that has a large number of variables (around 200k), and I don't know what the proper way to handle such a big problem is.

One suggestion I got is to use lazy constraints in order to limit the number of constraints, so that the model can be lighter, but I'm not sure I understand how they should be used.

Lazy constraints are constraints that get checked against a solution that satisfies all normal constraints, and in case they get violated, they get added as new constraints.

The problem with my model is that it can generate many solutions that have the same score, so I fear that a very large number of solutions would have to be tested against these lazy constraints, which they'd violate, resulting in many iterations of this process, and in each of these iterations many violations would be found (meaning that a very large number of constraints would be added anyway).

So, how do I use lazy constraints? Do I set as lazy only the constraints that rarely get violated, while keeping the others as normal? Or should I make a weak model, strenghtening it with lazy constraints?

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ Hi @Marco, welcome to or.stackexchange. Is your model a linear program, mixed integer linear program, a convex program, something entirely different? Also, you mention 200K variables, but how many constraints does your model have? $\endgroup$
    – Sune
    Commented Sep 25, 2023 at 19:52
  • $\begingroup$ Hi, the model is a MILP, and as for the number of constraints I'm not really sure (I don't know where I should look in the log of cbc for the exact number), but I'd guess it's something around 1M, the majority those are 'cuts' I added to try to speed up the model (such as disassembling bigger constraints) $\endgroup$
    – Marco
    Commented Sep 26, 2023 at 13:38
  • $\begingroup$ Hi @Marco. I am only asking for the number of constraints, as your model is also rather large in the "column dimension", i.e. it has many variables, so some sort of dynamic column generation might also be necessary - in stead of or in combination with row generation. $\endgroup$
    – Sune
    Commented Sep 28, 2023 at 11:11
  • $\begingroup$ I'll look into it, thank you! $\endgroup$
    – Marco
    Commented Sep 28, 2023 at 15:23

2 Answers 2

Reset to default
3
$\begingroup$

How lazy constraints are handled may depend on the solver, but CPLEX turns off dual reductions in the presence of lazy constraints, which could negatively impact performance. So I would probably limit my lazy constraint pool to constraints I believe are unlikely to be binding in the optimal solution, and then only if it made a meaningful reduction in the total number of constraints.

You mentioned your model having many solutions with the same score. If any of that is due to inherent symmetry in the model (basically, permutations of a feasible solution vector also being feasible with the same objective value), you might want to look at adding antisymmetry constraints (or invoking symmetry-breaking by the solver, if the solver provides it) to reduce the likelihood that the same objective value persists after activating bunches of lazy constraints. (It would also help with branch-and-bound performance in general, if you are solving a MIP.)

Improve this answer
$\endgroup$
0
$\begingroup$

Please see this link, it is for GUROBI https://support.gurobi.com/hc/en-us/articles/360013197972-How-do-I-implement-lazy-constraints-in-Gurobi-

Improve this answer
$\endgroup$

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.