LP with box constraints

Posted on March 13, 2025 by Yu Cong
Tags: ,

In [1] the following edge-connectivity related problem is studied.
Problem1

Given a undirected weighted graph G=(V,E)G=(V,E), a weight function w:E→ℤ+w:E\to \mathbb{Z}_+ and an integer kk, find a kk-edge-connected spanning subgraph of GG with the minimum weight.

Consider the following LP relaxation,

min∑e∈Ew(e)xes.t.∑e∈δ(S)xe≥k∀S⊂V0≤xe≤1∀e∈E\begin{align*} \min& \quad \sum_{e\in E} w(e)x_e\\ s.t.& \quad \sum_{e\in \delta(S)}x_e\geq k &&\forall S\subset V\\ & \quad 0\le x_e \le 1 &&\forall e\in E \end{align*}

Note that xe≤1x_e\le 1 is necessary since each edge can only be chosen once. In the paper the authors mentioned that this kind of constraints are called box constraints and they usually make LPs difficult to solve (for example, positive covering LPs can be solved through MWU). There is also a box-free version of LP relaxation,

min∑e∈Ew(e)xes.t.∑e∈C\Sxe≥k−|S|∀ cut C∀S∈{F:|F|≤k−1∧F⊂C}∑e∈C\Sxe≥0∀e∈E \begin{align*} \min& \quad \sum_{e\in E} w(e)x_e\\ s.t.& \quad \sum_{e\in C\setminus S}x_e\geq k-|S| &&\forall \text{ cut } C\\ & &&\forall S\in \left\{ F: |F|\le k-1 \wedge F\subset C \right\}\\ & \quad \phantom{\sum_{e\in C\setminus S}} x_e\ge 0 &&\forall e\in E \end{align*} which is box-free but includes exponentially many extra constraints. I will call the first LP boxLP and the second one boxlessLP. Any feasible solution to the boxLP is also feasible in the boxlessLP. For any xe>1x_e>1 in a feasible solution of boxlessLP, we consider those cuts containing ee. For such a cut CC, ∑f∈C\exf≥k−1\sum_{f\in C\setminus e} x_f\geq k-1 and thus ∑e∈Cxe>k\sum_{e\in C} x_e>k. Since this holds for any cut CC containing ee, we can certainly decrease xex_e for a smaller objective. Hence, in the optimal solution to boxlessLP, every xex_e is less than or equal to 1.

Kent Quanrud also used this technique in kk-cut LP [2].

In fact, one can see from the proof that enumerating all singletons F={f}F=\left\{ f \right\} is sufficient.

References

[1]
P. Chalermsook, C.-C. Huang, D. Nanongkai, T. Saranurak, P. Sukprasert, S. Yingchareonthawornchai, Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver, in: 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2022: pp. 37:1–37:20 10.4230/LIPIcs.ICALP.2022.37.
[2]
K. Quanrud, Fast and deterministic approximations for k-cut, LIPIcs, Volume 145, APPROX/RANDOM 2019. 145 (2019) 23:1–23:20 10.4230/LIPICS.APPROX-RANDOM.2019.23.