Today I have found this problem that really intrigues me while studying for an optimization exam:
Show that the relaxation of the clique formulation for the simple circular interval packing problem does not always describe the integer hull.
Here the 'clique formulation' denotes the inequality formulation of the linear problem that requires all maximal cliques $S$ of nodes in a graph $G = (V,E)$ to fulfill the following:
$$x(E[S])$$
And 'simple circular interval packing problem' denotes the following probem: The intervals are a consecutive subset of the circumference of a circle, and for any angle there can be at most one selected interval covering that angle.
Now in an attempt to solve the problem I have tied to draw several examples of such graphs. My main idea is to construct a graph that does not contain a maximal clique of size larger than 2 but that still prohibits some combinations of intervals in a maximal solution as this property would then not be covered by the relaxation... But I have severe problems finding such an example if there even exists one.
Edit: I have an idea. How about I take just one interval $x_1$ that goes around the circle more than once covering for example an angle of $3\pi$. Then an optimal integral solution is the empty set but an optimal solution to the linear relaxation would be $\frac{2}{3} x_1$. Does that make any sense?
Thanks in advance for your help.