19
$\begingroup$

In Laurence Wolsey's Integer Programming[1], he presents a well-known procedure for deriving valid inequalities (VI) suitable for integer and mixed integer linear problems (see Section 8.3, and also Ch 9).

In the application-oriented literature, I've often seen authors present a MILP formulation then follow it up with VIs they have derived and found to be helpful in the problem, usually accompanied with experimental results (robust or not) to show the utility of the VI. (For clarification, I'm referring to VIs authors suggest adding to the formulation, not user-generated cuts derived and/or added during the solution procedure. Modern solvers have many powerful tricks for both pre-processing and during the solution process, including powerful cutting plane approaches.)

Question: With the extensive pre-processing options available with commercial solvers like CPLEX or Gurobi, is this still worth doing? If yes, what are the best practices for testing and convincing oneself a VI (or set of VIs) is worth the trouble?

Clarification: Based on the comments, by "extensive options" I mean the powerful pre-processing options and the in-process bag-o-tricks used by solvers. Why mention pre-processing (as a commenter asks)? For one, because pre-processing options exist. Second, in the literature I've seen authors recommend a certain level based on empirical testing.


[1] Wolsey, Laurence A. 1998. Integer Programming. Wiley: New York. ISBN 0471283665.

$\endgroup$
  • 2
    $\begingroup$ Valid inequalities generally do help. That's why all good MIP solvers use them. Are you asking if it's worth it to add user-generated cuts? $\endgroup$ – Austin Buchanan Aug 5 at 16:11
  • 1
    $\begingroup$ @AustinBuchanan Latest edit should help clarify. Yes, VIs are useful during the solution procedure (we need cuts!). I'm specifically talking about the addition of VIs added to the formulation prior to passing to a solver. If this is still unclear, I'll be happy to edit. $\endgroup$ – SecretAgentMan Aug 5 at 16:15
  • 2
    $\begingroup$ Not clear why you mention preprocessing: maybe you mean that modern solvers already exploit a number of (powerful) cutting plane families (VIs), and you ask whether it makes sense to investigate new ones for specific problems. $\endgroup$ – Matteo Fischetti Aug 6 at 5:46
  • $\begingroup$ @MatteoFischetti Yes, solvers use a lot more tricks than preprocessing (I've updated the question). I think the question remains regardless of the solver preprocessing options or the in-process bag of tricks. If you'd like me to clarify, ping me. $\endgroup$ – SecretAgentMan Aug 6 at 12:56
11
$\begingroup$

It is, at least sometimes, still very useful. I have a short note (link) on a problem in quay crane scheduling in which adding a single - rather uninspired - family of valid inequalities greatly reduced solution times.

My understanding is that you make the most out of enumerated valid inequalities when the linear relaxation of the MIP is poor, as they can quickly improve the dual bound.

$\endgroup$
9
$\begingroup$

In my experience, it's rarely, but sometimes still, worth doing. There is no general answer however, as it's very model-specific (and sometimes even instance-specific). The only way to know for sure is to try both ways with the solver of your choice. Your results will also change over time, because newer versions of solvers generally implement better algorithms and use differently tuned heuristics.

$\endgroup$
  • $\begingroup$ @Matteo Fischetti: I did not mention preprocessing in my answer...?!? Did I misunderstand your comment? $\endgroup$ – Simon Aug 5 at 17:07
  • 1
    $\begingroup$ Sorry, that was was a comment to the original question, not to your answer: I removed it. $\endgroup$ – Matteo Fischetti Aug 6 at 5:45
5
$\begingroup$

I've seen rather encouraging results using symmetry-breaking constraints, but most valid inequalities were useless (no effect on solving time or, worse, degradation thereof…), both with CPLEX and Gurobi. You really have to test: sometimes, the solver already found better tricks; other times, there are things they are just not smart enough to seee.

$\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.