Gomory–Johnson's facet conjecture for the infinite group problem

Let f(0,1)f\in(0,1) be fixed, and consider the infinite group problem with variables srZ+s_r\in\mathbb{Z}_+ for r[0,1)r\in[0,1), finite support, and the equality constraint

r[0,1)rsr=f,\sum_{r\in[0,1)}rs_r=f,

where additions are modulo 11. A nonnegative function π:[0,1)R\pi:[0,1)\to\mathbb{R} with π(0)=0\pi(0)=0 is valid when every feasible solution satisfies r[0,1)π(r)sr1\sum_{r\in[0,1)}\pi(r)s_r\geq1. A valid inequality is a facet if its equality solutions are not contained in those of any distinct valid inequality. A function is piecewise linear if it is affine on finitely many intervals of a finite partition of [0,1)[0,1). Facet conjecture. Every continuous facet for the infinite group problem is piecewise linear. The conjecture was disproved in the paper by exhibiting a continuous facet that is not piecewise linear.

Sources & referencesView supporting material

Primary source

Amitabh Basu, Michele Conforti, Gerard Cornuejols and Giacomo Zambelli, “A Counterexample to a Conjecture of Gomory and Johnson”, arXiv:1701.06621 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.