The Cutting Plane Game
About
TL;DR: the cutting plane game was (slightly) updated and is hosted HERE.
This second version of the cutting plane game is a minor improvement from its previous version, which was released for the MIP Workshop 2019. Among other things, this new version contains a dedicated leaderboard for CO@Work 2020. Participants should use their provided code to register their scores in the dedicated leaderboard. All scores (regardless of having the CO@Work code or not) will be registered in a global leaderboard.
Other changes with respect to the previous version are:
- The option of restarting a level was removed. There is still a bug resulting in a cut not created when it should, but the current version does not discount any budget in this case.
- For this reason, a new clean leaderboard was created. Thanks to all that made it to the first leaderboard! You should confirm your skill now :)
- A new option of ending a level was added to the pause menu. Use in case the level is stuck for some reason, or if you just don't like some polytope.
- A new level was added, and an old annoying level was removed.
- Minor bug-fixes.
There are still some small bugs in the game, the most recurrent one being a cut not created when it should. Since the cut budget will not be decreased in this case, just try it again!
All feedback is greatly appreciated.
Instructions
The objective of the cutting plane game is simple: to get as close to the integer hull as possible.
In this version, there are 9 levels. If at any level you get the integer hull, your total score will double! This is hard (and maybe impossible) on many levels though. Whenever you decide to end the game, you can upload your score to the online leaderboard.
How do you get to the integer hull? Via cutting planes of course. There are 3 families of cuts: circle cuts, split cuts and Gomory cuts. In each level, you have a budget for each family, and you can continue cutting until your budget is zero or you have obtained the integer hull.
You can also zoom in/out using the mouse wheel or trackpad.
Cut details
Gomory cuts. When you select this cut family, the vertices of the polytope will be highlighted. If you click on one, and that vertex is not too close to being integer, a Gomory cut will be computed. The obvious question: which Gomory cut is computed? The most violated one from the tableau.
Circle cuts. When you select this family, you can click at any location on the screen and a circle of increasing radius will be created. The radius will increase until an integer point is hit by the circle. If any vertex of the polytope lies inside the circle, an intersection cut will be computed. The obvious question: is the cut computed with a conic relaxation? No, the actual convex hull of the polytope minus the circle is computed. In particular, two cuts from the same circle can be computed in some cases!
Split cuts. These cuts work the same way as the circle cuts (since they are also intersection cuts). Note that you can select either vertical or horizontal split, but the budget is shared for both. With these, it's easier to see two cuts obtained from one set!
Remark: for these last two families, it is very important where you click to create the circle or split. The lattice-free sets computed will not necessarily be maximal! In a situation like the following, for example, it might be hard to get a good split cut:
I hope you enjoy the game!