Y a-t-il des compétitions pour la programmation entière?

Question

Y a-t-il des compétitions pour une programmation entière comme s'il y a un sat et maxat ?

Answer 1

Il y a des compétitions pour des solveurs de satisfaction de contraintes.Certains problèmes peuvent également être facilement traduits sur les solveurs IP.Voir par exemple, Minizinc Challenge qui a eu lieu annuellement depuis 2008 ou le Concours XCSP .

Answer 2

Il n'y a pas de compétitions ciblant la programmation entière générale ou la programmation entière mixte, mais il y a (ou étaient) de points de repère, tels que le Miplib (linéaire) et le minlplib (non linéaire).

Il existe des concours pour sous-ensembles (PB, SAT, MAX-SAT) et pour la programmation de contraintes, comme vous et d'autres réponses indiquées. Vous pouvez trouver de nombreuses compétitions ( Dimacs défis , par exemple) avec des problèmes durs du NP qui peuvent être formulé comme adresse IP aussi.

Alors, pourquoi n'y a-t-il pas de telles compétitions? Ma supposition personnelle est que cela revient à:

• Complexité de la mise en œuvre. Un bon solveur de programmation entier est énorme et complexe. Les compétitions SAT et similaires sont intéressantes car de nombreuses petites équipes peuvent rivaliser et quelques astuces pourraient vous amener assez loin. Il n'y a que quelques solveurs IP, et tous sont de nombreuses années de travail.
• trop général. Il existe de nombreuses instances IP avec différentes propriétés. Il serait difficile de créer un ensemble de référence équilibré.
• champ mature. Les solveurs sont principalement commerciaux et les entreprises n'ont aucun intérêt à organiser ou à participer à de telles compétitions.

Answer 3

Il y avait une compétition de solveur pseudo-booléene de 2005-2012, mais (autant que je sache), rien depuis.La programmation linéaire entière est un sous-ensemble de programmation pseudo-booléenne.Voir le Page de compétition 2012 pour les résultats et les liens vers d'autres résultats de la concurrence.