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

Improve this question
$\endgroup$
4
  • 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, 2019 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, 2019 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, 2019 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, 2019 at 12:56

3 Answers 3

Reset to default
12
$\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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for sharing the note. Would you please, may the mentioned valid inequality in the paper, $ c \geq \sum_{b} x_{(b,k)}p_{(b)} \quad \forall k \in K$, be assumed as a cut? It is very similar to being a $\text{LB}$ on the objective function and treating as a cut-off option than actually being a valid cut that applies to the solution space. $\endgroup$
    – A.Omidi
    Feb 13 at 8:29
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ @Matteo Fischetti: I did not mention preprocessing in my answer...?!? Did I misunderstand your comment? $\endgroup$
    – Simon
    Aug 5, 2019 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, 2019 at 5:45
7
$\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.

Improve this answer
$\endgroup$

Your Answer

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

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