The Cutting Plane Game

Title-CPGame

Important info

This is a beta release for the MIP Workshop 2019. There are still some small bugs in the game (see below). All feedback is greatly appreciated.

The cutting plane game is hosted HERE for now. I’m just learning how many of these things work 🙂

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, and at the end of each you can either continue to the next level or restart the level (the points you had won in the level will be deducted of course). The main reason for allowing this, for now, is that there are still some minor bugs; in some cases, a cut that should be computed will not be. I am still working on these issues.

If at any level you get the integer hull, your 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.

level1-cpgame

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.

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:

level2-cpgame
So you might want to use a circle cut before the split 😉

I hope you enjoy the game!