Statistical mechanical analysis of linear programming relaxation for combinatorial optimization problems

Typical behavior of the linear programming (LP) problem is studied as a relaxation of the minimum vertex cover (min-VC), a type of integer programming (IP) problem. A lattice-gas model on the Erdös-Rényi random graphs of $\alpha$-uniform hyperedges is proposed to express both the LP and IP problems of the min-VC in the common statistical mechanical model with a one-parameter family. Statistical mechanical analyses reveal for $\alpha =2$ that the LP optimal solution is typically equal to that given by the IP below the critical average degree $c=e$ in the thermodynamic limit. The critical threshold for good accuracy of the relaxation extends the mathematical result $c=1$ and coincides with the replica symmetry-breaking threshold of the IP. The LP relaxation for the minimum hitting sets with $\alpha \ge 3$, minimum vertex covers on $\alpha$-uniform random graphs, is also studied. Analytic and numerical results strongly suggest that the LP relaxation fails to estimate optimal values above the critical average degree $c=e/(\alpha -1)$ where the replica symmetry is broken.

Figure 1

Frequency distribution of variables in the LP-relaxed min-HS, averaged over 100 random graphs with $\alpha =3, N=1600$, and $c=2.0$.

Figure 2

Saddle-point solution $P(h_1,h_2)$ of Eq. (15) obtained using a population dynamics with $\alpha =2, c=4, \mu =30$, and $r=0.01$. The fraction on each point is shown by the logarithmic gray scale. The number of population is ${10}^4$ and ${10}^4$ iterations are executed.

Figure 3

Maximal absolute eigenvalue for the local-stability matrix as a function of the average degree $c$. Solid and dotted lines represent the case of min-VC ($\alpha =2$) and min-HS ($\alpha =3$), respectively. The horizontal solid line is $max\left|\mathrm{\Lambda }\right(c\left)\right|=1$, above which the local stability breaks.

Figure 4

The minimum-cover ratio in Erdös-Rényi random graphs with $\alpha =2$ as a function of the average degree $c$. Circles are numerical results given by the replica exchange Monte Carlo method. Square marks are numerical results obtained using the revised simplex method with vertex cardinalities $N=50$ (open) and 200 (filled). These are averaged over 800 random graphs for the Monte Carlo method and 1600 random graphs for the LP relaxation. The solid and dotted lines, respectively, show the RS solutions in the IP limit and the LP limit. The vertical dashed line represents the critical average degree $c^{*}=e$.

Figure 5

Half-integral ratio $p_h$ as a function of the average degree $c$. Circles denote data obtained only using the revised simplex method with vertex cardinality $N=800$. Other open marks are numerical results obtained using the simplex method after running a leaf removal algorithm with $N=50$, 200, 800, and 2000. These are averaged over 1600 random graphs. The solid line represents the RS solution in the LP limit. The vertical dashed line represents the critical average degree $c^{*}=e$.

Figure 6

Minimum-cover ratio in Erdös-Rényi random graphs with $\alpha =3$ as a function of the average degree $c$. Circles are numerical results given by the replica exchange Monte Carlo (EMC) method. Marks denote the data obtained using the revised simplex method for vertex cardinalities of $N=800$ (square) and 1600 (triangle). These are averaged over 800 random graphs. The solid and dotted lines, respectively, show the RS solutions in the IP limit and the LP limit. The vertical dashed line represents the critical average degree $c^{*}=e/2$. In the inset, the LP-relaxed approximation values obtained by numerical results with $N=1600$ (triangle) and the RS solution in the LP limit (dashed line) are shown for relatively large $c$. The horizontal solid line is an upper bound of the LP relaxation for the min-HS ($\alpha =3$).