Are there competitions for integer programming like there are for SAT and MAXSAT?
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$– DCTLibJul 2, 2020 at 19:31
$\begingroup$ This may be a more relevant question for or.stackexchange.com $\endgroup$– csTheoryBeginnerJul 8, 2020 at 3:41
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.
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.
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.
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$– DCTLibJul 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$– GgouvineJul 2, 2020 at 19:40
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: