12
$\begingroup$

Are there competitions for integer programming like there are for SAT and MAXSAT?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ As a side remark, Such competitions would be difficult to have. There are very good commercial tools, and any competition that leaves them out would not reflect the state of the art. But these tools often have special (licensing) rules when publishing benchmarks made using them, which would make it very hard to have a competition with them. $\endgroup$
    – DCTLib
    Commented Jul 2, 2020 at 19:31
  • $\begingroup$ This may be a more relevant question for or.stackexchange.com $\endgroup$
    – csTheoryBeginner
    Commented Jul 8, 2020 at 3:41

4 Answers 4

Reset to default
5
$\begingroup$

There are competitions for constraint satisfaction solvers. Some problems there can be readily translated to IP solvers as well. See e.g., MiniZinc challenge which has taken place yearly since 2008 or the XCSP competition.

Improve this answer
$\endgroup$
6
$\begingroup$

There are no competitions targeting general integer programming or mixed integer programming, but there are (or were) benchmarks, such as the MIPLIB (linear) and the MINLPLIB (nonlinear).

There are competitions for subsets (PB, SAT, max-SAT) and for constraint programming, as you and other answers pointed out. You can find many competitions (DIMACS challenges, for example) with NP-hard problems that can be formulated as IP, too.

So, why are there no such competitions? My personal guess is that it comes down to:

  • Implementation complexity. A good integer programming solver is HUGE and COMPLEX. SAT competitions and the like are interesting because many (small) teams can compete and a few tricks could get you quite far. There are only a few IP solvers, and all of them are many years of work.
  • Too general. There are many many IP instances with different properties. It would be difficult to create a balanced benchmark set.
  • Mature field. The solvers are mostly commercial, and the companies have no interest in organizing or taking part in such competitions.
Improve this answer
$\endgroup$
3
$\begingroup$

There was a Pseudo-Boolean solver competition from 2005-2012, but (as far as I can tell) nothing since then. Integer Linear Programming is a subset of Pseudo-Boolean programming. See the 2012 competition page for results and links to other competition results.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Hmm, in practice, the ILP solving is quite different. Having a few 100 of constraints of the form 1.35205x + 2.345199y <= 0.114 for variables x and y between 0 and 2^32 would cause most Pseudo-Boolean solvers to give up, while for ILP solvers, this is not a big deal. So while in principle, Pseudo-Boolean solving may generalize ILP, the reduction is frequently not practical. $\endgroup$
    – DCTLib
    Commented Jul 2, 2020 at 19:30
  • 1
    $\begingroup$ And it's not a generalization. Pseudoboolean does not handle continuous or general integer variable, so its expressive power is much worse $\endgroup$
    – Ggouvine
    Commented Jul 2, 2020 at 19:40
2
$\begingroup$

It is not really a competition, but there is the well-known Mittelmann benchmark, which lists results for some of the best solvers (including commercial ones) for mixed-integer programming and related problem classes:

http://plato.asu.edu/bench.html

http://plato.asu.edu/ftp/milp.html

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.