How do minimally violated k-mod cuts work (intuitive explanation)?

Question

As a background, I am not a specialist in theoretical computer science. But I have to take an exam with research-level optimization topics, and I have to learn it on my own, without lectures or tutors.

One of the subtopics I am required to learn in integer programming are maximally violated mod-k cuts. I was able to understand cutting plane methods in general, and how Chvatal-Gomory cuts work. The book I am using says that k-mod cuts are created by multiplying the system of constraining inequalities with some vector $\lambda$, then summing up all inequalities. I have difficulty picturing this and understanding why this leads to an interesting form of cut.

I tried making a numerical example for myself starting out with an easy system with 2 variables and 3 inequalities, but wasn't able to come up with any (apparently, finding them is NP-hard for the general case, I had hoped to come up with something obvious with a few tries for a very small example).

Could you please give me an explanation about the intuition behind these cuts? What do they look like, what makes them "maximally violated", how are they an improvement over other cuts?

---

The main text from which I have to learn is http://www.springer.com/de/book/9783642167287, and I also found exactly one paper on the topic, http://www.lancaster.ac.uk/staff/letchfoa/articles/mod_k.pdf. They are research-level sources, and I don't have enough background to build an intuitive understanding when reading the definitions.

Answer 1

Suppose you have an integer linear program, and it contains the following constraints:

x1 + x2 + x3 >= 1, x1 + x2 + x4 >= 1, x1 + x3 + x4 >= 1, x2 + x3 + x4 >= 1.

If we set x1, ..., x4 to 1/3, we satisfy all of the constraints, but we don't have integer values.

Now multiply each constraint by 1/3 and sum them together. You obtain:

x1 + x2 + x3 + x4 >= 4/3.

Since the variables are integer-constrained, we can round up the right-hand side to obtain:

x1 + x2 + x3 + x4 >= 2.

This "cuts off" the above-mentioned fractional solution, so it is called a "cutting plane".

Since we multiplied the constraints by 1/3, the given cutting plane is a "mod-3" cut. Moreover, the fractional solution violates the cutting plane by 2/3, which is best possible. So the mod-3 cut is "maximally violated".

More generally, to obtain a mod-k cut, you multiply each constraint by a multiple of 1/k, before summing and rounding. Such a cut is "maximally violated" by a given fractional solution if it is violated by (k-1)/k.