Introduction
Let p 1 , … , p n ∈ R d p^1,\ldots,p^n \in\mathbb{R}^d p 1 , … , p n ∈ R d p i = ( p 1 i , … , p d i ) p^i=(p^i_1,\ldots,p^i_d) p i = ( p 1 i , … , p d i ) i ∈ [ n ] i \in[n] i ∈ [ n ] S ⊆ [ n ] S \subseteq[n] S ⊆ [ n ] t ∈ [ d ] t \in[d] t ∈ [ d ]
u t ( S ) : = max i ∈ S p t i , ℓ t ( S ) : = min i ∈ S p t i , wd t ( S ) : = u t ( S ) − ℓ t ( S ) . u_t(S):=\max_{i\in S}p^i_t,\qquad\ell_t(S):=\min_{i\in S}p^i_t,\qquad\operatorname{wd}_t(S):=u_t(S)-\ell_t(S). u t ( S ) := i ∈ S max p t i , ℓ t ( S ) := i ∈ S min p t i , wd t ( S ) := u t ( S ) − ℓ t ( S ) . Set wd t ( ∅ ) : = 0 \operatorname{wd}_t(\varnothing):=0 wd t ( ∅ ) := 0 t ∈ [ d ] t \in[d] t ∈ [ d ] S ⊆ [ n ] S \subseteq[n] S ⊆ [ n ] wd ( S ) : = ∑ t = 1 d wd t ( S ) \operatorname{wd}(S):=\sum_{t=1}^{d}\operatorname{wd}_t(S) wd ( S ) := ∑ t = 1 d wd t ( S ) wd ( S ) \operatorname{wd}(S) wd ( S ) S S S c i c_i c i i ∈ [ n ] i \in[n] i ∈ [ n ] c ( S ) : = ∑ i ∈ S c i c(S):=\sum_{i\in S}c_i c ( S ) := ∑ i ∈ S c i S S S Boxing Problem is
Definition 1.1 (Boxing Problem). Given p 1 , … , p n ∈ R d p^1,\ldots,p^n \in\mathbb{R}^d p 1 , … , p n ∈ R d c ∈ R + n c \in\mathbb{R}^n_+ c ∈ R + n
BP ( c ) : = max S ⊆ [ n ] { c ( S ) − wd ( S ) } . \operatorname{BP}(c):=\max_{S\subseteq[n]}\{c(S)-\operatorname{wd}(S)\}. BP ( c ) := S ⊆ [ n ] max { c ( S ) − wd ( S )} . For z ∈ { 0 , 1 } n z \in\{0,1\}^n z ∈ { 0 , 1 } n S ( z ) : = { i ∈ [ n ] : z i = 1 } S(z):=\{i \in[n]:z_i=1\} S ( z ) := { i ∈ [ n ] : z i = 1 } S ⊆ [ n ] S \subseteq[n] S ⊆ [ n ] χ S \chi^S χ S
Definition 1.2 (Boxing set). The Boxing Set is
B : = { ( w , z ) ∈ R × { 0 , 1 } n : w ≥ wd ( S ( z ) ) } . B:=\{(w,z)\in\mathbb{R}\times\{0,1\}^n:w\geq\operatorname{wd}(S(z))\}. B := {( w , z ) ∈ R × { 0 , 1 } n : w ≥ wd ( S ( z ))} . For J ⊆ [ n ] J \subseteq[n] J ⊆ [ n ]
B [ J ] : = B ∩ { ( w , z ) ∈ R × { 0 , 1 } n : z i = 0 for every i ∉ J } . B[J] := B \cap\{(w,z) \in\mathbb{R} \times\{0,1\}^{n} : z_i = 0 \text{ for every } i \notin J\}. B [ J ] := B ∩ {( w , z ) ∈ R × { 0 , 1 } n : z i = 0 for every i ∈ / J } . The Boxing Problem arises naturally in hyper-rectangular clustering, where points are partitioned into clusters to minimize the sum of the widths of their axis-aligned bounding boxes [5 , 16 ] . Delle Donne and Marenco [5 ] develop a branch-and-price algorithm for this problem.
To illustrate the connection, consider partitioning the points into exactly K K K C = 2 [ n ] ∖ { ∅ } \mathcal{C} = 2^{[n]} \setminus\{\emptyset\} C = 2 [ n ] ∖ { ∅ } y S y_S y S S ∈ C S \in\mathcal{C} S ∈ C
min ∑ S ∈ C wd ( S ) y S s.t. ∑ S ∈ C : i ∈ S y S = 1 ∀ i ∈ [ n ] , ∑ S ∈ C y S = K , y S ∈ { 0 , 1 } ∀ S ∈ C . \min\sum_{S \in\mathcal{C}} \operatorname{wd}(S)y_S \quad\text{s.t.} \quad\sum_{\substack{S \in\mathcal{C}:\\ i \in S}} y_S = 1 \ \forall i \in[n], \quad\sum_{S \in\mathcal{C}} y_S = K, \quad y_S \in\{0,1\} \ \forall S \in\mathcal{C}. min S ∈ C ∑ wd ( S ) y S s.t. S ∈ C : i ∈ S ∑ y S = 1 ∀ i ∈ [ n ] , S ∈ C ∑ y S = K , y S ∈ { 0 , 1 } ∀ S ∈ C . Since the number of possible clusters is exponential, column generation can be used to solve the linear relaxation. Let c i c_i c i i i i γ \gamma γ min ∅ ≠ S ⊆ [ n ] wd ( S ) − c ( S ) \min_{\emptyset\ne S \subseteq[n]} \operatorname{wd}(S) - c(S) min ∅ = S ⊆ [ n ] wd ( S ) − c ( S ) − γ -\gamma − γ c i c_i c i
The width function is not submodular on all of 2 [ n ] 2^{[n]} 2 [ n ]
Related work
Submodular set functions have a well-developed optimization and polyhedral theory. Edmonds [6 ] established the greedy algorithm for optimizing linear functions over submodular polyhedra, while the Lovász extension gives a convex representation of a submodular function and describes the convex hull of its binary epigraph through extended polymatroid inequalities [15 ] . Atamtürk and Narayanan [1 ] develop a polarity-based approach to set-function epigraphs. Their polar relaxation, based on homogeneous inequalities, is exact for submodular functions but generally provides only an outer approximation for non-submodular functions. Related polyhedral convexification results have also been developed for broader classes of submodular functions [23 , 24 , 25 ] . In contrast, the box-width function is not globally submodular: it satisfies the submodular inequality for intersecting sets, but the inequality may fail for disjoint sets. Consequently, the standard submodular epigraph description does not directly characterize the Boxing Set. Our approach considers the normalized polar coefficient polyhedron, which explicitly includes the right-hand-side variable needed to characterize nontrivial facets.
The algorithmic theory of submodular functions also provides important tools for our analysis. Edmonds’ greedy algorithm and its extensions to intersecting-submodular polyhedra are closely related to Dilworth truncation and the optimization of partition functions [6 , 7 ] . Nagano, Kawahara, and Iwata [17 ] use these connections to study parametric partition optimization. Strongly polynomial algorithms for submodular-function minimization are also available [19 ] . We exploit these techniques and provide a modified greedy procedure based on submodular-function minimization to compute the facet right-hand sides.
Although submodularity is restricted, the Boxing Set has a rich combinatorial structure that allows uncrossing arguments . Uncrossing is widely used in polyhedral combinatorics and approximation algorithms to establish laminar families of tight constraints. For example, Jain [11 ] shows that the tight cut constraints of a basic LP solution in survivable network design admit a laminar basis, which is central to his iterative-rounding algorithm. Related techniques appear in primal-dual network-design algorithms [8 , 21 ] and are developed systematically by Lau, Ravi, and Singh [14 ] . Our use of uncrossing is different: rather than analyzing the tight constraints of a basic LP solution, we uncross the tight constraints of the normalized polar coefficient polyhedron associated with a facet of the Boxing Set. This is possible because the width function is intersecting submodular, even though it is not submodular. The resulting laminar family uniquely determines the facet coefficients. By further analyzing its structure, we prove that every nontrivial facet can be obtained through sequential lifting. Thus, our approach extends the polarity-based viewpoint of Atamtürk and Narayanan [1 ] from homogeneous inequalities to a structural analysis of nontrivial facets with positive right-hand sides.
A separate line of related work concerns mixing sets and their intersections. Günlük and Pochet [9 ] develop mixing inequalities, while Atamtürk, Nemhauser, and Savelsbergh [2 ] study systems with multiple continuous variables sharing common binary variables. Conforti, Wolsey, and Zambelli [4 ] and Küçükyavuz [12 ] investigate related mixing-set formulations and additional constraints. Most closely related to our work, Kılınç-Karzan, Küçükyavuz, and Lee [13 ] establish a connection between mixing inequalities and submodularity, and study intersections of mixing sets with common binary variables under an additional linking constraint. Their approach exploits the submodular structure underlying mixing sets. However, it does not directly characterize the Boxing Set, because the original box-width function is not submodular. We overcome this difficulty through anchoring : fixing one selected point expresses the width as a sum of one-sided maxima, each of which is submodular. Thus, every anchored Boxing Set can be represented by an intersection of mixing sets with an epigraph linking constraint. Combining these anchored sets by disjunctive programming then yields a compact extended formulation for the original Boxing Set. Beyond this mixing-set representation, our polyhedral analysis directly addresses the original non-submodular width function, leading to the laminar facet structure and the complete one-dimensional convex-hull description.
In recent independent work, Wu, He, and Tawarmalani [22 ] develop a convexification framework for disjunctive submodular functions with any finite number of disjuncts. They obtain compact LP separation formulations when the component epigraph convex hulls admit compact formulations, and strongly polynomial separation for the minimum of two submodular functions on a common lattice. Our anchoring construction fits their pointwise-minimum framework, while their greedy construction and Dilworth truncation connect to our fixed-right-hand-side lifting and partition analysis. We exploit the geometry of the Boxing Problem to obtain sparse maximum-weight-closure formulations, a compact extended formulation, and a minimum-cost-flow separation algorithm in one dimension. Our polyhedral analysis further establishes laminar facet structure, a complete one-dimensional facet description, and a characterization of facet right-hand-side parameters through partitions of tight sets.
Contributions
We establish new optimization and polyhedral results for the Boxing Set, whose underlying width function is a monotone set function that is not globally submodular.
Higher-dimensional extensions. We characterize facet right-hand sides through partitions of tight sets, give polynomial-time algorithms for computing the associated partition parameter for a fixed subset and the smallest facet right-hand side, and identify additional families of facets.
The remainder of the paper is organized as follows. § 2 revisits extended formulations and develops optimization algorithms for the intersection of mixing sets over common binary variables. § 3 applies these results to the Boxing Set. § 4 studies general polyhedral properties, including laminarity and sequential lifting. § 5 gives the complete one-dimensional facet description and separation algorithm, and § 6 investigates the higher-dimensional case.
Multi-Mixing Sets
We begin by providing an algorithmic reformulation of known mixing-set structure [9 ] that is particularly useful for the Boxing Problem. For multiple mixing sets sharing common binary variables and having independent continuous variables, existing convex-hull results yield a compact extended formulation. We then exploit the ordered structure of the mixing coefficients to reduce linear optimization over their intersection to a maximum-weight graph closure problem, which can be solved by a minimum s s s t t t
This approach is closely related to the graph-based formulations of Conforti, Wolsey, and Zambelli [4 ] , who study mixed-integer covers on bipartite graphs and their equivalence to network-dual formulations. While their work focuses on deriving convex-hull descriptions through projections of extended formulations, our focus is on constructing a sparse closure graph that directly solves the multi-mixing optimization problem. This representation will be used in § 3 to solve the Boxing Problem after fixing an anchor point.
Let k ≥ 1 k \ge1 k ≥ 1 r ∈ [ k ] r \in[k] r ∈ [ k ] q r = ( q i r ) i ∈ [ n ] ∈ R + n q^r = (q_i^r)_{i \in[n]} \in\mathbb{R}_+^n q r = ( q i r ) i ∈ [ n ] ∈ R + n k k k [9 ] sharing the same binary vector z z z
MIX r ( q ) : = conv { ( u , z ) ∈ R k × { 0 , 1 } n : u r ≥ q i r z i ∀ i ∈ [ n ] } . \operatorname{MIX}_r(q) := \operatorname{conv}\left\{(u,z) \in\mathbb{R}^k \times\{0,1\}^n : u_r \ge q_i^r z_i \quad\forall i \in[n]\right\}. MIX r ( q ) := conv { ( u , z ) ∈ R k × { 0 , 1 } n : u r ≥ q i r z i ∀ i ∈ [ n ] } . We call the set
MMIX ( q ) : = { ( u , z ) ∈ R k × { 0 , 1 } n : u r ≥ q i r z i ∀ i ∈ [ n ] , r ∈ [ k ] } (1) \operatorname{MMIX}(q) := \left\{(u,z) \in\mathbb{R}^k \times\{0,1\}^n : u_r \ge q_i^r z_i \quad\forall i \in[n],\ r \in[k]\right\} \tag*{(1)} MMIX ( q ) := { ( u , z ) ∈ R k × { 0 , 1 } n : u r ≥ q i r z i ∀ i ∈ [ n ] , r ∈ [ k ] } (1) the multi-mixing set . It is the intersection of k k k [2 ] , and later by Kılınç-Karzan, Küçükyavuz, and Lee [13 ] . In particular, for this multi-mixing set without additional linking constraints, their results give
conv ( MMIX ( q ) ) = ⋂ r ∈ [ k ] conv ( MIX r ( q ) ) . (2) \operatorname{conv}(\operatorname{MMIX}(q)) = \bigcap_{r \in[k]} \operatorname{conv}(\operatorname{MIX}_r(q)). \tag*{(2)} conv ( MMIX ( q )) = r ∈ [ k ] ⋂ conv ( MIX r ( q )) . (2) where the convex hull of the mixing set is given by the mixing inequalities [9 ] .
For every r ∈ [ k ] r \in[k] r ∈ [ k ] σ r : [ n ] → [ n ] \sigma_r : [n] \to[n] σ r : [ n ] → [ n ] q r σ r ( 1 ) ≤ q r σ r ( 2 ) ≤ ⋯ ≤ q r σ r ( n ) q_r^{\sigma_r(1)} \le q_r^{\sigma_r(2)} \le\cdots\le q_r^{\sigma_r(n)} q r σ r ( 1 ) ≤ q r σ r ( 2 ) ≤ ⋯ ≤ q r σ r ( n ) η r , 0 : = 0 \eta_{r,0} := 0 η r , 0 := 0 η r , ℓ : = q r σ r ( ℓ ) \eta_{r,\ell} := q_r^{\sigma_r(\ell)} η r , ℓ := q r σ r ( ℓ ) ℓ ∈ [ n ] \ell\in[n] ℓ ∈ [ n ] Δ r , ℓ : = η r , ℓ − η r , ℓ − 1 \Delta_{r,\ell} := \eta_{r,\ell} - \eta_{r,\ell-1} Δ r , ℓ := η r , ℓ − η r , ℓ − 1 r ∈ [ k ] r \in[k] r ∈ [ k ] y r ∈ R n y^r \in\mathbb{R}^n y r ∈ R n M I X r \mathrm{MIX}_r MIX r [3 ]
M I X ^ r : = { ( u , z , y r ) : z σ r ( ℓ ) ≤ y ℓ r ℓ ∈ [ n ] , y ℓ + 1 r ≤ y ℓ r ℓ = 1 , … , n − 1 , u r ≥ ∑ ℓ = 1 n Δ r , ℓ y ℓ r , 0 ≤ z i ≤ 1 i ∈ [ n ] , 0 ≤ y ℓ r ≤ 1 ℓ ∈ [ n ] } . (3) \widehat{\mathrm{MIX}}_r := \left\{(u,z,y^r) :
\begin{aligned}
z_{\sigma_r(\ell)} &\le y^r_\ell&& \ell\in[n],\\
y^r_{\ell+1} &\le y^r_\ell&& \ell= 1,\ldots,n-1,\\
u_r &\ge\sum_{\ell=1}^{n}\Delta_{r,\ell}y^r_\ell,\\
0 &\le z_i \le1 && i \in[n],\\
0 &\le y^r_\ell\le1 && \ell\in[n]
\end{aligned}
\right\}. \tag*{(3)} MIX r := ⎩ ⎨ ⎧ ( u , z , y r ) : z σ r ( ℓ ) y ℓ + 1 r u r 0 0 ≤ y ℓ r ≤ y ℓ r ≥ ℓ = 1 ∑ n Δ r , ℓ y ℓ r , ≤ z i ≤ 1 ≤ y ℓ r ≤ 1 ℓ ∈ [ n ] , ℓ = 1 , … , n − 1 , i ∈ [ n ] , ℓ ∈ [ n ] ⎭ ⎬ ⎫ . (3) Thus proj u , z ( M I X ^ r ( q ) ) = M I X r ( q ) \operatorname{proj}_{u,z}(\widehat{\mathrm{MIX}}_r(q)) = \mathrm{MIX}_r(q) proj u , z ( MIX r ( q )) = MIX r ( q )
Theorem 2.1. The convex hull of the multi-mixing set (1) admits an extended formulation with O ( k n ) O(kn) O ( k n )
Proof. By (2) , it suffices to show
⋂ r ∈ [ k ] M I X r ( q ) = proj u , z { ( u , z , y ) : ( u , z , y r ) ∈ M I X ^ r ∀ r ∈ [ k ] } . \bigcap_{r\in[k]} \mathrm{MIX}_r(q) = \operatorname{proj}_{u,z}\left\{(u,z,y) : (u,z,y^r) \in\widehat{\mathrm{MIX}}_r\quad\forall r \in[k]\right\}. r ∈ [ k ] ⋂ MIX r ( q ) = proj u , z { ( u , z , y ) : ( u , z , y r ) ∈ MIX r ∀ r ∈ [ k ] } . We have
( u , z ) ∈ proj u , z { ( u , z , y ) : ( u , z , y r ) ∈ M I X ^ r ∀ r ∈ [ k ] } ⟺ ∃ y 1 , … , y k such that ( u , z , y r ) ∈ M I X ^ r ∀ r ∈ [ k ] ⟺ ( u , z ) ∈ M I X r ∀ r ∈ [ k ] ⟺ ( u , z ) ∈ ⋂ r ∈ [ k ] M I X r . \begin{aligned}
(u,z) &\in\operatorname{proj}_{u,z}\left\{(u,z,y) : (u,z,y^r) \in\widehat{\mathrm{MIX}}_r\quad\forall r \in[k]\right\}\\
&\Longleftrightarrow\exists y^1,\ldots,y^k\text{ such that }(u,z,y^r)\in\widehat{\mathrm{MIX}}_r\quad\forall r\in[k]\\
&\Longleftrightarrow(u,z)\in\mathrm{MIX}_r\quad\forall r\in[k]\\
&\Longleftrightarrow(u,z)\in\bigcap_{r\in[k]}\mathrm{MIX}_r.
\end{aligned} ( u , z ) ∈ proj u , z { ( u , z , y ) : ( u , z , y r ) ∈ MIX r ∀ r ∈ [ k ] } ⟺ ∃ y 1 , … , y k such that ( u , z , y r ) ∈ MIX r ∀ r ∈ [ k ] ⟺ ( u , z ) ∈ MIX r ∀ r ∈ [ k ] ⟺ ( u , z ) ∈ r ∈ [ k ] ⋂ MIX r . We use M M I X ^ ( q ) \widehat{\mathrm{MMIX}}(q) MMIX ( q ) M I X ^ r ( q ) \widehat{\mathrm{MIX}}_r(q) MIX r ( q )
Polynomial-time optimization over multi-mixing sets
Given c ∈ R n c \in\mathbb{R}^n c ∈ R n λ ∈ R + k \lambda\in\mathbb{R}_+^k λ ∈ R + k
M M O P T ( c , λ ) : = max ( u , z ) ∈ M M I X ( q ) { c T z − ∑ r = 1 k λ r u r } . \mathrm{MMOPT}(c,\lambda) := \max_{(u,z)\in\mathrm{MMIX}(q)}\left\{c^\mathsf{T}z-\sum_{r=1}^{k}\lambda_r u_r\right\}. MMOPT ( c , λ ) := ( u , z ) ∈ MMIX ( q ) max { c T z − r = 1 ∑ k λ r u r } . For fixed binary z z z u r u_r u r max i ∈ S ( z ) q r i \max_{i\in S(z)}q_r^i max i ∈ S ( z ) q r i λ ≥ 0 \lambda\ge0 λ ≥ 0
M M O P T ( c , λ ) = max S ⊆ [ n ] { c ( S ) − ∑ r = 1 k λ r max i ∈ S q r i } . \mathrm{MMOPT}(c,\lambda)=\max_{S\subseteq[n]}\left\{c(S)-\sum_{r=1}^{k}\lambda_r\max_{i\in S}q_r^i\right\}. MMOPT ( c , λ ) = S ⊆ [ n ] max { c ( S ) − r = 1 ∑ k λ r i ∈ S max q r i } . We propose a polynomial-time algorithm for this problem using maximum-weight closure. We first recall this classical graph problem.
Figure 1. Graph-closure reduction for k = 2 k = 2 k = 2 n = 3 n = 3 n = 3 q 1 = ( 2 , 1 , 4 ) q_1 = (2,1,4) q 1 = ( 2 , 1 , 4 ) q 2 = ( 1 , 4 , 2 ) q_2 = (1,4,2) q 2 = ( 1 , 4 , 2 ) λ 1 = λ 2 = 1 \lambda_1 = \lambda_2 = 1 λ 1 = λ 2 = 1
Definition 2.2 (Maximum-weight closure of a graph). Let G = ( V , A ) G = (V,A) G = ( V , A ) X ⊆ V X \subseteq V X ⊆ V closure of G G G u ∈ X u \in X u ∈ X ( u , v ) ∈ A (u,v) \in A ( u , v ) ∈ A v ∈ X v \in X v ∈ X X X X X X X ω ∈ R V \omega\in\mathbb{R}^{V} ω ∈ R V maximum-weight closure problem is max { ∑ v ∈ X ω v : X ⊆ V is a closure of G } \max\{\sum_{v\in X}\omega_v : X \subseteq V \text{ is a closure of } G\} max { ∑ v ∈ X ω v : X ⊆ V is a closure of G }
The maximum-weight closure problem is polynomially solvable through the classical reduction to a minimum s s s t t t [20 , 10 ] . For completeness, we recall the reduction. Let
V + : = { v ∈ V : ω v > 0 } , V − : = { v ∈ V : ω v < 0 } , W + : = ∑ v ∈ V + ω v . V^+ := \{v \in V : \omega_v > 0\}, \qquad V^- := \{v \in V : \omega_v < 0\}, \qquad W^+ := \sum_{v\in V^+}\omega_v. V + := { v ∈ V : ω v > 0 } , V − := { v ∈ V : ω v < 0 } , W + := v ∈ V + ∑ ω v . Add a source s s s t t t v ∈ V + v \in V^+ v ∈ V + ( s , v ) (s,v) ( s , v ) ω v \omega_v ω v v ∈ V − v \in V^- v ∈ V − ( v , t ) (v,t) ( v , t ) − ω v -\omega_v − ω v ( u , v ) ∈ A (u,v) \in A ( u , v ) ∈ A ( u , v ) (u,v) ( u , v ) M M M M > W + M > W^+ M > W + s s s t t t M M M V V V W + W^+ W + X X X W + − ω ( X ) W^+ - \omega(X) W + − ω ( X ) s s s t t t
We now construct a directed graph G ( c , λ ) = ( V , A ) G(c,\lambda) = (V,A) G ( c , λ ) = ( V , A ) ( c , λ ) (c,\lambda) ( c , λ ) σ r \sigma_r σ r i ∈ [ n ] i \in[n] i ∈ [ n ] item node v i ∈ V v_i \in V v i ∈ V ω ( v i ) : = c i \omega(v_i) := c_i ω ( v i ) := c i r ∈ [ k ] r \in[k] r ∈ [ k ] ℓ ∈ [ n ] \ell\in[n] ℓ ∈ [ n ] expansion node e r , ℓ ∈ V e_{r,\ell} \in V e r , ℓ ∈ V
ω ( e r , ℓ ) : = { − λ r q r σ r ( 1 ) , ℓ = 1 , − λ r ( q r σ r ( ℓ ) − q r σ r ( ℓ − 1 ) ) , ℓ = 2 , … , n . \omega(e_{r,\ell}) :=
\begin{cases}
-\lambda_r q_r^{\sigma_r(1)}, & \ell= 1,\\
-\lambda_r\left(q_r^{\sigma_r(\ell)} - q_r^{\sigma_r(\ell-1)}\right), & \ell= 2,\ldots,n.
\end{cases} ω ( e r , ℓ ) := { − λ r q r σ r ( 1 ) , − λ r ( q r σ r ( ℓ ) − q r σ r ( ℓ − 1 ) ) , ℓ = 1 , ℓ = 2 , … , n . For ℓ = 2 , … , n \ell= 2,\ldots,n ℓ = 2 , … , n ( e r , ℓ , e r , ℓ − 1 ) ∈ A (e_{r,\ell},e_{r,\ell-1}) \in A ( e r , ℓ , e r , ℓ − 1 ) ∈ A i = σ r ( ℓ ) i = \sigma_r(\ell) i = σ r ( ℓ ) r ∈ [ k ] r \in[k] r ∈ [ k ] ( v i , e r , ℓ ) ∈ A (v_i,e_{r,\ell}) \in A ( v i , e r , ℓ ) ∈ A
Lemma 2.3. For every c ∈ R n c \in\mathbb{R}^n c ∈ R n λ ∈ R + k \lambda\in\mathbb{R}_+^k λ ∈ R + k G ( c , λ ) G(c,\lambda) G ( c , λ ) ( c , λ ) (c,\lambda) ( c , λ )
Proof. Let X ⊆ V X \subseteq V X ⊆ V T ( X ) : = { i ∈ [ n ] : v i ∈ X } T(X) := \{i \in[n] : v_i \in X\} T ( X ) := { i ∈ [ n ] : v i ∈ X } r ∈ [ k ] r \in[k] r ∈ [ k ] v i ∈ X v_i \in X v i ∈ X i = σ r ( ℓ ) i = \sigma_r(\ell) i = σ r ( ℓ ) ( v i , e r , ℓ ) (v_i,e_{r,\ell}) ( v i , e r , ℓ )
e r , ℓ → e r , ℓ − 1 → ⋯ → e r , 1 e_{r,\ell} \to e_{r,\ell-1} \to\cdots\to e_{r,1} e r , ℓ → e r , ℓ − 1 → ⋯ → e r , 1 forces e r , 1 , … , e r , ℓ e_{r,1},\ldots,e_{r,\ell} e r , 1 , … , e r , ℓ X X X T ( X ) T(X) T ( X ) r r r
− λ r q r σ r ( 1 ) − λ r ∑ h = 2 ℓ ( q r σ r ( h ) − q r σ r ( h − 1 ) ) = − λ r q r σ r ( ℓ ) . -\lambda_r q_r^{\sigma_r(1)}-\lambda_r\sum_{h=2}^{\ell}\left(q_r^{\sigma_r(h)}-q_r^{\sigma_r(h-1)}\right)=-\lambda_r q_r^{\sigma_r(\ell)}. − λ r q r σ r ( 1 ) − λ r h = 2 ∑ ℓ ( q r σ r ( h ) − q r σ r ( h − 1 ) ) = − λ r q r σ r ( ℓ ) . Taking ℓ \ell ℓ T ( X ) T(X) T ( X ) − λ r max i ∈ T ( X ) q r i -\lambda_r\max_{i\in T(X)}q_r^i − λ r max i ∈ T ( X ) q r i T ( X ) = ∅ T(X)=\varnothing T ( X ) = ∅
ω ( X ) ≤ c ( T ( X ) ) − ∑ r = 1 k λ r max i ∈ T ( X ) q r i . \omega(X)\leq c(T(X))-\sum_{r=1}^{k}\lambda_r\max_{i\in T(X)}q_r^i. ω ( X ) ≤ c ( T ( X )) − r = 1 ∑ k λ r i ∈ T ( X ) max q r i . This is at most MMOPT ( c , λ ) \operatorname{MMOPT}(c,\lambda) MMOPT ( c , λ )
For the reverse inequality, fix any T ⊆ [ n ] T\subseteq[n] T ⊆ [ n ] v i v_i v i i ∈ T i\in T i ∈ T r ∈ [ k ] r\in[k] r ∈ [ k ] T T T T = ∅ T=\varnothing T = ∅ X ( T ) X(T) X ( T )
ω ( X ( T ) ) = c ( T ) − ∑ r = 1 k λ r max i ∈ T q r i . \omega(X(T))=c(T)-\sum_{r=1}^{k}\lambda_r\max_{i\in T}q_r^i. ω ( X ( T )) = c ( T ) − r = 1 ∑ k λ r i ∈ T max q r i . Maximizing over T T T MMOPT ( c , λ ) \operatorname{MMOPT}(c,\lambda) MMOPT ( c , λ )
Theorem 2.4 (Polynomial-time optimization over multi-mixing sets). The optimization problem MMOPT ( c , λ ) \operatorname{MMOPT}(c,\lambda) MMOPT ( c , λ ) can be solved by one maximum-weight closure computation on a directed acyclic graph with O ( k n ) O(kn) O ( k n ) nodes and arcs. Equivalently, it can be solved by one minimum s s s t t t cut computation on a graph of the same order in O ( k 3 n 3 ) O(k^3n^3) O ( k 3 n 3 ) time plus an overhead of O ( k n log n ) O(kn\log n) O ( k n log n ) time for constructing the graph.
Proof. By Lemma 2.3, the optimal value equals the maximum closure weight in G ( c , λ ) G(c,\lambda) G ( c , λ ) n n n k n kn k n k n kn k n k ( n − 1 ) k(n-1) k ( n − 1 ) O ( k n ) O(kn) O ( k n )
Boxing Problem: Complexity and Extended Formulation
Fixing an anchor point allows us to model the Boxing Set using a multi-mixing set. We then combine the anchored sets through disjunctive programming to obtain a compact extended formulation for conv ( B ) \operatorname{conv}(B) conv ( B )
The anchored boxing sets
Fix an anchor a ∈ [ n ] a\in[n] a ∈ [ n ] S ⊆ [ n ] S\subseteq[n] S ⊆ [ n ] a ∈ S a\in S a ∈ S S S S a a a S S S
wd ( S ) = ∑ t = 1 d ( max i ∈ S , p t i ≥ p t a ( p t i − p t a ) + max i ∈ S , p t i < p t a ( p t a − p t i ) ) . \operatorname{wd}(S)=\sum_{t=1}^{d}\left(\max_{\substack{i\in S,\ p_t^i\geq p_t^a}}(p_t^i-p_t^a)+\max_{\substack{i\in S,\ p_t^i<p_t^a}}(p_t^a-p_t^i)\right). wd ( S ) = t = 1 ∑ d ( i ∈ S , p t i ≥ p t a max ( p t i − p t a ) + i ∈ S , p t i < p t a max ( p t a − p t i ) ) . The maximum over an empty index set is taken to be zero. This decomposition therefore motivates us to define the positive and negative expansions of a point i i i a a a
q t , + a i : = max { 0 , p t i − p t a } , q t , − a i : = max { 0 , p t a − p t i } , i ∈ [ n ] , t ∈ [ d ] . q^{ai}_{t,+} := \max\{0,p^i_t-p^a_t\},\qquad q^{ai}_{t,-} := \max\{0,p^a_t-p^i_t\},\qquad i\in[n],\ t\in[d]. q t , + ai := max { 0 , p t i − p t a } , q t , − ai := max { 0 , p t a − p t i } , i ∈ [ n ] , t ∈ [ d ] . Let H : = { ( t , + ) , ( t , − ) : t ∈ [ d ] } \mathcal{H}:=\{(t,+),(t,-):t\in[d]\} H := {( t , + ) , ( t , − ) : t ∈ [ d ]} 2 d 2d 2 d q h a i q^{ai}_h q h ai a a a
q a : = ( q h a i ) h ∈ H , i ∈ [ n ] ∈ R + H × [ n ] , q h a a = 0 ∀ h ∈ H . q^a := (q^{ai}_h)_{h\in\mathcal{H},i\in[n]}\in\mathbb{R}^{\mathcal{H}\times[n]}_+,\qquad q^{aa}_h=0\quad\forall h\in\mathcal{H}. q a := ( q h ai ) h ∈ H , i ∈ [ n ] ∈ R + H × [ n ] , q h aa = 0 ∀ h ∈ H . Thus, q a q^a q a MMIX ( q a ) \operatorname{MMIX}(q^a) MMIX ( q a ) k = 2 d k=2d k = 2 d S ⊆ [ n ] S\subseteq[n] S ⊆ [ n ] a a a a a a wd ( S ) = ∑ h ∈ H max i ∈ S q h a i \operatorname{wd}(S)=\sum_{h\in\mathcal{H}}\max_{i\in S}q^{ai}_h wd ( S ) = ∑ h ∈ H max i ∈ S q h ai
For each a ∈ [ n ] a\in[n] a ∈ [ n ] B a : = B ∩ { ( w , z ) : z a = 1 } B_a:=B\cap\{(w,z):z_a=1\} B a := B ∩ {( w , z ) : z a = 1 }
B a = { ( w , z ) ∈ R × { 0 , 1 } n : ∃ u ∈ R H such that ( u , z ) ∈ MMIX ( q a ) , z a = 1 , w ≥ ∑ h ∈ H u h } . (4) B_a=\left\{(w,z)\in\mathbb{R}\times\{0,1\}^n:
\begin{array}{l}
\exists u\in\mathbb{R}^{\mathcal{H}}\text{ such that }(u,z)\in\operatorname{MMIX}(q^a),\\
z_a=1,\quad w\geq\sum_{h\in\mathcal{H}}u_h
\end{array}
\right\}. \tag*{(4)} B a = { ( w , z ) ∈ R × { 0 , 1 } n : ∃ u ∈ R H such that ( u , z ) ∈ MMIX ( q a ) , z a = 1 , w ≥ ∑ h ∈ H u h } . (4) Using the extended formulation of Section 2.1, define
B ^ a : = { ( w , z , u , y ) : ( u , z , y ) ∈ MMIX ^ ( q a ) , z a = 1 , w ≥ ∑ h ∈ H u h } . \widehat{B}_a:=\left\{(w,z,u,y):
\begin{array}{l}
(u,z,y)\in\widehat{\operatorname{MMIX}}(q^a),\\
z_a=1,\quad w\geq\sum_{h\in\mathcal{H}}u_h
\end{array}
\right\}. B a := { ( w , z , u , y ) : ( u , z , y ) ∈ MMIX ( q a ) , z a = 1 , w ≥ ∑ h ∈ H u h } . Lemma 3.1. For every a ∈ [ n ] a\in[n] a ∈ [ n ]
conv ( B a ) = { ( w , z ) : ∃ u ∈ R H such that ( u , z ) ∈ conv ( MMIX ( q a ) ) , z a = 1 , w ≥ ∑ h ∈ H u h } = proj w , z ( B ^ a ) . \operatorname{conv}(B_a)=\left\{(w,z):
\begin{array}{l}
\exists u\in\mathbb{R}^{\mathcal{H}}\text{ such that }(u,z)\in\operatorname{conv}(\operatorname{MMIX}(q^a)),\\
z_a=1,\quad w\geq\sum_{h\in\mathcal{H}}u_h
\end{array}
\right\}
=\operatorname{proj}_{w,z}(\widehat{B}_a). conv ( B a ) = { ( w , z ) : ∃ u ∈ R H such that ( u , z ) ∈ conv ( MMIX ( q a )) , z a = 1 , w ≥ ∑ h ∈ H u h } = proj w , z ( B a ) . Moreover, B ^ a \widehat{B}_a B a O ( d n ) O(dn) O ( d n )
Proof. By Theorem 2.1, MMIX ^ ( q a ) \widehat{\operatorname{MMIX}}(q^a) MMIX ( q a ) conv ( MMIX ( q a ) ) \operatorname{conv}(\operatorname{MMIX}(q^a)) conv ( MMIX ( q a )) z a = 1 z_a=1 z a = 1 w w w w ≥ ∑ h ∈ H u h w\geq\sum_{h\in\mathcal{H}}u_h w ≥ ∑ h ∈ H u h w w w proj w , z ( B ^ a ) = conv ( B a ) \operatorname{proj}_{w,z}(\widehat{B}_a)=\operatorname{conv}(B_a) proj w , z ( B a ) = conv ( B a ) k = 2 d k=2d k = 2 d
Let B 0 : = { ( w , 0 ) ∈ R × { 0 , 1 } n : w ≥ 0 } B_0:=\{(w,0)\in\mathbb{R}\times\{0,1\}^n:w\geq0\} B 0 := {( w , 0 ) ∈ R × { 0 , 1 } n : w ≥ 0 }
Theorem 3.2. The Boxing Set satisfies B = B 0 ∪ ⋃ a = 1 n B a B=B_0\cup\bigcup_{a=1}^nB_a B = B 0 ∪ ⋃ a = 1 n B a conv ( B ) = conv ( B 0 ∪ ⋃ a = 1 n B a ) \operatorname{conv}(B)=\operatorname{conv}\left(B_0\cup\bigcup_{a=1}^nB_a\right) conv ( B ) = conv ( B 0 ∪ ⋃ a = 1 n B a ) BP ( c ) = max { 0 , max a ∈ [ n ] max ( w , z ) ∈ B a { c ⊤ z − w } } \operatorname{BP}(c)=\max\left\{0,\max_{a\in[n]}\max_{(w,z)\in B_a}\{c^\top z-w\}\right\} BP ( c ) = max { 0 , max a ∈ [ n ] max ( w , z ) ∈ B a { c ⊤ z − w } }
Proof. Every nonempty support contains an anchor a ∈ [ n ] a\in[n] a ∈ [ n ] B 0 B_0 B 0
Since q h a a = 0 q^{aa}_h=0 q h aa = 0 h ∈ H h\in\mathcal{H} h ∈ H c a ≥ 0 c_a\geq0 c a ≥ 0 a a a z a = 1 z_a=1 z a = 1 MMOPT ( c , 1 ) \operatorname{MMOPT}(c,1) MMOPT ( c , 1 ) MMOPT ( c , 1 ) \operatorname{MMOPT}(c,1) MMOPT ( c , 1 )
Corollary 3.3. The Boxing Problem can be solved in O ( d 3 n 4 ) O(d^3n^4) O ( d 3 n 4 )
Extended formulation for the Boxing Set
We combine the n + 1 n+1 n + 1 λ a ≥ 0 \lambda_a \ge0 λ a ≥ 0 a = 0 , … , n a=0,\ldots,n a = 0 , … , n ∑ a = 0 n λ a = 1 \sum_{a=0}^{n}\lambda_a=1 ∑ a = 0 n λ a = 1 a ∈ [ n ] a\in[n] a ∈ [ n ] ( w a , z a , u a , y a ) (w^a,z^a,u^a,y^a) ( w a , z a , u a , y a ) B ˉ a \bar{B}_a B ˉ a λ a \lambda_a λ a w 0 ≥ 0 w^0\ge0 w 0 ≥ 0 E \mathcal{E} E ( w , z , ξ ) (w,z,\xi) ( w , z , ξ ) ξ : = ( λ , w 0 , { w a , z a , u a , y a } a = 1 n ) \xi:= (\lambda,w^0,\{w^a,z^a,u^a,y^a\}_{a=1}^n) ξ := ( λ , w 0 , { w a , z a , u a , y a } a = 1 n ) E ⊆ R n + 1 × R n + 2 + n ( 1 + n + 2 d + 2 d n ) \mathcal{E}\subseteq\mathbb{R}^{n+1}\times\mathbb{R}^{n+2+n(1+n+2d+2dn)} E ⊆ R n + 1 × R n + 2 + n ( 1 + n + 2 d + 2 d n )
Corollary 3.4. The formulation E \mathcal{E} E proj w , z ( E ) = conv ( B ) \operatorname{proj}_{w,z}(\mathcal{E})=\operatorname{conv}(B) proj w , z ( E ) = conv ( B ) Moreover, E \mathcal{E} E O ( d n 2 ) O(dn^2) O ( d n 2 ) variables and inequalities.
Remark 3.5. Küçükyavuz [12 ] develops a disjunctive extended formulation by fixing possible values of the continuous mixing variable. Direct extension of this strategy to the Boxing Set by enumerating coordinate-wise box extrema may involve up to n 2 d n^{2d} n 2 d n + 1 n+1 n + 1 O ( d n 2 ) O(dn^2) O ( d n 2 ) n n n d d d
An important consequence of Corollary 3.4 is that optimization and separation over conv ( B ) \operatorname{conv}(B) conv ( B )
Corollary 3.6. For rational input data, linear optimization over B B B conv ( B ) \operatorname{conv}(B) conv ( B ) n n n d d d
Corollary 3.7. Separation over conv ( B ) \operatorname{conv}(B) conv ( B ) ( w ^ , z ^ ) (\hat{w},\hat{z}) ( w ^ , z ^ ) z ^ ∈ [ 0 , 1 ] n \hat{z}\in[0,1]^n z ^ ∈ [ 0 , 1 ] n w w w w ≥ 0 w\ge0 w ≥ 0 min { w : ( w , z ^ , ξ ) ∈ E } − w ^ \min\{w:(w,\hat{z},\xi)\in\mathcal{E}\}-\hat{w} min { w : ( w , z ^ , ξ ) ∈ E } − w ^
Basic Polyhedral Properties
Although the extended formulation gives a compact representation in a higher-dimensional space, the facets of conv ( B ) \operatorname{conv}(B) conv ( B ) ( w , z ) (w,z) ( w , z )
Proposition 4.1. The following are basic properties of conv ( B ) \operatorname{conv}(B) conv ( B )
The convex hull conv ( B ) \operatorname{conv}(B) conv ( B ) R n + 1 \mathbb{R}^{n+1} R n + 1 rec ( conv ( B ) ) = { ( w , 0 ) ∈ R × R n : w ≥ 0 } \operatorname{rec}(\operatorname{conv}(B))=\{(w,0)\in\mathbb{R}\times\mathbb{R}^n:w\ge0\} rec ( conv ( B )) = {( w , 0 ) ∈ R × R n : w ≥ 0 }
The projection of conv ( B ) \operatorname{conv}(B) conv ( B ) z z z [ 0 , 1 ] n [0,1]^n [ 0 , 1 ] n 0 ≤ z i ≤ 1 0\le z_i\le1 0 ≤ z i ≤ 1 i ∈ [ n ] i\in[n] i ∈ [ n ] conv ( B ) \operatorname{conv}(B) conv ( B ) w w w
w ≥ 0 w\ge0 w ≥ 0 conv ( B ) \operatorname{conv}(B) conv ( B )
Proposition 4.2. Every nontrivial w w w w − α T z ≥ − β w-\alpha^\mathsf{T}z\ge-\beta w − α T z ≥ − β where α ≥ 0 \alpha\ge0 α ≥ 0 β > 0 \beta>0 β > 0 and, for all i ∈ [ n ] i\in[n] i ∈ [ n ] α i ≤ β \alpha_i\le\beta α i ≤ β
Proof. Write a valid inequality involving w w w γ w + c T z ≥ δ \gamma w+c^\mathsf{T}z\ge\delta γ w + c T z ≥ δ ( 1 , 0 ) (1,0) ( 1 , 0 ) conv ( B ) \operatorname{conv}(B) conv ( B ) γ ≥ 0 \gamma\ge0 γ ≥ 0 w w w γ > 0 \gamma>0 γ > 0 γ = 1 \gamma=1 γ = 1
The set B B B z ′ , z ∈ { 0 , 1 } n z',z\in\{0,1\}^n z ′ , z ∈ { 0 , 1 } n z ′ ≤ z z'\le z z ′ ≤ z ( w , z ) (w,z) ( w , z ) ( w , z ′ ) (w,z') ( w , z ′ ) wd ( S ( z ′ ) ) ≤ wd ( S ( z ) ) \operatorname{wd}(S(z'))\le\operatorname{wd}(S(z)) wd ( S ( z ′ )) ≤ wd ( S ( z )) c i > 0 c_i>0 c i > 0 i i i z i = 1 z_i = 1 z i = 1 c i ≤ 0 c_i \le0 c i ≤ 0 i i i α : = − c ≥ 0 \alpha:= -c \ge0 α := − c ≥ 0 β : = − δ \beta:= -\delta β := − δ
Validity at the empty support gives β ≥ 0 \beta\ge0 β ≥ 0 β = 0 \beta= 0 β = 0 − α i ≥ 0 -\alpha_i \ge0 − α i ≥ 0 α = 0 \alpha= 0 α = 0 w ≥ 0 w \ge0 w ≥ 0 β > 0 \beta> 0 β > 0 w − α T z ≥ − β w - \alpha^\mathsf{T}z \ge-\beta w − α T z ≥ − β ( 0 , e i ) (0,e_i) ( 0 , e i ) α i ≤ β \alpha_i \le\beta α i ≤ β
We state some properties of the function w d w_d w d
Proposition 4.3. The function w d w_d w d
(i) w d ( ∅ ) = 0 w_d(\varnothing) = 0 w d ( ∅ ) = 0 w d ( { i } ) = 0 w_d(\{i\}) = 0 w d ({ i }) = 0 i ∈ [ n ] i \in[n] i ∈ [ n ]
(ii) w d w_d w d monotone : if S ⊆ T S \subseteq T S ⊆ T w d ( S ) ≤ w d ( T ) w_d(S) \le w_d(T) w d ( S ) ≤ w d ( T )
(iii) If S , T ⊆ [ n ] S,T \subseteq[n] S , T ⊆ [ n ] S ∩ T ≠ ∅ S \cap T \ne\varnothing S ∩ T = ∅
w d ( S ∪ T ) + w d ( S ∩ T ) ≤ w d ( S ) + w d ( T ) . (5) w_d(S \cup T) + w_d(S \cap T) \le w_d(S) + w_d(T). \tag*{(5)} w d ( S ∪ T ) + w d ( S ∩ T ) ≤ w d ( S ) + w d ( T ) . (5) Proof. The first two properties follow directly from the definition. For the third, fix t ∈ [ d ] t \in[d] t ∈ [ d ] S ∩ T ≠ ∅ S \cap T \ne\varnothing S ∩ T = ∅
max i ∈ S ∪ T p t i + max i ∈ S ∩ T p t i ≤ max i ∈ S p t i + max i ∈ T p t i . \max_{i \in S \cup T} p_t^i + \max_{i \in S \cap T} p_t^i \le\max_{i \in S} p_t^i + \max_{i \in T} p_t^i. i ∈ S ∪ T max p t i + i ∈ S ∩ T max p t i ≤ i ∈ S max p t i + i ∈ T max p t i . whereas
min i ∈ S ∪ T p t i + min i ∈ S ∩ T p t i ≥ min i ∈ S p t i + min i ∈ T p t i . \min_{i \in S \cup T} p_t^i + \min_{i \in S \cap T} p_t^i \ge\min_{i \in S} p_t^i + \min_{i \in T} p_t^i. i ∈ S ∪ T min p t i + i ∈ S ∩ T min p t i ≥ i ∈ S min p t i + i ∈ T min p t i . Subtracting the second inequality from the first gives the coordinate-wise version of (5). Summing over t ∈ [ d ] t \in[d] t ∈ [ d ]
Uncrossing and laminar structure
Fix a nontrivial facet w − α T z ≥ − β w - \alpha^\mathsf{T}z \ge-\beta w − α T z ≥ − β conv ( B ) \operatorname{conv}(B) conv ( B )
T ( α , β ) : = { S ⊆ [ n ] : w d ( S ) − α ( S ) = − β } . \mathcal{T}(\alpha,\beta) := \{S \subseteq[n] : w_d(S) - \alpha(S) = -\beta\}. T ( α , β ) := { S ⊆ [ n ] : w d ( S ) − α ( S ) = − β } . For a family A ⊆ 2 [ n ] \mathcal{A} \subseteq2^{[n]} A ⊆ 2 [ n ] A ^ : = { ( w d ( S ) , χ S ) : S ∈ A } \widehat{\mathcal{A}} := \{(w_d(S),\chi^S) : S \in\mathcal{A}\} A := {( w d ( S ) , χ S ) : S ∈ A } [14 ] . We state the lemmas here and provide the proofs in Appendix A for completeness.
Lemma 4.4. [Crossing lemma] If S , T ∈ T ( α , β ) S,T \in\mathcal{T}(\alpha,\beta) S , T ∈ T ( α , β ) S ∩ T ≠ ∅ S \cap T \ne\varnothing S ∩ T = ∅ S ∩ T ∈ T ( α , β ) S \cap T \in\mathcal{T}(\alpha,\beta) S ∩ T ∈ T ( α , β ) S ∪ T ∈ T ( α , β ) S \cup T \in\mathcal{T}(\alpha,\beta) S ∪ T ∈ T ( α , β ) ( w d ( S ) , χ S ) + ( w d ( T ) , χ T ) = ( w d ( S ∩ T ) , χ S ∩ T ) + ( w d ( S ∪ T ) , χ S ∪ T ) (w_d(S),\chi^S) + (w_d(T),\chi^T) = (w_d(S \cap T),\chi^{S\cap T}) + (w_d(S \cup T),\chi^{S\cup T}) ( w d ( S ) , χ S ) + ( w d ( T ) , χ T ) = ( w d ( S ∩ T ) , χ S ∩ T ) + ( w d ( S ∪ T ) , χ S ∪ T )
Two sets S , T ⊆ [ n ] S,T \subseteq[n] S , T ⊆ [ n ] compatible if S ⊆ T S \subseteq T S ⊆ T T ⊆ S T \subseteq S T ⊆ S S ∩ T = ∅ S \cap T = \varnothing S ∩ T = ∅ laminar if every pair of its members is compatible. Otherwise, S S S T T T cross .
Lemma 4.5. Let L \mathcal{L} L T ( α , β ) \mathcal{T}(\alpha,\beta) T ( α , β ) aff ( T ( α , β ) ^ ) = aff ( L ^ ) \operatorname{aff}(\widehat{\mathcal{T}(\alpha,\beta)}) = \operatorname{aff}(\widehat{\mathcal{L}}) aff ( T ( α , β ) ) = aff ( L )
Corollary 4.6. The family L \mathcal{L} L n + 1 n + 1 n + 1
w d ( S ) − α ( S ) = − β , S ∈ L , (6) w_d(S) - \alpha(S) = -\beta,\qquad S \in\mathcal{L}, \tag*{(6)} w d ( S ) − α ( S ) = − β , S ∈ L , (6) uniquely determine the coefficients ( α , β ) (\alpha,\beta) ( α , β )
Proof. The tight face of a facet of the full-dimensional set conv ( B ) ⊆ R n + 1 \operatorname{conv}(B) \subseteq\mathbb{R}^{n+1} conv ( B ) ⊆ R n + 1 n n n T ( α , β ) \mathcal{T}(\alpha,\beta) T ( α , β ) n + 1 n+1 n + 1 L ^ \widehat{\mathcal{L}} L
Associate with L \mathcal{L} L F = ( L , A ) \mathcal{F}=(\mathcal{L},\mathcal{A}) F = ( L , A ) S ∈ L S \in\mathcal{L} S ∈ L T ∈ L T \in\mathcal{L} T ∈ L T ⊊ S T \subsetneq S T ⊊ S L \mathcal{L} L T T T S S S L \mathcal{L} L L \mathcal{L} L ch ( S ) \operatorname{ch}(S) ch ( S ) S S S
Lemma 4.7. A node S ∈ L S \in\mathcal{L} S ∈ L F \mathcal{F} F S S S
Proof. A singleton has no nonempty proper tight subset, and hence is a leaf whenever it belongs to L \mathcal{L} L S S S v ∈ R n v \in\mathbb{R}^{n} v ∈ R n j ∈ S j \in S j ∈ S
v i = { 1 ∣ S ∣ , i ≠ j , i ∈ S , − ∣ S ∣ − 1 ∣ S ∣ , i = j , 0 , i ∉ S . v_i =
\begin{cases}
\frac{1}{|S|}, & i \ne j,\ i \in S,\\
-\frac{|S|-1}{|S|}, & i=j,\\
0, & i \notin S.
\end{cases} v i = ⎩ ⎨ ⎧ ∣ S ∣ 1 , − ∣ S ∣ ∣ S ∣ − 1 , 0 , i = j , i ∈ S , i = j , i ∈ / S . Define α ( ϵ ) = α + ϵ v \alpha^{(\epsilon)}=\alpha+\epsilon v α ( ϵ ) = α + ϵ v T ∈ L T \in\mathcal{L} T ∈ L T T T S S S T T T S S S T ∩ S = ∅ T \cap S=\varnothing T ∩ S = ∅
wd ( T ) − α ( ϵ ) ( T ) = wd ( T ) − α ( T ) = − β . \operatorname{wd}(T)-\alpha^{(\epsilon)}(T)=\operatorname{wd}(T)-\alpha(T)=-\beta. wd ( T ) − α ( ϵ ) ( T ) = wd ( T ) − α ( T ) = − β . If S ⊆ T S \subseteq T S ⊆ T
wd ( T ) − α ( ϵ ) ( T ) = wd ( T ) − α ( T ) − ϵ v ( T ) = wd ( T ) − α ( T ) = − β . \operatorname{wd}(T)-\alpha^{(\epsilon)}(T)=\operatorname{wd}(T)-\alpha(T)-\epsilon v(T)=\operatorname{wd}(T)-\alpha(T)=-\beta. wd ( T ) − α ( ϵ ) ( T ) = wd ( T ) − α ( T ) − ϵ v ( T ) = wd ( T ) − α ( T ) = − β . That is, there is another facet with coefficient α ( ϵ ) \alpha^{(\epsilon)} α ( ϵ ) β \beta β L \mathcal{L} L
Lemma 4.8. For i ∈ [ n ] i \in[n] i ∈ [ n ] { i } \{i\} { i } L \mathcal{L} L α i = β \alpha_i=\beta α i = β
Proof. The singleton is tight if and only if 0 − α i = − β 0-\alpha_i=-\beta 0 − α i = − β α i = β \alpha_i=\beta α i = β L \mathcal{L} L L \mathcal{L} L
Lemma 4.9. Every non-leaf node S ∈ L S \in\mathcal{L} S ∈ L ∣ S ∖ ch ( S ) ∣ ≤ 1 |S \setminus\operatorname{ch}(S)| \le1 ∣ S ∖ ch ( S ) ∣ ≤ 1
Proof. The proof follows the same analysis as Lemma 4.7. Let H : = S ∖ ch ( S ) H:=S \setminus\operatorname{ch}(S) H := S ∖ ch ( S ) ∣ H ∣ ≥ 2 |H| \ge2 ∣ H ∣ ≥ 2 v v v H H H v ( H ) = 0 v(H)=0 v ( H ) = 0 T ∈ L T \in\mathcal{L} T ∈ L H H H H H H T ⊊ S T \subsetneq S T ⊊ S T T T S S S H H H S ⊆ T S \subseteq T S ⊆ T H ⊆ T H \subseteq T H ⊆ T v ( T ) = 0 v(T)=0 v ( T ) = 0 T ∈ L T \in\mathcal{L} T ∈ L
Lemma 4.10. Every element of [ n ] [n] [ n ] F \mathcal{F} F
Proof. If some j ∈ [ n ] j \in[n] j ∈ [ n ] L \mathcal{L} L α \alpha α α + ϵ e j \alpha+\epsilon e_j α + ϵ e j
Sequential lifting
Fix β > 0 \beta> 0 β > 0 π = ( π 1 , … , π n ) \pi= (\pi_1,\ldots,\pi_n) π = ( π 1 , … , π n ) [ n ] [n] [ n ] A k : = { π 1 , … , π k } A_k := \{\pi_1,\ldots,\pi_k\} A k := { π 1 , … , π k } A 0 = ∅ A_0 = \varnothing A 0 = ∅ w ≥ − β w \ge-\beta w ≥ − β
α π k β , π : = min S ⊆ A k − 1 { wd ( S ∪ { π k } ) − α β , π ( S ) + β } , k = 1 , … , n . (7) \alpha_{\pi_k}^{\beta,\pi} := \min_{S \subseteq A_{k-1}} \left\{ \operatorname{wd}(S \cup\{\pi_k\}) - \alpha^{\beta,\pi}(S) + \beta\right\}, \qquad k = 1,\ldots,n. \tag*{(7)} α π k β , π := S ⊆ A k − 1 min { wd ( S ∪ { π k }) − α β , π ( S ) + β } , k = 1 , … , n . (7) For example, the coefficients of the first two variables indexed by the permutation π \pi π α π 1 β , π = β \alpha_{\pi_1}^{\beta,\pi} = \beta α π 1 β , π = β α π 2 β , π = min { β , ∣ p π 2 − p π 1 ∣ } \alpha_{\pi_2}^{\beta,\pi} = \min\{\beta, |p_{\pi_2} - p_{\pi_1}|\} α π 2 β , π = min { β , ∣ p π 2 − p π 1 ∣ }
We remark that (7) is a lifting optimization problem which is the key machinery to yield a valid inequality. Moreover, the lifting problem, after switching minimization to maximization, is exactly the Boxing Problem defined in Section 1 for which a polynomial-time algorithm is provided. In this section, we prove that all facets can be obtained via sequential lifting.
Fix an arbitrary facet w − α ˉ T z ≥ − β ˉ w - \bar{\alpha}^{\mathsf{T}}z \ge-\bar{\beta} w − α ˉ T z ≥ − β ˉ F ( α ˉ , β ˉ ) \mathcal{F}(\bar{\alpha},\bar{\beta}) F ( α ˉ , β ˉ ) T ( α ˉ , β ˉ ) \mathcal{T}(\bar{\alpha},\bar{\beta}) T ( α ˉ , β ˉ ) j ∈ [ n ] j \in[n] j ∈ [ n ] N ( j ) N(j) N ( j ) F ( α ˉ , β ˉ ) \mathcal{F}(\bar{\alpha},\bar{\beta}) F ( α ˉ , β ˉ ) j j j N ( j ) ∖ ch ( N ( j ) ) = { j } N(j) \setminus\operatorname{ch}(N(j)) = \{j\} N ( j ) ∖ ch ( N ( j )) = { j }
Definition 4.11. Fix a forest F ( α ˉ , β ˉ ) \mathcal{F}(\bar{\alpha},\bar{\beta}) F ( α ˉ , β ˉ ) w − α ˉ T z ≥ − β ˉ w - \bar{\alpha}^{\mathsf{T}}z \ge-\bar{\beta} w − α ˉ T z ≥ − β ˉ F ( α ˉ , β ˉ ) \mathcal{F}(\bar{\alpha},\bar{\beta}) F ( α ˉ , β ˉ ) π = ( π 1 , … , π n ) \pi= (\pi_1,\ldots,\pi_n) π = ( π 1 , … , π n ) j j j N ( j ) N(j) N ( j ) N ( j ) N(j) N ( j ) j j j π \pi π
Theorem 4.12. Let w − α ˉ T z ≥ − β ˉ w - \bar{\alpha}^{\mathsf{T}}z \ge-\bar{\beta} w − α ˉ T z ≥ − β ˉ conv ( B ) \operatorname{conv}(B) conv ( B ) π \pi π F ( α ˉ , β ˉ ) \mathcal{F}(\bar{\alpha},\bar{\beta}) F ( α ˉ , β ˉ ) w ≥ − β ˉ w \ge-\bar{\beta} w ≥ − β ˉ π \pi π α ˉ \bar{\alpha} α ˉ
Proof. We induct on the lifting order. Suppose j = π 1 j = \pi_1 j = π 1 j j j α ˉ j = β ˉ \bar{\alpha}_j = \bar{\beta} α ˉ j = β ˉ
Now suppose the variables in A k − 1 = { π 1 , … , π k − 1 } A_{k-1} = \{\pi_1,\ldots,\pi_{k-1}\} A k − 1 = { π 1 , … , π k − 1 } j : = π k j := \pi_k j := π k R ⊆ A k − 1 R \subseteq A_{k-1} R ⊆ A k − 1 R ∪ { j } R \cup\{j\} R ∪ { j }
wd ( R ∪ { j } ) − α ˉ ( R ) − α ˉ j ≥ − β ˉ ⟺ wd ( R ∪ { j } ) − α ˉ ( R ) + β ˉ ≥ α ˉ j . \operatorname{wd}(R \cup\{j\}) - \bar{\alpha}(R) - \bar{\alpha}_j \ge-\bar{\beta}
\Longleftrightarrow
\operatorname{wd}(R \cup\{j\}) - \bar{\alpha}(R) + \bar{\beta} \ge\bar{\alpha}_j. wd ( R ∪ { j }) − α ˉ ( R ) − α ˉ j ≥ − β ˉ ⟺ wd ( R ∪ { j }) − α ˉ ( R ) + β ˉ ≥ α ˉ j . Thus every feasible solution of the lifting problem has value at least α ˉ j \bar{\alpha}_j α ˉ j
Conversely, consider N ( j ) N(j) N ( j ) j j j ch ( N ( j ) ) \operatorname{ch}(N(j)) ch ( N ( j )) N ( j ) = ch ( N ( j ) ) ∪ { j } N(j) = \operatorname{ch}(N(j)) \cup\{j\} N ( j ) = ch ( N ( j )) ∪ { j }
wd ( N ( j ) ) − α ˉ ( ch ( N ( j ) ) ) + β ˉ = α ˉ j . (8) \operatorname{wd}(N(j)) - \bar{\alpha}(\operatorname{ch}(N(j))) + \bar{\beta} = \bar{\alpha}_j. \tag*{(8)} wd ( N ( j )) − α ˉ ( ch ( N ( j ))) + β ˉ = α ˉ j . (8) Hence ch ( N ( j ) ) ⊆ A k − 1 \operatorname{ch}(N(j)) \subseteq A_{k-1} ch ( N ( j )) ⊆ A k − 1 α ˉ j \bar{\alpha}_j α ˉ j α ˉ j \bar{\alpha}_j α ˉ j
We want to emphasize that Theorem 4.12 is dimension-independent. However, to obtain all facets using Theorem 4.12, we need to enumerate all right-hand side β \beta β
The One-dimensional Boxing Set
Throughout this section, d = 1 d = 1 d = 1 p 1 < p 2 < ⋯ < p n p^1 < p^2 < \cdots< p^n p 1 < p 2 < ⋯ < p n w w w w − α ⊤ z ≥ − β w-\alpha^{\top}z\ge-\beta w − α ⊤ z ≥ − β α ≥ 0 \alpha\ge0 α ≥ 0 β > 0 \beta>0 β > 0 S ⊆ [ n ] S\subseteq[n] S ⊆ [ n ] u ( S ) u(S) u ( S ) ℓ ( S ) \ell(S) ℓ ( S ) max i ∈ S p i \max_{i\in S}p^i max i ∈ S p i min i ∈ S p i \min_{i\in S}p^i min i ∈ S p i wd ( S ) = u ( S ) − ℓ ( S ) \operatorname{wd}(S)=u(S)-\ell(S) wd ( S ) = u ( S ) − ℓ ( S )
The laminar-family results of Section 4 hold without any assumption on the dimension. In one dimension, the geometry of the laminar forest becomes substantially more explicit, where disjoint tight sets can be ordered from left to right. Thus, the ordering of the points allows us to turn this structure into a particularly simple sequential-lifting description of all facets.
The right-hand side of a one-dimensional facet
We now connect the lifting construction to the laminar forest of Section 4.
Fix a nontrivial facet w − α ⊤ z ≥ − β w-\alpha^{\top}z\ge-\beta w − α ⊤ z ≥ − β L \mathcal{L} L S , T ⊆ [ n ] S,T\subseteq[n] S , T ⊆ [ n ] S ≺ T S\prec T S ≺ T u ( S ) < ℓ ( T ) u(S)<\ell(T) u ( S ) < ℓ ( T )
gap ( S , T ) : = min j ∈ T p j − max i ∈ S p i . \operatorname{gap}(S,T):=\min_{j\in T}p^j-\max_{i\in S}p^i. gap ( S , T ) := j ∈ T min p j − i ∈ S max p i . Lemma 5.1. Let S , T ∈ L S,T\in\mathcal{L} S , T ∈ L [ ℓ ( S ) , u ( S ) ] [\ell(S),u(S)] [ ℓ ( S ) , u ( S )] [ ℓ ( T ) , u ( T ) ] [\ell(T),u(T)] [ ℓ ( T ) , u ( T )] S ≺ T S\prec T S ≺ T gap ( S , T ) ≥ β \operatorname{gap}(S,T)\ge\beta gap ( S , T ) ≥ β S ∪ T S\cup T S ∪ T gap ( S , T ) = β \operatorname{gap}(S,T)=\beta gap ( S , T ) = β
Proof. Since S S S T T T α ( S ) = wd ( S ) + β \alpha(S)=\operatorname{wd}(S)+\beta α ( S ) = wd ( S ) + β α ( T ) = wd ( T ) + β \alpha(T)=\operatorname{wd}(T)+\beta α ( T ) = wd ( T ) + β S ∪ T S\cup T S ∪ T
wd ( S ∪ T ) − wd ( S ) − wd ( T ) ≥ β . (9) \operatorname{wd}(S\cup T)-\operatorname{wd}(S)-\operatorname{wd}(T)\ge\beta. \tag*{(9)} wd ( S ∪ T ) − wd ( S ) − wd ( T ) ≥ β . (9) If their coordinate intervals overlapped, the left-hand side of (9) would be nonpositive, a contradiction. Hence the intervals are disjoint.
Assume S ≺ T S\prec T S ≺ T wd ( S ∪ T ) = wd ( S ) + wd ( T ) + gap ( S , T ) \operatorname{wd}(S\cup T)=\operatorname{wd}(S)+\operatorname{wd}(T)+\operatorname{gap}(S,T) wd ( S ∪ T ) = wd ( S ) + wd ( T ) + gap ( S , T ) gap ( S , T ) ≥ β \operatorname{gap}(S,T)\ge\beta gap ( S , T ) ≥ β S ∪ T S\cup T S ∪ T gap ( S , T ) = β \operatorname{gap}(S,T)=\beta gap ( S , T ) = β
The next result is the only place where the one-dimensional geometry is needed to identify the possible right-hand sides.
Lemma 5.2. For every nontrivial w w w a < b a<b a < b β = p b − p a \beta=p^b-p^a β = p b − p a
Proof. For a node S ∈ L S\in\mathcal{L} S ∈ L ch ( S ) \operatorname{ch}(S) ch ( S ) ∣ S ∖ ch ( S ) ∣ ≤ 1 |S\setminus\operatorname{ch}(S)|\le1 ∣ S ∖ ch ( S ) ∣ ≤ 1 [ n ] [n] [ n ]
Thus exactly n n n L \mathcal{L} L n + 1 n+1 n + 1 S S S S 1 ≺ S 2 ≺ ⋯ ≺ S k S_1\prec S_2\prec\cdots\prec S_k S 1 ≺ S 2 ≺ ⋯ ≺ S k k ≥ 2 k\ge2 k ≥ 2 S = S 1 ∪ ⋯ ∪ S k S=S_1\cup\cdots\cup S_k S = S 1 ∪ ⋯ ∪ S k
wd ( S ) = ∑ q = 1 k wd ( S q ) + ∑ q = 1 k − 1 gap ( S q , S q + 1 ) . \operatorname{wd}(S)=\sum_{q=1}^{k}\operatorname{wd}(S_q)+\sum_{q=1}^{k-1}\operatorname{gap}(S_q,S_{q+1}). wd ( S ) = q = 1 ∑ k wd ( S q ) + q = 1 ∑ k − 1 gap ( S q , S q + 1 ) . Using tightness of S S S S q S_q S q
∑ q = 1 k − 1 gap ( S q , S q + 1 ) = ( k − 1 ) β . \sum_{q=1}^{k-1}\operatorname{gap}(S_q,S_{q+1})=(k-1)\beta. q = 1 ∑ k − 1 gap ( S q , S q + 1 ) = ( k − 1 ) β . By Lemma 5.1, every term on the left-hand side is at least β \beta β β \beta β a , b ∈ [ n ] a,b\in[n] a , b ∈ [ n ] p b − p a = β p^b-p^a=\beta p b − p a = β q ∈ [ k − 1 ] q\in[k-1] q ∈ [ k − 1 ]
a ∈ arg max { p i : i ∈ S q } , b ∈ arg min { p i : i ∈ S q + 1 } . a\in\arg\max\{p^i:i\in S_q\},\qquad b\in\arg\min\{p^i:i\in S_{q+1}\}. a ∈ arg max { p i : i ∈ S q } , b ∈ arg min { p i : i ∈ S q + 1 } . Then p b − p a = gap ( S q , S q + 1 ) = β p^b-p^a=\operatorname{gap}(S_q,S_{q+1})=\beta p b − p a = gap ( S q , S q + 1 ) = β
Thus, we define the finite set of candidate right-hand sides using B : = { p j − p i : 1 ≤ i < j ≤ n } \mathcal{B}:=\{p^j-p^i:1\le i<j\le n\} B := { p j − p i : 1 ≤ i < j ≤ n }
Facet description
§ 5.1 shows that the right-hand side of every nontrivial one-dimensional facet belongs to the finite set B \mathcal{B} B
The nearest-neighbor lifting rule
Fix β > 0 \beta>0 β > 0 π = ( π 1 , … , π n ) \pi=(\pi_1,\ldots,\pi_n) π = ( π 1 , … , π n ) [ n ] [n] [ n ] k ∈ [ n ] k\in[n] k ∈ [ n ] A k : = { π 1 , … , π k } A_k:=\{\pi_1,\ldots,\pi_k\} A k := { π 1 , … , π k } A 0 : = ∅ A_0:=\varnothing A 0 := ∅ k ≥ 2 k\ge2 k ≥ 2 j : = π k j:=\pi_k j := π k p j p^j p j
L k : = max { i ∈ A k − 1 : i < π k } , R k : = min { i ∈ A k − 1 : i > π k } , L_k:=\max\{i\in A_{k-1}:i<\pi_k\},\qquad R_k:=\min\{i\in A_{k-1}:i>\pi_k\}, L k := max { i ∈ A k − 1 : i < π k } , R k := min { i ∈ A k − 1 : i > π k } , whenever the corresponding sets are nonempty. We use the notation ( x ) + : = max { x , 0 } (x)_+:=\max\{x,0\} ( x ) + := max { x , 0 } α β , π ∈ R + n \alpha^{\beta,\pi}\in\mathbb{R}^n_+ α β , π ∈ R + n
α π k β , π : = { β if neither L k nor R k exists , min { β , p R k − p π k } if L k does not exist , min { β , p π k − p L k } if R k does not exist , min { β , p π k − p L k , p R k − p π k , ( p R k − p L k − β ) + } otherwise . \alpha_{\pi_k}^{\beta,\pi}:=
\begin{cases}
\beta& \text{if neither $L_k$ nor $R_k$ exists},\\
\min\{\beta,p^{R_k}-p^{\pi_k}\} & \text{if $L_k$ does not exist},\\
\min\{\beta,p^{\pi_k}-p^{L_k}\} & \text{if $R_k$ does not exist},\\
\min\{\beta,p^{\pi_k}-p^{L_k},p^{R_k}-p^{\pi_k},(p^{R_k}-p^{L_k}-\beta)_+\} & \text{otherwise}.
\end{cases} α π k β , π := ⎩ ⎨ ⎧ β min { β , p R k − p π k } min { β , p π k − p L k } min { β , p π k − p L k , p R k − p π k , ( p R k − p L k − β ) + } if neither L k nor R k exists , if L k does not exist , if R k does not exist , otherwise . (Nearest Neighbor Lifting Rule)
Thus the coefficient of a newly inserted point depends only on its two nearest previously inserted neighbors. We view the lifting process as building the laminar forest of the underlying facet from bottom up. The four quantities in (Nearest Neighbor Lifting Rule) have a direct interpretation: β \beta β p R k − p L k − β p^{R_k}-p^{L_k}-\beta p R k − p L k − β p R k − p L k ≤ β p^{R_k}-p^{L_k}\le\beta p R k − p L k ≤ β
Example 5.3. Consider the ten points ( p 1 , … , p 10 ) = ( 0 , 1 , 2 , 4 , 6 , 7 , 9 , 11.5 , 13 , 15.5 ) (p^1,\ldots,p^{10})=(0,1,2,4,6,7,9,11.5,13,15.5) ( p 1 , … , p 10 ) = ( 0 , 1 , 2 , 4 , 6 , 7 , 9 , 11.5 , 13 , 15.5 ) β = 4 \beta=4 β = 4 ( 2 , 5 , 8 , 1 , 3 , 6 , 9 , 10 ) (2,5,8,1,3,6,9,10) ( 2 , 5 , 8 , 1 , 3 , 6 , 9 , 10 ) w − z 1 − 4 z 2 − z 3 − 4 z 5 − z 6 − 4 z 8 − 3 2 z 9 − 5 2 z 10 ≥ − 4 w-z_1-4z_2-z_3-4z_5-z_6-4z_8-\frac{3}{2}z_9-\frac{5}{2}z_{10}\ge-4 w − z 1 − 4 z 2 − z 3 − 4 z 5 − z 6 − 4 z 8 − 2 3 z 9 − 2 5 z 10 ≥ − 4 L k = 6 L_k=6 L k = 6 R k = 8 R_k=8 R k = 8
α 7 = min { β , p 7 − p 6 , p 8 − p 7 , ( p 8 − p 6 − β ) + } = min { 4 , 2 , 2.5 , 0.5 } = 1 2 . \alpha_7=\min\{\beta,p^7-p^6,p^8-p^7,(p^8-p^6-\beta)_+\}=\min\{4,2,2.5,0.5\}=\frac{1}{2}. α 7 = min { β , p 7 − p 6 , p 8 − p 7 , ( p 8 − p 6 − β ) + } = min { 4 , 2 , 2.5 , 0.5 } = 2 1 . Finally, lift variable 4. Its nearest previously lifted neighbors are L k = 3 L_k=3 L k = 3 R k = 5 R_k=5 R k = 5 p 5 − p 3 = β p^5-p^3=\beta p 5 − p 3 = β α 4 = min { 4 , 2 , 2 , ( 6 − 2 − 4 ) + } = 0 \alpha_4=\min\{4,2,2,(6-2-4)_+\}=0 α 4 = min { 4 , 2 , 2 , ( 6 − 2 − 4 ) + } = 0
Lemma 5.4. For every β > 0 \beta> 0 β > 0 π \pi π α π k β , π \alpha^{\beta,\pi}_{\pi_k} α π k β , π
min S ⊆ A k − 1 { wd ( S ∪ { π k } ) − α β , π ( S ) + β } . (10) \min_{S \subseteq A_{k-1}} \left\{ \operatorname{wd}(S \cup\{\pi_k\}) - \alpha^{\beta,\pi}(S) + \beta\right\}. \tag*{(10)} S ⊆ A k − 1 min { wd ( S ∪ { π k }) − α β , π ( S ) + β } . (10) Consequently, w − ( α β , π ) T z ≥ − β w - (\alpha^{\beta,\pi})^{\mathsf{T}}z \ge-\beta w − ( α β , π ) T z ≥ − β B B B
Proof. For any integer k ≥ 1 k \ge1 k ≥ 1 A k A_k A k β \beta β β \beta β k k k β \beta β C C C
wd ( C ) − α β , π ( C ) = − β . (11) \operatorname{wd}(C) - \alpha^{\beta,\pi}(C) = -\beta. \tag*{(11)} wd ( C ) − α β , π ( C ) = − β . (11) This is immediate for A 1 A_1 A 1 j : = π k j := \pi_k j := π k A k − 1 A_{k-1} A k − 1 S ⊆ A k − 1 S \subseteq A_{k-1} S ⊆ A k − 1 S = ∅ S = \varnothing S = ∅ (10) equals β \beta β S S S j j j wd ( S ) − α β , π ( S ) ≥ − β \operatorname{wd}(S) - \alpha^{\beta,\pi}(S) \ge-\beta wd ( S ) − α β , π ( S ) ≥ − β wd ( S ∪ { j } ) − α β , π ( S ) + β ≥ p j − u ( S ) ≥ p j − p L k \operatorname{wd}(S \cup\{j\}) - \alpha^{\beta,\pi}(S) + \beta\ge p^j - u(S) \ge p^j - p^{L_k} wd ( S ∪ { j }) − α β , π ( S ) + β ≥ p j − u ( S ) ≥ p j − p L k p R k − p j p^{R_k} - p^j p R k − p j S S S S S S j j j S − S^- S − S + S^+ S + j j j
wd ( S ∪ { j } ) = wd ( S − ) + wd ( S + ) + gap ( S − , S + ) . \operatorname{wd}(S \cup\{j\}) = \operatorname{wd}(S^-) + \operatorname{wd}(S^+) + \operatorname{gap}(S^-, S^+). wd ( S ∪ { j }) = wd ( S − ) + wd ( S + ) + gap ( S − , S + ) . Using validity on S − S^- S − S + S^+ S +
wd ( S ∪ { j } ) − α β , π ( S ) + β ≥ gap ( S − , S + ) − β ≥ ( p R k − p L k − β ) + . \operatorname{wd}(S \cup\{j\}) - \alpha^{\beta,\pi}(S) + \beta\ge\operatorname{gap}(S^-, S^+) - \beta\ge(p^{R_k} - p^{L_k} - \beta)_+. wd ( S ∪ { j }) − α β , π ( S ) + β ≥ gap ( S − , S + ) − β ≥ ( p R k − p L k − β ) + . The first inequality is because adding j j j S S S wd ( S ) \operatorname{wd}(S) wd ( S )
Thus every feasible S S S β \beta β S = ∅ S = \varnothing S = ∅ p π k − p L k p^{\pi_k} - p^{L_k} p π k − p L k β \beta β L k L_k L k L k L_k L k R k R_k R k p R k − p L k − β p^{R_k} - p^{L_k} - \beta p R k − p L k − β
This case analysis also shows that after j j j β \beta β (11) . This completes the induction. □
Generating facets from β \beta β
We now give a blockwise description of the facets generated by the one-dimensional lifting rule.
Fix β ∈ B \beta\in\mathcal{B} β ∈ B b 1 < b 2 < ⋯ < b m b_1 < b_2 < \cdots< b_m b 1 < b 2 < ⋯ < b m p b t + 1 − p b t ≥ β p^{b_{t+1}} - p^{b_t} \ge\beta p b t + 1 − p b t ≥ β t = 1 , … , m − 1 t = 1, \ldots, m - 1 t = 1 , … , m − 1 b 1 , … , b m b_1, \ldots, b_m b 1 , … , b m β \beta β
[ 1 , b 1 ] , [ b 1 , b 2 ] , … , [ b m − 1 , b m ] , [ b m , n ] . [1,b_1],\ [b_1,b_2],\ \ldots,\ [b_{m-1},b_m],\ [b_m,n]. [ 1 , b 1 ] , [ b 1 , b 2 ] , … , [ b m − 1 , b m ] , [ b m , n ] . Adjacent intervals share one β \beta β [ b t , b t + 1 ] [b_t,b_{t+1}] [ b t , b t + 1 ] [ 1 , b 1 ] [1,b_1] [ 1 , b 1 ] [ b m , n ] [b_m,n] [ b m , n ]
The main idea is to describe the facet coefficients within each interval through chains (subset) of points. In an internal block , two chains grow inward from the two β \beta β merger , giving rise to a separated block or a merged block, respectively. In an exterior block, only one chain grows outward from its β \beta β
We call an interval a β \beta β
Internal blocks. Consider interval I t = [ b t , b t + 1 ] I_t=[b_t,b_{t+1}] I t = [ b t , b t + 1 ] t = 1 , … , m − 1 t=1,\ldots,m-1 t = 1 , … , m − 1 I t I_t I t
b t = r 0 t < r 1 t < ⋯ < r s t t = c t < d t = ℓ 0 t < ℓ 1 t < ⋯ < ℓ u t t = b t + 1 b_t=r^t_0<r^t_1<\cdots<r^t_{s_t}=c_t<d_t=\ell^t_0<\ell^t_1<\cdots<\ell^t_{u_t}=b_{t+1} b t = r 0 t < r 1 t < ⋯ < r s t t = c t < d t = ℓ 0 t < ℓ 1 t < ⋯ < ℓ u t t = b t + 1 satisfying
p r h t − p r h − 1 t < β , h = 1 , … , s t , p ℓ h t − p ℓ h − 1 t < β , h = 1 , … , u t . p^{r^t_h}-p^{r^t_{h-1}}<\beta,\quad h=1,\ldots,s_t,\qquad p^{\ell^t_h}-p^{\ell^t_{h-1}}<\beta,\quad h=1,\ldots,u_t. p r h t − p r h − 1 t < β , h = 1 , … , s t , p ℓ h t − p ℓ h − 1 t < β , h = 1 , … , u t . For a fixed pair of chains satisfying the above conditions, we distinguish the following two configurations of the chains. If neither configurations hold, the chosen chains are not admissible for an internal block.
Separated block. The block is separated if either
p d t − p c t = β , p^{d_t}-p^{c_t}=\beta, p d t − p c t = β , or
d t = c t + 1 and p d t − p c t > β . d_t=c_t+1\qquad\text{and}\qquad p^{d_t}-p^{c_t}>\beta. d t = c t + 1 and p d t − p c t > β . Its coefficients are
α i = { p r h t − p r h − 1 t , i = r h t , h = 1 , … , s t , p ℓ h + 1 t − p ℓ h t , i = ℓ h t , h = 0 , … , u t − 1 , β i = b t or i = b t + 1 , 0 , otherwise in ( b t , b t + 1 ) . (12) \alpha_i=
\begin{cases}
p^{r^t_h}-p^{r^t_{h-1}}, & i=r^t_h,\quad h=1,\ldots,s_t,\\
p^{\ell^t_{h+1}}-p^{\ell^t_h}, & i=\ell^t_h,\quad h=0,\ldots,u_t-1,\\
\beta& i=b_t\text{ or }i=b_{t+1},\\
0, & \text{otherwise in }(b_t,b_{t+1}).
\end{cases} \tag*{(12)} α i = ⎩ ⎨ ⎧ p r h t − p r h − 1 t , p ℓ h + 1 t − p ℓ h t , β 0 , i = r h t , h = 1 , … , s t , i = ℓ h t , h = 0 , … , u t − 1 , i = b t or i = b t + 1 , otherwise in ( b t , b t + 1 ) . (12) Merged block. The block is merged if there exists an index c t < μ t < d t c_t<\mu_t<d_t c t < μ t < d t
p μ t − p c t < β , p d t − p μ t < β , p d t − p c t > β . p^{\mu_t}-p^{c_t}<\beta,\qquad p^{d_t}-p^{\mu_t}<\beta,\qquad p^{d_t}-p^{c_t}>\beta. p μ t − p c t < β , p d t − p μ t < β , p d t − p c t > β . The index μ t \mu_t μ t merger of the block. Its coefficients are
α i = { p r h t − p r h − 1 t , i = r h t , h = 1 , … , s t , p ℓ h + 1 t − p ℓ h t , i = ℓ h t , h = 0 , … , u t − 1 , p d t − p c t − β , i = μ t , β i = b t or i = b t + 1 , 0 , otherwise in ( b t , b t + 1 ) . (13) \alpha_i=
\begin{cases}
p^{r^t_h}-p^{r^t_{h-1}}, & i=r^t_h,\quad h=1,\ldots,s_t,\\
p^{\ell^t_{h+1}}-p^{\ell^t_h}, & i=\ell^t_h,\quad h=0,\ldots,u_t-1,\\
p^{d_t}-p^{c_t}-\beta, & i=\mu_t,\\
\beta& i=b_t\text{ or }i=b_{t+1},\\
0, & \text{otherwise in }(b_t,b_{t+1}).
\end{cases} \tag*{(13)} α i = ⎩ ⎨ ⎧ p r h t − p r h − 1 t , p ℓ h + 1 t − p ℓ h t , p d t − p c t − β , β 0 , i = r h t , h = 1 , … , s t , i = ℓ h t , h = 0 , … , u t − 1 , i = μ t , i = b t or i = b t + 1 , otherwise in ( b t , b t + 1 ) . (13) We call I t I_t I t β \beta β
Exterior blocks. The left exterior block [ 1 , b 1 ] [1,b_1] [ 1 , b 1 ] ℓ \ell ℓ 1 = ℓ 0 < ℓ 1 < ⋯ < ℓ s = b 1 1=\ell_0<\ell_1<\cdots<\ell_s=b_1 1 = ℓ 0 < ℓ 1 < ⋯ < ℓ s = b 1 p ℓ h + 1 − p ℓ h < β p^{\ell_{h+1}}-p^{\ell_h}<\beta p ℓ h + 1 − p ℓ h < β h = 0 , … , s − 1 h=0,\ldots,s-1 h = 0 , … , s − 1
α i = { p ℓ h + 1 − p ℓ h , i = ℓ h , h = 0 , … , s − 1 , β i = b 1 , 0 , otherwise in [ 1 , b 1 ) . (14) \alpha_i=
\begin{cases}
p^{\ell_{h+1}}-p^{\ell_h}, & i=\ell_h,\quad h=0,\ldots,s-1,\\
\beta& i=b_1,\\
0, & \text{otherwise in }[1,b_1).
\end{cases} \tag*{(14)} α i = ⎩ ⎨ ⎧ p ℓ h + 1 − p ℓ h , β 0 , i = ℓ h , h = 0 , … , s − 1 , i = b 1 , otherwise in [ 1 , b 1 ) . (14) Symmetrically, the right exterior block [ b m , n ] [b_m,n] [ b m , n ] r r r b m = r 0 < r 1 < ⋯ < r s = n b_m=r_0<r_1<\cdots<r_s=n b m = r 0 < r 1 < ⋯ < r s = n p r h − p r h − 1 < β p^{r_h}-p^{r_{h-1}}<\beta p r h − p r h − 1 < β h = 1 , … , s h=1,\ldots,s h = 1 , … , s
α i = { p r h − p r h − 1 , i = r h , h = 1 , … , s , β i = b m , 0 , otherwise in ( b m , n ] . (15) \alpha_i=
\begin{cases}
p^{r_h}-p^{r_{h-1}}, & i=r_h,\quad h=1,\ldots,s,\\
\beta& i=b_m,\\
0, & \text{otherwise in }(b_m,n].
\end{cases} \tag*{(15)} α i = ⎩ ⎨ ⎧ p r h − p r h − 1 , β 0 , i = r h , h = 1 , … , s , i = b m , otherwise in ( b m , n ] . (15) Remark 5.5. If an exterior endpoint, z 1 z_1 z 1 z n z_n z n β \beta β β \beta β
Definition 5.6 (admissible β \beta β β \beta β b 1 < ⋯ < b m b_1<\cdots<b_m b 1 < ⋯ < b m β \beta β admissible β \beta β if
m ≥ 2 m\ge2 m ≥ 2 p b t + 1 − p b t ≥ β p^{b_{t+1}}-p^{b_t}\ge\beta p b t + 1 − p b t ≥ β t = 1 , … , m − 1 t=1,\ldots,m-1 t = 1 , … , m − 1
every interval partitioned by the β \beta β β \beta β
at least one internal separated block satisfies p d t − p c t = β p^{d_t}-p^{c_t}=\beta p d t − p c t = β
Example 5.7. Let β = 4 \beta=4 β = 4
( p 1 , … , p 10 ) = ( 0 , 1 , 2 , 4 , 6 , 7 , 9 , 11.5 , 13 , 15.5 ) . (p^1,\ldots,p^{10})=(0,1,2,4,6,7,9,11.5,13,15.5). ( p 1 , … , p 10 ) = ( 0 , 1 , 2 , 4 , 6 , 7 , 9 , 11.5 , 13 , 15.5 ) . Choose the β \beta β b 1 = 2 b_1=2 b 1 = 2 b 2 = 5 b_2=5 b 2 = 5 b 3 = 8 b_3=8 b 3 = 8 p b 2 − p b 1 = 5 ≥ β p^{b_2}-p^{b_1}=5\ge\beta p b 2 − p b 1 = 5 ≥ β p b 3 − p b 2 = 5.5 ≥ β p^{b_3}-p^{b_2}=5.5\ge\beta p b 3 − p b 2 = 5.5 ≥ β [ 1 , 2 ] [1,2] [ 1 , 2 ] [ 2 , 5 ] [2,5] [ 2 , 5 ] [ 5 , 8 ] [5,8] [ 5 , 8 ] [ 8 , 10 ] [8,10] [ 8 , 10 ] admissible β \beta β , illustrated below.
Figure 3 (PDF p. 17).
The chains and their coefficients are as follows (starting from a β \beta β
Left exterior block [ 1 , 2 ] [1,2] [ 1 , 2 ] ℓ = ( 1 , 2 ) \ell=(1,2) ℓ = ( 1 , 2 ) α 1 = p 2 − p 1 = 1 \alpha_1=p^2-p^1=1 α 1 = p 2 − p 1 = 1
Separated block [ 2 , 5 ] [2,5] [ 2 , 5 ] r 1 = ( 2 , 3 ) r^1=(2,3) r 1 = ( 2 , 3 ) ℓ 1 = ( 5 ) \ell^1=(5) ℓ 1 = ( 5 ) c 1 = 3 c_1=3 c 1 = 3 d 1 = 5 d_1=5 d 1 = 5 p 3 − p 2 = 1 < β p^3-p^2=1<\beta p 3 − p 2 = 1 < β p d 1 − p c 1 = p 5 − p 3 = 4 = β p^{d_1}-p^{c_1}=p^5-p^3=4=\beta p d 1 − p c 1 = p 5 − p 3 = 4 = β α 3 = 1 \alpha_3=1 α 3 = 1 α 4 = 0 \alpha_4=0 α 4 = 0
Merged block [5 , 8 ] : Take r 2 = ( 5 , 6 ) r^2=(5,6) r 2 = ( 5 , 6 ) ℓ 2 = ( 8 ) \ell^2=(8) ℓ 2 = ( 8 ) c 2 = 6 c_2=6 c 2 = 6 d 2 = 8 d_2=8 d 2 = 8 μ 2 = 7 \mu_2=7 μ 2 = 7
p 7 − p 6 = 2 < β , p 8 − p 7 = 2.5 < β , p 8 − p 6 = 4.5 > β . p^7-p^6=2<\beta,\qquad p^8-p^7=2.5<\beta,\qquad p^8-p^6=4.5>\beta. p 7 − p 6 = 2 < β , p 8 − p 7 = 2.5 < β , p 8 − p 6 = 4.5 > β . Consequently, α 6 = p 6 − p 5 = 1 \alpha_6=p^6-p^5=1 α 6 = p 6 − p 5 = 1 α 7 = p 8 − p 6 − β = 1 2 \alpha_7=p^8-p^6-\beta=\frac{1}{2} α 7 = p 8 − p 6 − β = 2 1
Right exterior block [8 , 10 ] : The chain is r = ( 8 , 9 , 10 ) r=(8,9,10) r = ( 8 , 9 , 10 ) α 9 = p 9 − p 8 = 3 2 \alpha_9=p^9-p^8=\frac{3}{2} α 9 = p 9 − p 8 = 2 3 α 10 = p 10 − p 9 = 5 2 \alpha_{10}=p^{10}-p^9=\frac{5}{2} α 10 = p 10 − p 9 = 2 5
The three β \beta β α 2 = α 5 = α 8 = β = 4 \alpha_2=\alpha_5=\alpha_8=\beta=4 α 2 = α 5 = α 8 = β = 4
α = ( 1 , 4 , 1 , 0 , 4 , 1 , 1 2 , 4 , 3 2 , 5 2 ) . \alpha=(1,4,1,0,4,1,\tfrac{1}{2},4,\tfrac{3}{2},\tfrac{5}{2}). α = ( 1 , 4 , 1 , 0 , 4 , 1 , 2 1 , 4 , 2 3 , 2 5 ) . and the corresponding facet is w − z 1 − 4 z 2 − z 3 − 4 z 5 − z 6 − 1 2 z 7 − 4 z 8 − 3 2 z 9 − 5 2 z 10 ≥ − 4 w-z_1-4z_2-z_3-4z_5-z_6-\frac{1}{2}z_7-4z_8-\frac{3}{2}z_9-\frac{5}{2}z_{10}\ge-4 w − z 1 − 4 z 2 − z 3 − 4 z 5 − z 6 − 2 1 z 7 − 4 z 8 − 2 3 z 9 − 2 5 z 10 ≥ − 4 [ 2 , 5 ] [2,5] [ 2 , 5 ] p 5 − p 3 = β p^5-p^3=\beta p 5 − p 3 = β β \beta β conv ( B ) \operatorname{conv}(B) conv ( B )
Lemma 5.8. Let I q = [ b q , b q + 1 ] I_q=[b_q,b_{q+1}] I q = [ b q , b q + 1 ] internal separated block with p d q − p c q = β p^{d_q}-p^{c_q}=\beta p d q − p c q = β w − ∑ i ∈ I q α i z i ≥ − β w-\sum_{i\in I_q}\alpha_i z_i\ge-\beta w − ∑ i ∈ I q α i z i ≥ − β conv ( B [ I q ] ) \operatorname{conv}(B[I_q]) conv ( B [ I q ])
Proof. Let r r r ℓ \ell ℓ b q = r 0 < ⋯ < r s = c q < d q = ℓ 0 < ⋯ < ℓ u = b q + 1 b_q=r_0<\cdots<r_s=c_q<d_q=\ell_0<\cdots<\ell_u=b_{q+1} b q = r 0 < ⋯ < r s = c q < d q = ℓ 0 < ⋯ < ℓ u = b q + 1 h = 0 , … , s h=0,\ldots,s h = 0 , … , s { r 0 , … , r h } \{r_0,\ldots,r_h\} { r 0 , … , r h }
∑ v = 0 h α r v = β + p r h − p b q = β + wd ( { r 0 , … , r h } ) . \sum_{v=0}^{h}\alpha_{r_v}=\beta+p^{r_h}-p^{b_q}=\beta+\operatorname{wd}(\{r_0,\ldots,r_h\}). v = 0 ∑ h α r v = β + p r h − p b q = β + wd ({ r 0 , … , r h }) . Similarly, { ℓ h , … , ℓ u } \{\ell_h,\ldots,\ell_u\} { ℓ h , … , ℓ u } h = 0 , … , u h=0,\ldots,u h = 0 , … , u p d q − p c q = β p^{d_q}-p^{c_q}=\beta p d q − p c q = β
These s + u + 3 s+u+3 s + u + 3 i ∈ I q i\in I_q i ∈ I q p i p^i p i c q c_q c q d q d_q d q i i i e i e_i e i ∣ I q ∣ + 1 |I_q|+1 ∣ I q ∣ + 1
Corollary 5.9. Let I I I β \beta β β \beta β w − ∑ i ∈ I α i z i ≥ − β w-\sum_{i\in I}\alpha_i z_i\ge-\beta w − ∑ i ∈ I α i z i ≥ − β α i \alpha_i α i
Thus every non-anchor internal β \beta β β \beta β β \beta β β \beta β β \beta β β \beta β
Proposition 5.10. The coefficient vector α \alpha α β \beta β β \beta β
Proof. Since every chain gap is strictly less than β \beta β β \beta β β \beta β α i = β \alpha_i=\beta α i = β
Fix an internal block [ b t , b t + 1 ] [b_t,b_{t+1}] [ b t , b t + 1 ] r 0 = b t r_0=b_t r 0 = b t r h r_h r h α r h = p r h − p r h − 1 \alpha_{r_h}=p^{r_h}-p^{r_{h-1}} α r h = p r h − p r h − 1 β ≤ p d t − p c t \beta\le p^{d_t}-p^{c_t} β ≤ p d t − p c t μ t \mu_t μ t α μ t = p d t − p c t − β < p μ t − p c t \alpha_{\mu_t}=p^{d_t}-p^{c_t}-\beta<p^{\mu_t}-p^{c_t} α μ t = p d t − p c t − β < p μ t − p c t b t + 1 b_{t+1} b t + 1 β \beta β
Algorithm 1 One-dimensional facet generation
Require: Distinct coordinates p 1 < ⋯ < p n p^1<\cdots<p^n p 1 < ⋯ < p n
for each distinct β ∈ B \beta\in\mathbb{B} β ∈ B do
for each admissible β \beta β do
Set α b t ← β \alpha_{b_t}\leftarrow\beta α b t ← β β \beta β b t b_t b t
for each internal β \beta β I t I_t I t do
if I t I_t I t then
Assign its coefficients using (12) .
else
Assign its coefficients using (13) .
end if
end for
Assign the two exterior-block coefficients using (14) and (15) .
Output w − α ⊤ z ≥ − β w-\alpha^\top z\ge-\beta w − α ⊤ z ≥ − β
end for
end for
Theorem 5.11. Every inequality output by Algorithm 1 is facet-defining for conv ( B ) \operatorname{conv}(B) conv ( B )
Proof. By Definition 5.6, at least one internal block has p d t − p c t = β p^{d_t}-p^{c_t}=\beta p d t − p c t = β
Consider the following order for the remaining variables. First add the remaining β \beta β β \beta β
The Nearest Neighbor Lifting Rule shows that the β \beta β β \beta β β \beta β p d t − p c t − β p^{d_t}-p^{c_t}-\beta p d t − p c t − β β \beta β conv ( B ) \operatorname{conv}(B) conv ( B )
Complete convex hull description
For this section, we fix an arbitrary nontrivial facet w − α ⊤ z ≥ − β w-\alpha^{\top}z\ge-\beta w − α ⊤ z ≥ − β conv ( B ) \operatorname{conv}(B) conv ( B ) L \mathcal{L} L F \mathcal{F} F F \mathcal{F} F F \mathcal{F} F L \mathcal{L} L L \mathcal{L} L F \mathcal{F} F F \mathcal{F} F
Structure of F \mathcal{F} F
The following proposition gives a concrete structure on F \mathcal{F} F
Proposition 5.12 (One-dimensional node classification). Every node S ′ ∈ F S' \in\mathcal{F} S ′ ∈ F
Type 1. S ′ = { j } S'=\{j\} S ′ = { j } α j = β \alpha_j=\beta α j = β
Type 2. S ′ = S ∪ { j } S'=S\cup\{j\} S ′ = S ∪ { j } S S S S ′ S' S ′ α j \alpha_j α j
Type 3. S ′ = S 1 ∪ S 2 ∪ { j } S'=S_1\cup S_2\cup\{j\} S ′ = S 1 ∪ S 2 ∪ { j } S 1 ∈ F S_1\in\mathcal{F} S 1 ∈ F S 2 ∈ F S_2\in\mathcal{F} S 2 ∈ F S ′ S' S ′ S 1 ≺ { j } ≺ S 2 S_1\prec\{j\}\prec S_2 S 1 ≺ { j } ≺ S 2 α j = gap ( S 1 , S 2 ) − β \alpha_j=\operatorname{gap}(S_1,S_2)-\beta α j = gap ( S 1 , S 2 ) − β
Type 4. S ′ = S 1 ∪ S 2 S'=S_1\cup S_2 S ′ = S 1 ∪ S 2 S 1 ∈ F S_1\in\mathcal{F} S 1 ∈ F S 2 ∈ F S_2\in\mathcal{F} S 2 ∈ F S ′ S' S ′ S 1 ≺ S 2 S_1\prec S_2 S 1 ≺ S 2 gap ( S 1 , S 2 ) = β \operatorname{gap}(S_1,S_2)=\beta gap ( S 1 , S 2 ) = β
We prove the Proposition assuming Lemma 5.14 to Lemma 5.16. Proofs of these lemmas are presented in Appendix B.
Example 5.13. Consider the points ( p 1 , … , p 10 ) = ( 0 , 1 , 2 , 4 , 6 , 7 , 9 , 11.5 , 13 , 15.5 ) (p^1,\ldots,p^{10})=(0,1,2,4,6,7,9,11.5,13,15.5) ( p 1 , … , p 10 ) = ( 0 , 1 , 2 , 4 , 6 , 7 , 9 , 11.5 , 13 , 15.5 ) w − z 1 − 4 z 2 − z 3 − 4 z 5 − z 6 − 1 2 z 7 − 4 z 8 − 3 2 z 9 − 5 2 z 10 ≥ − 4 w-z_1-4z_2-z_3-4z_5-z_6-\frac{1}{2}z_7-4z_8-\frac{3}{2}z_9-\frac{5}{2}z_{10}\ge-4 w − z 1 − 4 z 2 − z 3 − 4 z 5 − z 6 − 2 1 z 7 − 4 z 8 − 2 3 z 9 − 2 5 z 10 ≥ − 4
Figure 2. Laminar forest associated with w − z 1 − 4 z 2 − z 3 − 4 z 5 − z 6 − 1 2 z 7 − 4 z 8 − 3 2 z 9 − 5 2 z 10 ≥ − 4 w-z_1-4z_2-z_3-4z_5-z_6-\frac{1}{2}z_7-4z_8-\frac{3}{2}z_9-\frac{5}{2}z_{10}\ge-4 w − z 1 − 4 z 2 − z 3 − 4 z 5 − z 6 − 2 1 z 7 − 4 z 8 − 2 3 z 9 − 2 5 z 10 ≥ − 4
Lemma 5.14. Let S 1 ≺ S 2 ≺ ⋯ ≺ S k S_1\prec S_2\prec\cdots\prec S_k S 1 ≺ S 2 ≺ ⋯ ≺ S k S ′ ∈ F S'\in\mathcal{F} S ′ ∈ F S ′ = ( ⋃ i = 1 k S i ) ∪ { j } S'=\left(\bigcup_{i=1}^{k}S_i\right)\cup\{j\} S ′ = ( ⋃ i = 1 k S i ) ∪ { j } k ≤ 2 k\le2 k ≤ 2 k = 2 k=2 k = 2 S 1 ≺ { j } ≺ S 2 S_1\prec\{j\}\prec S_2 S 1 ≺ { j } ≺ S 2 α j = gap ( S 1 , S 2 ) − β \alpha_j=\operatorname{gap}(S_1,S_2)-\beta α j = gap ( S 1 , S 2 ) − β p j − u ( S 1 ) < β p^j-u(S_1)<\beta p j − u ( S 1 ) < β ℓ ( S 2 ) − p j < β \ell(S_2)-p^j<\beta ℓ ( S 2 ) − p j < β
Lemma 5.15. Let S 1 ≺ S 2 ≺ ⋯ ≺ S k S_1 \prec S_2 \prec\cdots\prec S_k S 1 ≺ S 2 ≺ ⋯ ≺ S k S i ∪ S j S_i \cup S_j S i ∪ S j i , j i,j i , j ⋃ i = 1 k S i \bigcup_{i=1}^k S_i ⋃ i = 1 k S i k ≥ 2 k \ge2 k ≥ 2
Lemma 5.16. If S S S S ′ S' S ′ S ′ = S ∪ { j } S'=S\cup\{j\} S ′ = S ∪ { j } F \mathcal{F} F
α j = { p j − u ( S ) if p j > u ( S ) , ℓ ( S ) − p j if p j < ℓ ( S ) , 0 otherwise. \alpha_j =
\begin{cases}
p^j-u(S) & \text{if } p^j>u(S),\\
\ell(S)-p^j & \text{if } p^j<\ell(S),\\
0 & \text{otherwise.}
\end{cases} α j = ⎩ ⎨ ⎧ p j − u ( S ) ℓ ( S ) − p j 0 if p j > u ( S ) , if p j < ℓ ( S ) , otherwise. Moreover, 0 ≤ α j < β 0 \le\alpha_j < \beta 0 ≤ α j < β
Remark 5.17. We want to emphasize that a variable z j z_j z j j j j S S S
Proof of Proposition 5.12. Lemmas 4.7 and 4.8 show that all leaf node of F \mathcal{F} F
Corollary 5.18. The forest F \mathcal{F} F
Proof. By Corollary 4.6, the laminar family contains at least n + 1 n+1 n + 1 [ n ] [n] [ n ] n n n
Construct an admissible β \beta β
Section 4 shows that all facets are obtained by sequential lifting. We next give an explicit description of these lifting sequences that will eventually lead to a facet.
Lemma 5.19. Let w − α ˉ T z ≥ − β ˉ w-\bar{\alpha}^{\mathsf{T}}z\ge-\bar{\beta} w − α ˉ T z ≥ − β ˉ F \mathcal{F} F β ˉ \bar{\beta} β ˉ β ˉ \bar{\beta} β ˉ μ t \mu_t μ t c t < d t c_t<d_t c t < d t
p μ t − p c t < β ˉ , p d t − p μ t < β ˉ , α ˉ μ t = p d t − p c t − β ˉ > 0. p^{\mu_t}-p^{c_t}<\bar{\beta},\qquad
p^{d_t}-p^{\mu_t}<\bar{\beta},\qquad
\bar{\alpha}_{\mu_t}=p^{d_t}-p^{c_t}-\bar{\beta}>0. p μ t − p c t < β ˉ , p d t − p μ t < β ˉ , α ˉ μ t = p d t − p c t − β ˉ > 0. Every variable subsequently inserted between the joined components has coefficient zero. The two exterior intervals have one chain each.
Proof. By Theorem 4.12, the lifting order produces exactly α ˉ \bar{\alpha} α ˉ β ˉ \bar{\beta} β ˉ
Consider an index j j j L L L R R R p R − p L ≤ β ˉ p^R-p^L\le\bar{\beta} p R − p L ≤ β ˉ α ˉ j = 0 \bar{\alpha}_j=0 α ˉ j = 0 p j − p L < β ˉ ≤ p R − p j p^j-p^L<\bar{\beta}\le p^R-p^j p j − p L < β ˉ ≤ p R − p j α ˉ j = p j − p L \bar{\alpha}_j=p^j-p^L α ˉ j = p j − p L p j − p L p^j-p^L p j − p L p R − p j p^R-p^j p R − p j β ˉ \bar{\beta} β ˉ β ˉ \bar{\beta} β ˉ
p j − p L < β ˉ , p R − p j < β ˉ , p R − p L > β ˉ . p^{j}-p^{L}<\bar{\beta},\quad p^{R}-p^{j}<\bar{\beta},\quad p^{R}-p^{L}>\bar{\beta}. p j − p L < β ˉ , p R − p j < β ˉ , p R − p L > β ˉ . Then α ˉ j = p R − p L − β ˉ > 0 \bar{\alpha}_{j}=p^{R}-p^{L}-\bar{\beta}>0 α ˉ j = p R − p L − β ˉ > 0 j j j β ˉ \bar{\beta} β ˉ β ˉ \bar{\beta} β ˉ
For an index to the left of the first leaf, the one-sided formula similarly gives either a strict extension of the left exterior chain or coefficient zero. The right exterior block is symmetric.
Theorem 5.20. Let w − α ˉ T z ≥ − β ˉ w-\bar{\alpha}^{\mathsf{T}}z\geq-\bar{\beta} w − α ˉ T z ≥ − β ˉ conv ( B ) \operatorname{conv}(B) conv ( B ) L \mathcal{L} L α ˉ \bar{\alpha} α ˉ β ˉ \bar{\beta} β ˉ
Proof. Let F \mathcal{F} F L \mathcal{L} L β ˉ \bar{\beta} β ˉ F \mathcal{F} F
Find the β ˉ \bar{\beta} β ˉ By Lemmas 4.7 and 4.8 , the leaves of F \mathcal{F} F { i } \{i\} { i } α ˉ i = β ˉ \bar{\alpha}_{i}=\bar{\beta} α ˉ i = β ˉ b 1 < ⋯ < b m b_{1}<\cdots<b_{m} b 1 < ⋯ < b m s < t s<t s < t { b s , b t } \{b_{s},b_{t}\} { b s , b t } p b t − p b s − 2 β ˉ ≥ − β ˉ p^{b_{t}}-p^{b_{s}}-2\bar{\beta}\geq-\bar{\beta} p b t − p b s − 2 β ˉ ≥ − β ˉ p b t − p b s ≥ β ˉ p^{b_{t}}-p^{b_{s}}\geq\bar{\beta} p b t − p b s ≥ β ˉ F \mathcal{F} F β ˉ \bar{\beta} β ˉ
Find the internal blocks. Choose a bottom-up lifting order with all leaf variables first. Such an order exists, and Theorem 4.12 shows that it recovers exactly α ˉ \bar{\alpha} α ˉ β ˉ \bar{\beta} β ˉ b t < b t + 1 b_{t}<b_{t+1} b t < b t + 1 Lemma 5.19 , the positive-coefficient variables between these leaves form two chains growing inward, with strict consecutive gaps, and possibly one merger.
If a positive merger occurs, the block satisfies the strict merged-block conditions, and its coefficients are given by (13) . Otherwise, let c t < d t c_{t}<d_{t} c t < d t p d t − p c t > β ˉ p^{d_{t}}-p^{c_{t}}>\bar{\beta} p d t − p c t > β ˉ c t c_{t} c t d t d_{t} d t β ˉ \bar{\beta} β ˉ d t = c t + 1 d_{t}=c_{t}+1 d t = c t + 1 p d t − p c t = β ˉ p^{d_{t}}-p^{c_{t}}=\bar{\beta} p d t − p c t = β ˉ (12) . All remaining variables have coefficient zero, as required.
Find the exterior blocks. By Lemma 5.19 , each exterior interval consists of a single outward-growing chain and zero-coefficient variables. Every chain gap is strictly less than β ˉ \bar{\beta} β ˉ (14) or (15) .
Choose an anchor block. By Corollary 5.18 , the forest contains a Type 4 node S = S − ∪ S + S=S^{-}\cup S^{+} S = S − ∪ S + S − ≺ S + S^{-}\prec S^{+} S − ≺ S + Proposition 5.12 , gap ( S − , S + ) = β ˉ \operatorname{gap}(S^{-},S^{+})=\bar{\beta} gap ( S − , S + ) = β ˉ S − S^{-} S − S + S^{+} S + β ˉ \bar{\beta} β ˉ β ˉ \bar{\beta} β ˉ S − S^{-} S − S + S^{+} S + Lemma 5.1 , contradicting their gap being β ˉ \bar{\beta} β ˉ β ˉ \bar{\beta} β ˉ
Consequently, every interval is a β ˉ \bar{\beta} β ˉ β ˉ \bar{\beta} β ˉ α ˉ \bar{\alpha} α ˉ
Theorem 5.21. Assume p 1 < ⋯ < p n p^{1}<\cdots<p^{n} p 1 < ⋯ < p n conv ( B ) \operatorname{conv}(B) conv ( B ) β \beta β
Proof. By Theorem 5.11, each admissible β \beta β
Corollary 5.22. Assume p 1 < p 2 < ⋯ < p n p^{1}<p^{2}<\cdots<p^{n} p 1 < p 2 < ⋯ < p n conv ( B ) \operatorname{conv}(B) conv ( B ) conv ( B ) \operatorname{conv}(B) conv ( B ) w ≥ 0 w\geq0 w ≥ 0 0 ≤ z i ≤ 1 0\leq z_i\leq1 0 ≤ z i ≤ 1 i ∈ [ n ] i\in[n] i ∈ [ n ]
Proof. By Theorem 5.11, every inequality output by Algorithm 1 is facet-defining. Conversely, let w − α ˉ T z ≥ − β ˉ w-\bar{\alpha}^{\mathsf{T}}z\geq-\bar{\beta} w − α ˉ T z ≥ − β ˉ β ˉ \bar{\beta} β ˉ α ˉ \bar{\alpha} α ˉ β ˉ ∈ B \bar{\beta}\in\mathcal{B} β ˉ ∈ B w ≥ 0 w\geq0 w ≥ 0 conv ( B ) \operatorname{conv}(B) conv ( B )
Polynomial-time separation in one dimension
The lifting description is complete but involves exponentially many permutations. However, separation does not require enumerating them. In one dimension, validity can be checked using only interval supports: a nontrivial w w w conv ( B ) \operatorname{conv}(B) conv ( B ) ∑ i = ℓ r α i − β ≤ p r − p ℓ \sum_{i=\ell}^{r}\alpha_i-\beta\leq p^{r}-p^{\ell} ∑ i = ℓ r α i − β ≤ p r − p ℓ 1 ≤ ℓ ≤ r ≤ n 1\leq\ell\leq r\leq n 1 ≤ ℓ ≤ r ≤ n ( w ^ , z ^ ) (\hat{w},\hat{z}) ( w ^ , z ^ ) z ^ ∈ [ 0 , 1 ] n \hat{z}\in[0,1]^n z ^ ∈ [ 0 , 1 ] n conv ( B ) \operatorname{conv}(B) conv ( B ) − w ^ -\hat{w} − w ^
max α , β ∑ i = 1 n z ^ i α i − β s.t. ∑ i = ℓ r α i − β ≤ p r − p ℓ , 1 ≤ ℓ ≤ r ≤ n , α ≥ 0 , β ≥ 0. (16) \begin{aligned}
\max_{\alpha,\beta}\quad& \sum_{i=1}^{n}\hat{z}_i\alpha_i-\beta\\
\text{s.t.}\quad& \sum_{i=\ell}^{r}\alpha_i-\beta\leq p^{r}-p^{\ell},\\
& 1\leq\ell\leq r\leq n,\\
& \alpha\geq0,\quad\beta\geq0. \tag*{(16)}
\end{aligned} α , β max s.t. i = 1 ∑ n z ^ i α i − β i = ℓ ∑ r α i − β ≤ p r − p ℓ , 1 ≤ ℓ ≤ r ≤ n , α ≥ 0 , β ≥ 0. (16) min y ∑ ℓ ≤ r ( p r − p ℓ ) y ℓ r s.t. ∑ ℓ ≤ i ≤ r y ℓ r ≥ z ^ i , i ∈ [ n ] , ∑ ℓ ≤ r y ℓ r = 1 , y ℓ r ≥ 0 , 1 ≤ ℓ ≤ r ≤ n . (17) \begin{aligned}
\min_y\quad& \sum_{\ell\leq r}(p^{r}-p^{\ell})y_{\ell r}\\
\text{s.t.}\quad& \sum_{\ell\leq i\leq r}y_{\ell r}\geq\hat{z}_i,\quad i\in[n],\\
& \sum_{\ell\leq r}y_{\ell r}=1,\\
& y_{\ell r}\geq0,\quad1\leq\ell\leq r\leq n. \tag*{(17)}
\end{aligned} y min s.t. ℓ ≤ r ∑ ( p r − p ℓ ) y ℓ r ℓ ≤ i ≤ r ∑ y ℓ r ≥ z ^ i , i ∈ [ n ] , ℓ ≤ r ∑ y ℓ r = 1 , y ℓ r ≥ 0 , 1 ≤ ℓ ≤ r ≤ n . (17) (D) is the corresponding dual. The equality constraint in (D) is because every singleton interval has zero cost, so any unused mass can be assigned to a singleton without changing the objective.
We next give a minimum-cost flow representation of (D). Let V = { s , t } ∪ { i − , i + : i ∈ [ n ] } V=\{s,t\}\cup\{i^{-},i^{+}:i\in[n]\} V = { s , t } ∪ { i − , i + : i ∈ [ n ]} i ∈ [ n ] i\in[n] i ∈ [ n ] ( s , i − ) (s,i^{-}) ( s , i − ) ( i − , i + ) (i^{-},i^{+}) ( i − , i + ) ( i + , t ) (i^{+},t) ( i + , t ) f i − i + ≥ z ^ i f_{i^{-}i^{+}}\geq\hat{z}_i f i − i + ≥ z ^ i i = 1 , … , n − 1 i=1,\ldots,n-1 i = 1 , … , n − 1 ( i + , ( i + 1 ) − ) (i^{+},(i+1)^{-}) ( i + , ( i + 1 ) − ) p i + 1 − p i p_{i+1}-p_i p i + 1 − p i s s s t t t
min ∑ i = 1 n − 1 ( p i + 1 − p i ) f i + , ( i + 1 ) − s.t. f is an s - t flow of value 1 , f i − i + ≥ z ^ i , i ∈ [ n ] , f ≥ 0. (18) \begin{aligned}
\min\quad& \sum_{i=1}^{n-1}(p_{i+1}-p_i)f_{i^{+},(i+1)^{-}}\\
\text{s.t.}\quad& f\text{ is an }s\text{-}t\text{ flow of value }1,\\
& f_{i^{-}i^{+}}\geq\hat{z}_i,\quad i\in[n],\\
& f\geq0. \tag*{(18)}
\end{aligned} min s.t. i = 1 ∑ n − 1 ( p i + 1 − p i ) f i + , ( i + 1 ) − f is an s - t flow of value 1 , f i − i + ≥ z ^ i , i ∈ [ n ] , f ≥ 0. (18) Lemma 5.23. Problems (D) and (MCF) are equivalent and have the same objective value.
Proof. Every s s s t t t [ l , r ] [l,r] [ l , r ]
P l r = s → l − → l + → ⋯ → r − → r + → t . P_{lr}=s\to l^{-}\to l^{+}\to\cdots\to r^{-}\to r^{+}\to t. P l r = s → l − → l + → ⋯ → r − → r + → t . Its cost is c ( P l r ) = ∑ i = l r − 1 ( p i + 1 − p i ) = p r − p l c(P_{lr})=\sum_{i=l}^{r-1}(p_{i+1}-p_i)=p_r-p_l c ( P l r ) = ∑ i = l r − 1 ( p i + 1 − p i ) = p r − p l
Given a feasible solution y y y y l r y_{lr} y l r s s s t t t P l r P_{lr} P l r ∑ l ≤ r y l r = 1 \sum_{l\leq r}y_{lr}=1 ∑ l ≤ r y l r = 1 s s s t t t f i − i + = ∑ l ≤ i ≤ r y l r ≥ z ^ i f_{i^{-}i^{+}}=\sum_{l\leq i\leq r}y_{lr}\geq\hat z_i f i − i + = ∑ l ≤ i ≤ r y l r ≥ z ^ i s s s t t t
∑ l ≤ r y l r c ( P l r ) = ∑ l ≤ r ( p r − p l ) y l r . \sum_{l\leq r}y_{lr}c(P_{lr})=\sum_{l\leq r}(p_r-p_l)y_{lr}. l ≤ r ∑ y l r c ( P l r ) = l ≤ r ∑ ( p r − p l ) y l r . Conversely, since the network is acyclic, every feasible unit flow admits an s s s t t t y l r y_{lr} y l r P l r P_{lr} P l r
∑ l ≤ r y l r = 1 , ∑ l ≤ i ≤ r y l r = f i − i + ≥ z ^ i , \sum_{l\leq r}y_{lr}=1,\qquad\sum_{l\leq i\leq r}y_{lr}=f_{i^{-}i^{+}}\geq\hat z_i, l ≤ r ∑ y l r = 1 , l ≤ i ≤ r ∑ y l r = f i − i + ≥ z ^ i , and the objective values coincide by the expression for c ( P l r ) c(P_{lr}) c ( P l r )
Theorem 5.24. When d = 1 d=1 d = 1 B B B O ( n 2 log 2 n ) O(n^2\log^2 n) O ( n 2 log 2 n )
The Convex Hull in Higher Dimensions
The uncrossing and laminar-basis results of § 4 hold in every dimension. What fails beyond one dimension is the additive left-to-right gap structure used to classify branching nodes.
For the rest of this section, we fix an arbitrary nontrivial facet w − α ⊤ z ≥ − β w-\alpha^{\top}z\geq-\beta w − α ⊤ z ≥ − β conv ( B ) \operatorname{conv}(B) conv ( B ) L \mathcal{L} L F \mathcal{F} F
The failure of the one-dimensional gap decomposition
For pairwise disjoint sets S 1 , … , S k ∈ L S_1,\ldots,S_k\in\mathcal{L} S 1 , … , S k ∈ L
Γ ( S 1 , … , S k ) : = wd ( ⋃ i = 1 k S i ) − ∑ i = 1 k wd ( S i ) . (19) \Gamma(S_1,\ldots,S_k):=\operatorname{wd}\left(\bigcup_{i=1}^{k}S_i\right)-\sum_{i=1}^{k}\operatorname{wd}(S_i). \tag*{(19)} Γ ( S 1 , … , S k ) := wd ( i = 1 ⋃ k S i ) − i = 1 ∑ k wd ( S i ) . (19) In one dimension, ordered disjoint sets satisfy
Γ ( S 1 , … , S k ) = ∑ i = 1 k − 1 gap ( S i , S i + 1 ) . \Gamma(S_1,\ldots,S_k)=\sum_{i=1}^{k-1}\operatorname{gap}(S_i,S_{i+1}). Γ ( S 1 , … , S k ) = i = 1 ∑ k − 1 gap ( S i , S i + 1 ) . There is no analogous pairwise decomposition in higher dimensions. Consider the example: p 1 = ( 0 , 0 ) p_1=(0,0) p 1 = ( 0 , 0 ) p 2 = ( 0 , 2 ) p_2=(0,2) p 2 = ( 0 , 2 ) p 3 = ( 1 , 1 ) p_3=(1,1) p 3 = ( 1 , 1 ) Γ ( { 1 } , { 2 } , { 3 } ) = 3 \Gamma(\{1\},\{2\},\{3\})=3 Γ ({ 1 } , { 2 } , { 3 }) = 3
The aggregate quantity (16) has a direct interpretation for tight nodes.
Lemma 6.1. Let S 1 , … , S k S_1,\ldots,S_k S 1 , … , S k w − α ⊤ z ≥ − β w-\alpha^{\top}z\geq-\beta w − α ⊤ z ≥ − β ⋃ i = 1 k S i \bigcup_{i=1}^{k}S_i ⋃ i = 1 k S i Γ ( S 1 , … , S k ) = ( k − 1 ) β \Gamma(S_1,\ldots,S_k)=(k-1)\beta Γ ( S 1 , … , S k ) = ( k − 1 ) β
Proof. Since the sets are disjoint,
α ( ⋃ i = 1 k S i ) = ∑ i = 1 k α ( S i ) = ∑ i = 1 k wd ( S i ) + k β . \alpha\left(\bigcup_{i=1}^{k} S_i\right)=\sum_{i=1}^{k}\alpha(S_i)=\sum_{i=1}^{k}\operatorname{wd}(S_i)+k\beta. α ( i = 1 ⋃ k S i ) = i = 1 ∑ k α ( S i ) = i = 1 ∑ k wd ( S i ) + k β . Tightness of the union gives
wd ( ⋃ i = 1 k S i ) − ∑ i = 1 k wd ( S i ) − k β = − β , \operatorname{wd}\left(\bigcup_{i=1}^{k} S_i\right)-\sum_{i=1}^{k}\operatorname{wd}(S_i)-k\beta=-\beta, wd ( i = 1 ⋃ k S i ) − i = 1 ∑ k wd ( S i ) − k β = − β , which is the desired identity.
General node configurations
Let S ′ ∈ F S' \in\mathcal{F} S ′ ∈ F S 1 , … , S k S_1,\ldots,S_k S 1 , … , S k Lemma 4.9 implies that S ′ S' S ′
Proposition 6.2 (Higher-dimensional node classification). Every node S ′ ∈ F S' \in\mathcal{F} S ′ ∈ F
Type 1. S ′ = { j } S'=\{j\} S ′ = { j } Then α j = β \alpha_j=\beta α j = β
Type 2. S ′ = S ∪ { j } S'=S\cup\{j\} S ′ = S ∪ { j } where S S S α j = wd ( S ′ ) − wd ( S ) \alpha_j=\operatorname{wd}(S')-\operatorname{wd}(S) α j = wd ( S ′ ) − wd ( S )
Type 3. S ′ = ( ⋃ i = 1 k S i ) ∪ { j } S'=\left(\bigcup_{i=1}^{k}S_i\right)\cup\{j\} S ′ = ( ⋃ i = 1 k S i ) ∪ { j } where S 1 , … , S k S_1,\ldots,S_k S 1 , … , S k S ′ S' S ′ F \mathcal{F} F
α j = wd ( S ′ ) − ∑ i = 1 k wd ( S i ) − ( k − 1 ) β . (20) \alpha_j=\operatorname{wd}(S')-\sum_{i=1}^{k}\operatorname{wd}(S_i)-(k-1)\beta. \tag*{(20)} α j = wd ( S ′ ) − i = 1 ∑ k wd ( S i ) − ( k − 1 ) β . (20) Type 4. S ′ = ⋃ i = 1 k S i S'=\bigcup_{i=1}^{k}S_i S ′ = ⋃ i = 1 k S i k ≥ 2 k\ge2 k ≥ 2 where S 1 , … , S k S_1,\ldots,S_k S 1 , … , S k S ′ S' S ′ F \mathcal{F} F Γ ( S 1 , … , S k ) = ( k − 1 ) β \Gamma(S_1,\ldots,S_k)=(k-1)\beta Γ ( S 1 , … , S k ) = ( k − 1 ) β
Remark 6.3. Type 2 is the special case k = 1 k=1 k = 1
Proof. The structural alternatives follow from Lemmas 4.7 and 4.9 . Type 1 follows from Lemma 4.8 . In Type 3, tightness of S ′ S' S ′
− β = wd ( S ′ ) − α j − ∑ i = 1 k α ( S i ) = wd ( S ′ ) − α j − ∑ i = 1 k [ wd ( S i ) + β ] . -\beta=\operatorname{wd}(S')-\alpha_j-\sum_{i=1}^{k}\alpha(S_i)=\operatorname{wd}(S')-\alpha_j-\sum_{i=1}^{k}\left[\operatorname{wd}(S_i)+\beta\right]. − β = wd ( S ′ ) − α j − i = 1 ∑ k α ( S i ) = wd ( S ′ ) − α j − i = 1 ∑ k [ wd ( S i ) + β ] . which yields (20) . Type 4 is Lemma 6.1 .
The laminar family contains at least n + 1 n+1 n + 1
Characterization of the right-hand-side of a nontrivial facet
Type 4 nodes give a characterization of the right-hand sides of nontrivial facets through partitions of tight sets. This suggests that to find all possible right-hand-sides, we need to consider partitions of subsets S ⊆ [ n ] S \subseteq[n] S ⊆ [ n ] β S ∗ \beta^*_S β S ∗ S S S ∣ S ∣ ≥ 2 |S| \ge2 ∣ S ∣ ≥ 2 S S S β S ∗ \beta^*_S β S ∗ β S ∗ \beta^*_S β S ∗ S S S
For any S ⊆ [ n ] S \subseteq[n] S ⊆ [ n ] ∣ S ∣ ≥ 2 |S| \ge2 ∣ S ∣ ≥ 2 Π ( S ) \Pi(S) Π ( S ) S S S P = { S 1 , … , S k } ∈ Π ( S ) \mathcal{P} = \{S_1,\ldots,S_k\} \in\Pi(S) P = { S 1 , … , S k } ∈ Π ( S ) k ≥ 2 k \ge2 k ≥ 2
β S ( P ) = wd ( S ) − ∑ i = 1 k wd ( S i ) k − 1 , \beta_S(\mathcal{P}) = \frac{\operatorname{wd}(S)-\sum_{i=1}^{k}\operatorname{wd}(S_i)}{k-1}, β S ( P ) = k − 1 wd ( S ) − ∑ i = 1 k wd ( S i ) , and let β S ∗ = max P ∈ Π ( S ) ∣ P ∣ ≥ 2 β S ( P ) \beta^*_S = \max_{\substack{\mathcal{P}\in\Pi(S)\\|\mathcal{P}|\ge2}}\beta_S(\mathcal{P}) β S ∗ = max P ∈ Π ( S ) ∣ P ∣ ≥ 2 β S ( P )
Lemma 6.4. Let P = { S 1 , … , S k } \mathcal{P} = \{S_1,\ldots,S_k\} P = { S 1 , … , S k } S ⊆ [ n ] S \subseteq[n] S ⊆ [ n ] k ≥ 2 k \ge2 k ≥ 2 w − α ⊤ z ≥ − β w-\alpha^\top z \ge-\beta w − α ⊤ z ≥ − β conv ( B ) \operatorname{conv}(B) conv ( B ) S , S 1 , … , S k S,S_1,\ldots,S_k S , S 1 , … , S k
Proof. Consider the normalized polar of conv ( B ) \operatorname{conv}(B) conv ( B ) Q : = { ( α , β ) ∈ R n + 1 : α ( T ) − β ≤ wd ( T ) , ∀ T ⊆ [ n ] } Q := \{(\alpha,\beta) \in\mathbb{R}^{n+1}: \alpha(T)-\beta\le\operatorname{wd}(T),\ \forall T \subseteq[n]\} Q := {( α , β ) ∈ R n + 1 : α ( T ) − β ≤ wd ( T ) , ∀ T ⊆ [ n ]} S , S 1 , … , S k S,S_1,\ldots,S_k S , S 1 , … , S k F Q = { ( α , β ) ∈ Q : α ( T ) − β = wd ( T ) , ∀ T ∈ { S , S 1 , … , S k } } F_Q = \{(\alpha,\beta) \in Q : \alpha(T)-\beta= \operatorname{wd}(T),\ \forall T \in\{S,S_1,\ldots,S_k\}\} F Q = {( α , β ) ∈ Q : α ( T ) − β = wd ( T ) , ∀ T ∈ { S , S 1 , … , S k }} Q Q Q ( h , τ ) (h,\tau) ( h , τ ) h ( T ) − τ = 0 h(T)-\tau=0 h ( T ) − τ = 0 T ⊆ [ n ] T \subseteq[n] T ⊆ [ n ] T = ∅ T=\varnothing T = ∅ T = { i } T=\{i\} T = { i } τ = 0 \tau=0 τ = 0 h = 0 h=0 h = 0 F Q F_Q F Q Q Q Q Q Q Q ( α ∗ , β ∗ ) (\alpha^*,\beta^*) ( α ∗ , β ∗ ) w − α ∗ ⊤ z ≥ − β ∗ w-\alpha^{*\top}z\ge-\beta^* w − α ∗ ⊤ z ≥ − β ∗ conv B \operatorname{conv} B conv B S , S 1 , … , S k S,S_1,\ldots,S_k S , S 1 , … , S k S 1 , … , S k S_1,\ldots,S_k S 1 , … , S k S S S S S S
( k − 1 ) β ∗ = wd ( S ) − ∑ i = 1 k wd ( S i ) = ( k − 1 ) β . (k-1)\beta^*=\operatorname{wd}(S)-\sum_{i=1}^{k}\operatorname{wd}(S_i)=(k-1)\beta. ( k − 1 ) β ∗ = wd ( S ) − i = 1 ∑ k wd ( S i ) = ( k − 1 ) β . Hence β ∗ = β \beta^*=\beta β ∗ = β
Lemma 6.4 motivates the following definition.
Definition 6.5 (Facet admissible partition). Given a subset S ⊆ [ n ] S \subseteq[n] S ⊆ [ n ] P = { S 1 , … , S k } \mathcal{P}=\{S_1,\ldots,S_k\} P = { S 1 , … , S k } S S S k ≥ 2 k\ge2 k ≥ 2 facet-admissible if there exists a facet w − α ⊤ z ≥ − β w-\alpha^\top z\ge-\beta w − α ⊤ z ≥ − β conv ( B ) \operatorname{conv}(B) conv ( B ) S 1 , S 2 , … , S k S_1,S_2,\ldots,S_k S 1 , S 2 , … , S k S S S
Lemma 6.6. Suppose a valid inequality w − α ⊤ z ≥ − β w-\alpha^\top z\ge-\beta w − α ⊤ z ≥ − β S S S β S ( P ) ≤ β \beta_S(\mathcal{P})\le\beta β S ( P ) ≤ β P ∈ Π ( S ) \mathcal{P}\in\Pi(S) P ∈ Π ( S ) ∣ P ∣ ≥ 2 |\mathcal{P}|\ge2 ∣ P ∣ ≥ 2 P \mathcal{P} P
Proof. Let P = { S 1 , … , S k } \mathcal{P}=\{S_1,\ldots,S_k\} P = { S 1 , … , S k } S S S k ≥ 2 k\ge2 k ≥ 2
α ( S i ) ≤ wd ( S i ) + β , i = 1 , … , k . \alpha(S_i)\le\operatorname{wd}(S_i)+\beta,\qquad i=1,\ldots,k. α ( S i ) ≤ wd ( S i ) + β , i = 1 , … , k . Since S S S
wd ( S ) + β = α ( S ) = ∑ i = 1 k α ( S i ) ≤ ∑ i = 1 k ( wd ( S i ) + β ) . \operatorname{wd}(S)+\beta=\alpha(S)=\sum_{i=1}^{k}\alpha(S_i)\le\sum_{i=1}^{k}(\operatorname{wd}(S_i)+\beta). wd ( S ) + β = α ( S ) = i = 1 ∑ k α ( S i ) ≤ i = 1 ∑ k ( wd ( S i ) + β ) . Rearranging gives
β S ( P ) = wd ( S ) − ∑ i = 1 k wd ( S i ) k − 1 ≤ β . \beta_S(\mathcal{P})=\frac{\operatorname{wd}(S)-\sum_{i=1}^{k}\operatorname{wd}(S_i)}{k-1}\le\beta. β S ( P ) = k − 1 wd ( S ) − ∑ i = 1 k wd ( S i ) ≤ β . Equality holds if and only if every S i ∈ P S_i\in\mathcal{P} S i ∈ P
The reverse of the lemma is also true. We provide the proof in Appendix § 11 .
Theorem 6.7. For every S ⊆ [ n ] S \subseteq[n] S ⊆ [ n ] ∣ S ∣ ≥ 2 |S| \ge2 ∣ S ∣ ≥ 2 P ∈ Π ( S ) \mathcal{P} \in\Pi(S) P ∈ Π ( S ) β S ∗ \beta^*_S β S ∗ S S S
Remark 6.8. If wd ( S ) > 0 \operatorname{wd}(S) > 0 wd ( S ) > 0 β S ∗ > 0 \beta^*_S > 0 β S ∗ > 0 wd ( S ) = 0 \operatorname{wd}(S) = 0 wd ( S ) = 0 β S ∗ = 0 \beta^*_S = 0 β S ∗ = 0 S S S w ≥ 0 w \ge0 w ≥ 0
Corollary 6.9. Let S ⊆ [ n ] S \subseteq[n] S ⊆ [ n ] ∣ S ∣ ≥ 2 |S| \ge2 ∣ S ∣ ≥ 2 P ∈ Π ( S ) \mathcal{P} \in\Pi(S) P ∈ Π ( S ) ∣ P ∣ ≥ 2 |\mathcal{P}| \ge2 ∣ P ∣ ≥ 2 β S ( P ) = β S ∗ \beta_S(\mathcal{P}) = \beta^*_S β S ( P ) = β S ∗
{ β > 0 : w − α T z ≥ − β defines a nontrivial facet for some α } = { β S ∗ : S ⊆ [ n ] , ∣ S ∣ ≥ 2 , wd ( S ) > 0 } \{\beta> 0 : w - \alpha^{\mathsf{T}}z \ge-\beta\text{ defines a nontrivial facet for some } \alpha\}
= \{\beta^*_S : S \subseteq[n], |S| \ge2, \operatorname{wd}(S) > 0\} { β > 0 : w − α T z ≥ − β defines a nontrivial facet for some α } = { β S ∗ : S ⊆ [ n ] , ∣ S ∣ ≥ 2 , wd ( S ) > 0 } The preceding results establish that the facet-admissible partitions of a given subset S S S β S ∗ \beta^*_S β S ∗ β S ∗ \beta^*_S β S ∗ § 11 .
Theorem 6.10. There exists an algorithm that computes β S ∗ \beta^*_S β S ∗ S ⊆ [ n ] S \subseteq[n] S ⊆ [ n ] ∣ S ∣ ≥ 2 |S| \ge2 ∣ S ∣ ≥ 2 O ( ∣ S ∣ 2 ) O(|S|^2) O ( ∣ S ∣ 2 )
Family of facets
We next provide a family of facets by identifying the smallest value of β \beta β conv ( B ) \operatorname{conv}(B) conv ( B )
Proposition 6.11. Assume that no two points coincide. Then
β min : = min S ⊆ [ n ] ∣ S ∣ ≥ 2 wd ( S ) ∣ S ∣ − 1 (21) \beta_{\min} := \min_{\substack{S \subseteq[n]\\ |S| \ge2}} \frac{\operatorname{wd}(S)}{|S|-1} \tag*{(21)} β m i n := S ⊆ [ n ] ∣ S ∣ ≥ 2 min ∣ S ∣ − 1 wd ( S ) (21) is the smallest possible right-hand side of a nontrivial normalized facet of conv ( B ) \operatorname{conv}(B) conv ( B )
w − β min ∑ i = 1 n z i ≥ − β min (22) w-\beta_{\min}\sum_{i=1}^{n}z_i \ge-\beta_{\min} \tag*{(22)} w − β m i n i = 1 ∑ n z i ≥ − β m i n (22) is facet-defining.
Proof. Let w − α T z ≥ − β w-\alpha^{\mathsf{T}}z \ge-\beta w − α T z ≥ − β conv ( B ) \operatorname{conv}(B) conv ( B ) α i ≤ β \alpha_i \le\beta α i ≤ β n + 1 n+1 n + 1 n n n T T T ∣ T ∣ ≥ 2 |T| \ge2 ∣ T ∣ ≥ 2
wd ( T ) = α ( T ) − β ≤ ( ∣ T ∣ − 1 ) β , \operatorname{wd}(T)=\alpha(T)-\beta\le(|T|-1)\beta, wd ( T ) = α ( T ) − β ≤ ( ∣ T ∣ − 1 ) β , and hence
β ≥ wd ( T ) ∣ T ∣ − 1 ≥ β min . \beta\ge\frac{\operatorname{wd}(T)}{|T|-1} \ge\beta_{\min}. β ≥ ∣ T ∣ − 1 wd ( T ) ≥ β m i n . For validity of (19), let S ⊆ [ n ] S \subseteq[n] S ⊆ [ n ] ∣ S ∣ ≥ 2 |S| \ge2 ∣ S ∣ ≥ 2 wd ( S ) ≥ ( ∣ S ∣ − 1 ) β min \operatorname{wd}(S) \ge(|S|-1)\beta_{\min} wd ( S ) ≥ ( ∣ S ∣ − 1 ) β m i n S ∗ S^* S ∗ n n n ( wd ( S ∗ ) , χ S ∗ ) (\operatorname{wd}(S^*),\chi^{S^*}) ( wd ( S ∗ ) , χ S ∗ ) χ S ∗ \chi^{S^*} χ S ∗ ∑ i z i = 1 \sum_i z_i=1 ∑ i z i = 1
We propose an algorithm that finds β min \beta_{\min} β m i n
Theorem 6.12. There exists an algorithm that computes β min \beta_{\min} β m i n O ( n 2 ) O(n^2) O ( n 2 ) d d d
Discussion
Many arguments in this paper, such as the uncrossing argument, are independent of the w d w_d w d
We are able to give an explicit characterization of the right-hand sides of all facets in the higher-dimensional case. We are hoping to give an explicit description for all facets, not just the right-hand sides.
Omitted Proofs in Section 4
Lemma 4.4. [Crossing lemma] If S , T ∈ T ( α , β ) S,T\in\mathcal{T}(\alpha,\beta) S , T ∈ T ( α , β ) S ∩ T ≠ ∅ S\cap T\ne\varnothing S ∩ T = ∅ S ∩ T ∈ T ( α , β ) S\cap T\in\mathcal{T}(\alpha,\beta) S ∩ T ∈ T ( α , β ) S ∪ T ∈ T ( α , β ) S\cup T\in\mathcal{T}(\alpha,\beta) S ∪ T ∈ T ( α , β ) ( wd ( S ) , χ S ) + ( wd ( T ) , χ T ) = ( wd ( S ∩ T ) , χ S ∩ T ) + ( wd ( S ∪ T ) , χ S ∪ T ) (\operatorname{wd}(S),\chi^{S})+(\operatorname{wd}(T),\chi^{T})=(\operatorname{wd}(S\cap T),\chi^{S\cap T})+(\operatorname{wd}(S\cup T),\chi^{S\cup T}) ( wd ( S ) , χ S ) + ( wd ( T ) , χ T ) = ( wd ( S ∩ T ) , χ S ∩ T ) + ( wd ( S ∪ T ) , χ S ∪ T )
Proof. Let ϕ ( A ) : = wd ( A ) − α ( A ) \phi(A):=\operatorname{wd}(A)-\alpha(A) ϕ ( A ) := wd ( A ) − α ( A ) α \alpha α
ϕ ( S ∪ T ) + ϕ ( S ∩ T ) ≤ ϕ ( S ) + ϕ ( T ) = − 2 β . \phi(S\cup T)+\phi(S\cap T)\le\phi(S)+\phi(T)=-2\beta. ϕ ( S ∪ T ) + ϕ ( S ∩ T ) ≤ ϕ ( S ) + ϕ ( T ) = − 2 β . Validity gives ϕ ( S ∪ T ) ≥ − β \phi(S\cup T)\ge-\beta ϕ ( S ∪ T ) ≥ − β ϕ ( S ∩ T ) ≥ − β \phi(S\cap T)\ge-\beta ϕ ( S ∩ T ) ≥ − β
wd ( S ∪ T ) + wd ( S ∩ T ) = wd ( S ) + wd ( T ) \operatorname{wd}(S\cup T)+\operatorname{wd}(S\cap T)=\operatorname{wd}(S)+\operatorname{wd}(T) wd ( S ∪ T ) + wd ( S ∩ T ) = wd ( S ) + wd ( T ) The incidence-vector identity χ S + χ T = χ S ∩ T + χ S ∪ T \chi^{S}+\chi^{T}=\chi^{S\cap T}+\chi^{S\cup T} χ S + χ T = χ S ∩ T + χ S ∪ T
Lemma 4.5. Let L \mathcal{L} L T ( α , β ) \mathcal{T}(\alpha,\beta) T ( α , β ) aff ( T ( α , β ) ^ ) = aff ( L ^ ) \operatorname{aff}(\widehat{\mathcal{T}(\alpha,\beta)})=\operatorname{aff}(\widehat{\mathcal{L}}) aff ( T ( α , β ) ) = aff ( L )
Proof. For S ∈ T ( α , β ) S\in\mathcal{T}(\alpha,\beta) S ∈ T ( α , β )
c L ( S ) : = { R ∈ L : R crosses S } . c_{\mathcal{L}}(S):=\{R\in\mathcal{L}:R\text{ crosses }S\}. c L ( S ) := { R ∈ L : R crosses S } . We prove by induction on ∣ c L ( S ) ∣ |c_{\mathcal{L}}(S)| ∣ c L ( S ) ∣ ( wd ( S ) , χ S ) ∈ aff ( L ^ ) (\operatorname{wd}(S),\chi^{S})\in\operatorname{aff}(\widehat{\mathcal{L}}) ( wd ( S ) , χ S ) ∈ aff ( L )
If c L ( S ) = ∅ c_{\mathcal{L}}(S)=\varnothing c L ( S ) = ∅ S S S L \mathcal{L} L L \mathcal{L} L S ∈ L S\in\mathcal{L} S ∈ L
Now suppose c L ( S ) ≠ ∅ c_{\mathcal{L}}(S)\ne\varnothing c L ( S ) = ∅ R ∈ c L ( S ) R\in c_{\mathcal{L}}(S) R ∈ c L ( S ) S ∩ R S\cap R S ∩ R S ∪ R S\cup R S ∪ R
( wd ( S ) , χ S ) = ( wd ( S ∩ R ) , χ S ∩ R ) + ( wd ( S ∪ R ) , χ S ∪ R ) − ( wd ( R ) , χ R ) . (\operatorname{wd}(S),\chi^{S})=(\operatorname{wd}(S\cap R),\chi^{S\cap R})+(\operatorname{wd}(S\cup R),\chi^{S\cup R})-(\operatorname{wd}(R),\chi^{R}). ( wd ( S ) , χ S ) = ( wd ( S ∩ R ) , χ S ∩ R ) + ( wd ( S ∪ R ) , χ S ∪ R ) − ( wd ( R ) , χ R ) . Moreover,
c L ( S ∩ R ) ⊊ c L ( S ) , c L ( S ∪ R ) ⊊ c L ( S ) . c_{\mathcal{L}}(S\cap R)\subsetneq c_{\mathcal{L}}(S),\qquad c_{\mathcal{L}}(S\cup R)\subsetneq c_{\mathcal{L}}(S). c L ( S ∩ R ) ⊊ c L ( S ) , c L ( S ∪ R ) ⊊ c L ( S ) . Indeed, if Q ∈ L Q\in\mathcal{L} Q ∈ L S ∩ R S\cap R S ∩ R Q Q Q R R R Q ⊊ R Q\subsetneq R Q ⊊ R Q Q Q S S S L \mathcal{L} L S ∪ R S\cup R S ∪ R S S S R R R S S S S ∩ R S\cap R S ∩ R S ∪ R S\cup R S ∪ R
The induction hypothesis therefore applies to S ∩ R S\cap R S ∩ R S ∪ R S\cup R S ∪ R R ∈ L R\in\mathcal{L} R ∈ L ( wd ( S ) , χ S ) ∈ aff ( L ^ ) (\operatorname{wd}(S),\chi^{S})\in\operatorname{aff}(\widehat{\mathcal{L}}) ( wd ( S ) , χ S ) ∈ aff ( L ) L ⊆ T ( α , β ) \mathcal{L}\subseteq\mathcal{T}(\alpha,\beta) L ⊆ T ( α , β )
Omitted Proofs in Section 5
Lemma 5.14. Let S 1 ≺ S 2 ≺ ⋯ ≺ S k S_1\prec S_2\prec\cdots\prec S_k S 1 ≺ S 2 ≺ ⋯ ≺ S k S ′ ∈ F S'\in\mathcal{F} S ′ ∈ F S ′ = ( ⋃ i = 1 k S i ) ∪ { j } S'=\left(\bigcup_{i=1}^{k}S_i\right)\cup\{j\} S ′ = ( ⋃ i = 1 k S i ) ∪ { j } k ≤ 2 k\le2 k ≤ 2 k = 2 k=2 k = 2 S 1 ≺ { j } ≺ S 2 S_1\prec\{j\}\prec S_2 S 1 ≺ { j } ≺ S 2 α j = gap ( S 1 , S 2 ) − β \alpha_j=\operatorname{gap}(S_1,S_2)-\beta α j = gap ( S 1 , S 2 ) − β p j − u ( S 1 ) < β p^j-u(S_1)<\beta p j − u ( S 1 ) < β ℓ ( S 2 ) − p j < β \ell(S_2)-p^j<\beta ℓ ( S 2 ) − p j < β
Proof. Before proving the statement, we first show that the union of two consecutive children is not tight. For i = 1 , … , k − 1 i=1,\ldots,k-1 i = 1 , … , k − 1 U i : = S i ∪ S i + 1 U_i:=S_i\cup S_{i+1} U i := S i ∪ S i + 1 U i U_i U i L \mathcal{L} L
Indeed, let R ∈ L R\in\mathcal{L} R ∈ L R R R S ′ S' S ′ R ∩ S ′ = ∅ R\cap S'=\varnothing R ∩ S ′ = ∅ S ′ ⊆ R S'\subseteq R S ′ ⊆ R R ⊆ S ′ R\subseteq S' R ⊆ S ′ R R R U i U_i U i S 1 , … , S k S_1,\ldots,S_k S 1 , … , S k S ′ S' S ′ R R R R ⊆ U i R\subseteq U_i R ⊆ U i R ∩ U i = ∅ R\cap U_i=\varnothing R ∩ U i = ∅ U i U_i U i L \mathcal{L} L
If U i U_i U i L \mathcal{L} L U i ∈ L U_i\in\mathcal{L} U i ∈ L S i ⊊ U i ⊊ S ′ S_i\subsetneq U_i\subsetneq S' S i ⊊ U i ⊊ S ′ S i S_i S i S ′ S' S ′ U i U_i U i i = 1 , … , k − 1 i=1,\ldots,k-1 i = 1 , … , k − 1 gap ( S i , S i + 1 ) > β \operatorname{gap}(S_i,S_{i+1})>\beta gap ( S i , S i + 1 ) > β
Show k ≤ 2 k \le2 k ≤ 2 To this end, we use validity after deleting an extreme child: S 1 S_1 S 1 S k S_k S k
Suppose for the contrary that { j } ⊀ S 2 \{j\} \not\prec S_2 { j } ≺ S 2 p j ≥ ℓ ( S 2 ) p^j \ge\ell(S_2) p j ≥ ℓ ( S 2 ) T : = S ′ ∖ S 1 T := S' \setminus S_1 T := S ′ ∖ S 1 S 1 S_1 S 1 p j ≥ ℓ ( S 2 ) p^j \ge\ell(S_2) p j ≥ ℓ ( S 2 ) S 1 S_1 S 1 ℓ ( S 1 ) \ell(S_1) ℓ ( S 1 ) ℓ ( S 2 ) \ell(S_2) ℓ ( S 2 )
wd ( S ′ ) − wd ( T ) = ℓ ( S 2 ) − ℓ ( S 1 ) = wd ( S 1 ) + gap ( S 1 , S 2 ) . \operatorname{wd}(S')-\operatorname{wd}(T)=\ell(S_2)-\ell(S_1)=\operatorname{wd}(S_1)+\operatorname{gap}(S_1,S_2). wd ( S ′ ) − wd ( T ) = ℓ ( S 2 ) − ℓ ( S 1 ) = wd ( S 1 ) + gap ( S 1 , S 2 ) . Since S 1 S_1 S 1 α ( S 1 ) = wd ( S 1 ) + β \alpha(S_1)=\operatorname{wd}(S_1)+\beta α ( S 1 ) = wd ( S 1 ) + β S ′ S' S ′ α ( T ) = α ( S ′ ) − α ( S 1 ) \alpha(T)=\alpha(S')-\alpha(S_1) α ( T ) = α ( S ′ ) − α ( S 1 )
wd ( T ) − α ( T ) = wd ( S ′ ) − α ( S ′ ) − ( wd ( S ′ ) − wd ( T ) ) + α ( S 1 ) = − β − ( wd ( S 1 ) + gap ( S 1 , S 2 ) ) + ( wd ( S 1 ) + β ) = − gap ( S 1 , S 2 ) < − β . \begin{aligned}
\operatorname{wd}(T)-\alpha(T)
&=\operatorname{wd}(S')-\alpha(S')-\bigl(\operatorname{wd}(S')-\operatorname{wd}(T)\bigr)+\alpha(S_1)\\
&=-\beta-\bigl(\operatorname{wd}(S_1)+\operatorname{gap}(S_1,S_2)\bigr)+\bigl(\operatorname{wd}(S_1)+\beta\bigr)\\
&=-\operatorname{gap}(S_1,S_2)\\
&<-\beta.
\end{aligned} wd ( T ) − α ( T ) = wd ( S ′ ) − α ( S ′ ) − ( wd ( S ′ ) − wd ( T ) ) + α ( S 1 ) = − β − ( wd ( S 1 ) + gap ( S 1 , S 2 ) ) + ( wd ( S 1 ) + β ) = − gap ( S 1 , S 2 ) < − β . which contradicts the validity of the facet at the support T T T { j } ≺ S 2 \{j\}\prec S_2 { j } ≺ S 2 T ′ : = S ′ ∖ S k T' := S'\setminus S_k T ′ := S ′ ∖ S k { j } ≻ S k − 1 \{j\}\succ S_{k-1} { j } ≻ S k − 1
If k ≥ 3 k\ge3 k ≥ 3 ℓ ( S 2 ) ≤ u ( S k − 1 ) \ell(S_2)\le u(S_{k-1}) ℓ ( S 2 ) ≤ u ( S k − 1 )
p j < ℓ ( S 2 ) ≤ u ( S k − 1 ) < p j , (23) p^j<\ell(S_2)\le u(S_{k-1})<p^j, \tag*{(23)} p j < ℓ ( S 2 ) ≤ u ( S k − 1 ) < p j , (23) a contradiction. Hence k ≤ 2 k\le2 k ≤ 2
Show S 1 ≺ { j } ≺ S 2 S_1\prec\{j\}\prec S_2 S 1 ≺ { j } ≺ S 2 α j = gap ( S 1 , S 2 ) − β \alpha_j=\operatorname{gap}(S_1,S_2)-\beta α j = gap ( S 1 , S 2 ) − β k = 2 k=2 k = 2 Suppose now that k = 2 k=2 k = 2 u ( S 1 ) < p j < ℓ ( S 2 ) u(S_1)<p^j<\ell(S_2) u ( S 1 ) < p j < ℓ ( S 2 ) S 1 ≺ { j } ≺ S 2 S_1\prec\{j\}\prec S_2 S 1 ≺ { j } ≺ S 2
Because p j p^j p j j j j
wd ( S ′ ) = wd ( S 1 ) + gap ( S 1 , S 2 ) + wd ( S 2 ) . \operatorname{wd}(S')=\operatorname{wd}(S_1)+\operatorname{gap}(S_1,S_2)+\operatorname{wd}(S_2). wd ( S ′ ) = wd ( S 1 ) + gap ( S 1 , S 2 ) + wd ( S 2 ) . Using tightness of S ′ S' S ′ S 1 S_1 S 1 S 2 S_2 S 2
− β = wd ( S ′ ) − α ( S ′ ) = wd ( S 1 ) + wd ( S 2 ) + gap ( S 1 , S 2 ) − α ( S 1 ) − α ( S 2 ) − α j = − 2 β + gap ( S 1 , S 2 ) − α j . \begin{aligned}
-\beta&=\operatorname{wd}(S')-\alpha(S')\\
&=\operatorname{wd}(S_1)+\operatorname{wd}(S_2)+\operatorname{gap}(S_1,S_2)-\alpha(S_1)-\alpha(S_2)-\alpha_j\\
&=-2\beta+\operatorname{gap}(S_1,S_2)-\alpha_j.
\end{aligned} − β = wd ( S ′ ) − α ( S ′ ) = wd ( S 1 ) + wd ( S 2 ) + gap ( S 1 , S 2 ) − α ( S 1 ) − α ( S 2 ) − α j = − 2 β + gap ( S 1 , S 2 ) − α j . Therefore, α j = gap ( S 1 , S 2 ) − β = gap ( S 1 , S 2 ) − β \alpha_j=\operatorname{gap}(S_1,S_2)-\beta=\operatorname{gap}(S_1,S_2)-\beta α j = gap ( S 1 , S 2 ) − β = gap ( S 1 , S 2 ) − β
The “moreover” part. Evaluate the valid facet inequality on S 1 ∪ { j } S_1\cup\{j\} S 1 ∪ { j } S 1 ≺ { j } S_1\prec\{j\} S 1 ≺ { j }
wd ( S 1 ∪ { j } ) − α ( S 1 ∪ { j } ) = wd ( S 1 ) + p j − u ( S 1 ) − α ( S 1 ) − α j = p j − u ( S 1 ) − β − α j = p j − ℓ ( S 2 ) ≥ − β . \begin{aligned}
\operatorname{wd}(S_1\cup\{j\})-\alpha(S_1\cup\{j\})
&=\operatorname{wd}(S_1)+p^j-u(S_1)-\alpha(S_1)-\alpha_j\\
&=p^j-u(S_1)-\beta-\alpha_j\\
&=p^j-\ell(S_2)\\
&\ge-\beta.
\end{aligned} wd ( S 1 ∪ { j }) − α ( S 1 ∪ { j }) = wd ( S 1 ) + p j − u ( S 1 ) − α ( S 1 ) − α j = p j − u ( S 1 ) − β − α j = p j − ℓ ( S 2 ) ≥ − β . where the last inequality is by validity at S 1 ∪ { j } S_1\cup\{j\} S 1 ∪ { j } S 2 ∪ { j } S_2\cup\{j\} S 2 ∪ { j } p j − u ( S 1 ) ≤ β p^j-u(S_1)\le\beta p j − u ( S 1 ) ≤ β ℓ ( S 2 ) − p j = β \ell(S_2)-p^j=\beta ℓ ( S 2 ) − p j = β S 1 ∪ { j } S_1\cup\{j\} S 1 ∪ { j } L \mathcal{L} L S 1 S_1 S 1 S ′ S' S ′ L \mathcal{L} L ℓ ( S 2 ) − p j < β \ell(S_2)-p^j<\beta ℓ ( S 2 ) − p j < β p j − u ( S 1 ) < β p^j-u(S_1)<\beta p j − u ( S 1 ) < β S 2 ∪ { j } S_2\cup\{j\} S 2 ∪ { j }
Lemma 5.15. Let S 1 ≺ S 2 ≺ ⋯ ≺ S k S_1 \prec S_2 \prec\cdots\prec S_k S 1 ≺ S 2 ≺ ⋯ ≺ S k S i ∪ S j S_i \cup S_j S i ∪ S j i , j i,j i , j ⋃ i = 1 k S i \bigcup_{i=1}^k S_i ⋃ i = 1 k S i k ≥ 2 k \ge2 k ≥ 2
Proof. By Lemma 5.1, every adjacent gap satisfies gap ( S i , S i + 1 ) > β \operatorname{gap}(S_i,S_{i+1}) > \beta gap ( S i , S i + 1 ) > β
wd ( ⋃ i = 1 k S i ) − α ( ⋃ i = 1 k S i ) = ∑ i = 1 k [ wd ( S i ) − α ( S i ) ] + ∑ i = 1 k − 1 gap ( S i , S i + 1 ) > − k β + ( k − 1 ) β = − β . \operatorname{wd}\left(\bigcup_{i=1}^k S_i\right)-\alpha\left(\bigcup_{i=1}^k S_i\right)
= \sum_{i=1}^k [\operatorname{wd}(S_i)-\alpha(S_i)] + \sum_{i=1}^{k-1}\operatorname{gap}(S_i,S_{i+1})
> -k\beta+(k-1)\beta=-\beta. wd ( i = 1 ⋃ k S i ) − α ( i = 1 ⋃ k S i ) = i = 1 ∑ k [ wd ( S i ) − α ( S i )] + i = 1 ∑ k − 1 gap ( S i , S i + 1 ) > − k β + ( k − 1 ) β = − β . Thus the union is not tight.
Lemma 5.16. If S S S S ′ S' S ′ S ′ = S ∪ { j } S'=S\cup\{j\} S ′ = S ∪ { j } F \mathcal{F} F
α j = { p j − u ( S ) if p j > u ( S ) , ℓ ( S ) − p j if p j < ℓ ( S ) , 0 otherwise. \alpha_j =
\begin{cases}
p^j-u(S) & \text{if }p^j>u(S),\\
\ell(S)-p^j & \text{if }p^j<\ell(S),\\
0 & \text{otherwise.}
\end{cases} α j = ⎩ ⎨ ⎧ p j − u ( S ) ℓ ( S ) − p j 0 if p j > u ( S ) , if p j < ℓ ( S ) , otherwise. Moreover, 0 ≤ α j < β 0\le\alpha_j<\beta 0 ≤ α j < β
Proof. Suppose p j > u ( S ) p^j>u(S) p j > u ( S ) S ′ S' S ′ S S S wd ( S ′ ) − α ˉ ( S ′ ) = − β ˉ \operatorname{wd}(S')-\bar{\alpha}(S')=-\bar{\beta} wd ( S ′ ) − α ˉ ( S ′ ) = − β ˉ wd ( S ) − α ˉ ( S ) = − β \operatorname{wd}(S)-\bar{\alpha}(S)=-\beta wd ( S ) − α ˉ ( S ) = − β S ′ = S ∪ { j } S'=S\cup\{j\} S ′ = S ∪ { j } α ˉ j = wd ( S ′ ) − wd ( S ) = p j − u ( S ) \bar{\alpha}_j=\operatorname{wd}(S')-\operatorname{wd}(S)=p^j-u(S) α ˉ j = wd ( S ′ ) − wd ( S ) = p j − u ( S ) ℓ ( S ′ ) = ℓ ( S ) \ell(S')=\ell(S) ℓ ( S ′ ) = ℓ ( S )
The argument for the case p j < ℓ ( S ) p^j<\ell(S) p j < ℓ ( S )
Now suppose inserting j j j S S S wd ( S ′ ) = wd ( S ∪ { j } ) = wd ( S ) \operatorname{wd}(S')=\operatorname{wd}(S\cup\{j\})=\operatorname{wd}(S) wd ( S ′ ) = wd ( S ∪ { j }) = wd ( S ) S ′ S' S ′ S S S α j = wd ( S ′ ) − wd ( S ) = 0 \alpha_j=\operatorname{wd}(S')-\operatorname{wd}(S)=0 α j = wd ( S ′ ) − wd ( S ) = 0 α j ≥ 0 \alpha_j\ge0 α j ≥ 0 α j = β \alpha_j=\beta α j = β { j } \{j\} { j } j j j S ′ S' S ′ α j < β \alpha_j<\beta α j < β
Theorem 5.24. When d = 1 d=1 d = 1 B B B O ( n 2 log 2 n ) O(n^2\log^2 n) O ( n 2 log 2 n )
Proof. First check the trivial inequalities w ≥ 0 w\ge0 w ≥ 0 0 ≤ z i ≤ 1 0\le z_i\le1 0 ≤ z i ≤ 1
The lower bounds in (MCF) can be removed by the standard flow shift. Let π v \pi_v π v π u − π v ≤ c u v \pi_u-\pi_v\le c_{uv} π u − π v ≤ c uv ( u , v ) (u,v) ( u , v ) α i : = π i + − π i − \alpha_i:=\pi_{i^+}-\pi_{i^-} α i := π i + − π i − β : = π t − π s \beta:=\pi_t-\pi_s β := π t − π s α i ≥ 0 \alpha_i\ge0 α i ≥ 0 s → i − → i + → t s\to i^-\to i^+\to t s → i − → i + → t β ≥ 0 \beta\ge0 β ≥ 0 [ l , r ] [l,r] [ l , r ]
∑ i = l r α i − β = ( π s − π l − ) + ∑ i = l r − 1 ( π i + − π ( i + 1 ) − ) + ( π r + − π t ) \sum_{i=l}^{r}\alpha_i-\beta=(\pi_s-\pi_{l^-})+\sum_{i=l}^{r-1}(\pi_{i^+}-\pi_{(i+1)^-})+(\pi_{r^+}-\pi_t) i = l ∑ r α i − β = ( π s − π l − ) + i = l ∑ r − 1 ( π i + − π ( i + 1 ) − ) + ( π r + − π t ) ≤ ∑ i = l r − 1 ( p i + 1 − p i ) = p r − p l . \le\sum_{i=l}^{r-1}(p_{i+1}-p_i)=p_r-p_l. ≤ i = l ∑ r − 1 ( p i + 1 − p i ) = p r − p l . Thus ( α , β ) (\alpha,\beta) ( α , β ) ∑ i = 1 n z ^ i α i − β \sum_{i=1}^n \hat{z}_i\alpha_i-\beta ∑ i = 1 n z ^ i α i − β
reduced costs is standard in minimum-cost flow. See [18 ] as an example. Hence w − α ⊤ z ≥ − β w-\alpha^{\top}z\ge-\beta w − α ⊤ z ≥ − β
The network has O ( n ) O(n) O ( n ) O ( n 2 log 2 n ) O(n^2\log^2 n) O ( n 2 log 2 n ) [18 ] .
Repeated Coordinates
We now remove the assumption that the one-dimensional coordinates are distinct. Reindex the points, if necessary, so that p 1 ≤ p 2 ≤ ⋯ ≤ p n p^1\le p^2\le\cdots\le p^n p 1 ≤ p 2 ≤ ⋯ ≤ p n ξ 1 < ξ 2 < ⋯ < ξ m \xi^1<\xi^2<\cdots<\xi^m ξ 1 < ξ 2 < ⋯ < ξ m C r : = { i ∈ [ n ] : p i = ξ r } C_r:=\{i\in[n]:p^i=\xi^r\} C r := { i ∈ [ n ] : p i = ξ r } r ∈ [ m ] r\in[m] r ∈ [ m ] [ n ] = C 1 ∪ ˙ C 2 ∪ ˙ ⋯ ∪ ˙ C m [n]=C_1\mathbin{\dot\cup}C_2\mathbin{\dot\cup}\cdots\mathbin{\dot\cup}C_m [ n ] = C 1 ∪ ˙ C 2 ∪ ˙ ⋯ ∪ ˙ C m
Define the reduced boxing set on the m m m B ‾ : = { ( w , y ) ∈ R × { 0 , 1 } m : w ≥ wd ( S ( y ) ) } \overline{B}:=\{(w,y)\in\mathbb{R}\times\{0,1\}^m:w\ge\operatorname{wd}(S(y))\} B := {( w , y ) ∈ R × { 0 , 1 } m : w ≥ wd ( S ( y ))} J ⊆ [ m ] J\subseteq[m] J ⊆ [ m ]
wd ( J ) : = { max r ∈ J ξ r − min r ∈ J ξ r , J ≠ ∅ , 0 , J = ∅ . \operatorname{wd}(J):=
\begin{cases}
\max_{r\in J}\xi^r-\min_{r\in J}\xi^r, & J\ne\varnothing,\\
0, & J=\varnothing.
\end{cases} wd ( J ) := { max r ∈ J ξ r − min r ∈ J ξ r , 0 , J = ∅ , J = ∅ . The set B ‾ \overline{B} B ξ 1 < ⋯ < ξ m \xi^1<\cdots<\xi^m ξ 1 < ⋯ < ξ m conv ( B ‾ ) \operatorname{conv}(\overline{B}) conv ( B )
Class activation and multiplicity
For each class C r C_r C r y r y_r y r
R : = { ( w , z , y ) ∈ R 1 + n + m : ( w , y ) ∈ conv ( B ‾ ) , z i ≤ y r i ∈ C r , r ∈ [ m ] , y r ≤ ∑ i ∈ C r z i r ∈ [ m ] , 0 ≤ z i ≤ 1 i ∈ [ n ] } . (24) \mathcal{R}:=\left\{(w,z,y)\in\mathbb{R}^{1+n+m}:
\begin{aligned}
&(w,y)\in\operatorname{conv}(\overline{B}),\\
&z_i\le y_r && i\in C_r,\ r\in[m],\\
&y_r\le\sum_{i\in C_r}z_i && r\in[m],\\
&0\le z_i\le1 && i\in[n]
\end{aligned}
\right\}. \tag*{(24)} R := ⎩ ⎨ ⎧ ( w , z , y ) ∈ R 1 + n + m : ( w , y ) ∈ conv ( B ) , z i ≤ y r y r ≤ i ∈ C r ∑ z i 0 ≤ z i ≤ 1 i ∈ C r , r ∈ [ m ] , r ∈ [ m ] , i ∈ [ n ] ⎭ ⎬ ⎫ . (24) For binary z z z y r = max i ∈ C r z i y_r=\max_{i\in C_r}z_i y r = max i ∈ C r z i y r y_r y r C r C_r C r
Lemma C.1. The original boxing polyhedron (with repeated coordinates) satisfies conv ( B ) = proj w , z ( R ) \operatorname{conv}(B)=\operatorname{proj}_{w,z}(\mathcal{R}) conv ( B ) = proj w , z ( R )
Proof. Let ( w , z ) ∈ conv ( B ) (w,z)\in\operatorname{conv}(B) ( w , z ) ∈ conv ( B ) z z z y ∈ { 0 , 1 } m y\in\{0,1\}^m y ∈ { 0 , 1 } m ( w , z , y ) ∈ R (w,z,y)\in\mathcal{R} ( w , z , y ) ∈ R y r : = max i ∈ C r z i y_r:=\max_{i\in C_r}z_i y r := max i ∈ C r z i r ∈ [ m ] r\in[m] r ∈ [ m ] y ∈ { 0 , 1 } m y\in\{0,1\}^m y ∈ { 0 , 1 } m wd ( S ( z ) ) = wd ( S ( y ) ) \operatorname{wd}(S(z))=\operatorname{wd}(S(y)) wd ( S ( z )) = wd ( S ( y )) B B B R \mathcal{R} R R \mathcal{R} R conv ( B ) ⊆ proj w , z ( R ) \operatorname{conv}(B)\subseteq\operatorname{proj}_{w,z}(\mathcal{R}) conv ( B ) ⊆ proj w , z ( R )
For the reverse inclusion, take ( w , z , y ) ∈ R (w,z,y)\in\mathcal{R} ( w , z , y ) ∈ R ( w , y ) ∈ conv ( B ‾ ) (w,y)\in\operatorname{conv}(\overline{B}) ( w , y ) ∈ conv ( B ) z z z
The polytope { x ∈ [ 0 , 1 ] C r : ∑ i ∈ C r x i ≥ 1 } \{x\in[0,1]^{C_r}:\sum_{i\in C_r}x_i\ge1\} { x ∈ [ 0 , 1 ] C r : ∑ i ∈ C r x i ≥ 1 } C r C_r C r T ⊆ C r T\subseteq C_r T ⊆ C r x x x y ˉ \bar{y} y ˉ ( w , y ) (w,y) ( w , y ) z ˉ \bar{z} z ˉ C r C_r C r
if y ˉ r = 0 \bar{y}_r=0 y ˉ r = 0 z ˉ i = 0 \bar{z}_i=0 z ˉ i = 0 ∀ i ∈ C r \forall i\in C_r ∀ i ∈ C r
if y ˉ r = 1 \bar{y}_r=1 y ˉ r = 1 T r ⊆ C r T_r\subseteq C_r T r ⊆ C r
z ˉ i = { 1 , i ∈ T r , 0 , i ∈ C r ∖ T r . \bar{z}_i =
\begin{cases}
1, & i\in T_r,\\
0, & i\in C_r\setminus T_r.
\end{cases} z ˉ i = { 1 , 0 , i ∈ T r , i ∈ C r ∖ T r . Thus, for every class C r C_r C r y ˉ r = 1 \bar{y}_r=1 y ˉ r = 1 ∑ i ∈ C r z ˉ i ≥ 1 \sum_{i\in C_r}\bar{z}_i\ge1 ∑ i ∈ C r z ˉ i ≥ 1 y ˉ \bar{y} y ˉ z ˉ \bar{z} z ˉ
Since all points in C r C_r C r ξ r \xi_r ξ r wd ( S ( z ˉ ) ) = wd ‾ ( S ( y ˉ ) ) \operatorname{wd}(S(\bar{z}))=\overline{\operatorname{wd}}(S(\bar{y})) wd ( S ( z ˉ )) = wd ( S ( y ˉ )) ( w , z ) (w,z) ( w , z ) B B B ( w , z ) ∈ conv ( B ) (w,z)\in\operatorname{conv}(B) ( w , z ) ∈ conv ( B )
Lifting facets from the distinct-coordinate instance
Let
w − ∑ r = 1 m α ˉ r y r ≥ − β . (25) w-\sum_{r=1}^{m}\bar{\alpha}_r y_r\ge-\beta. \tag*{(25)} w − r = 1 ∑ m α ˉ r y r ≥ − β . (25) be a nontrivial facet of conv ( B ‾ ) \operatorname{conv}(\overline{B}) conv ( B ) α ˉ r ≥ 0 \bar{\alpha}_r\ge0 α ˉ r ≥ 0 r ∈ [ m ] r\in[m] r ∈ [ m ]
For each r ∈ [ m ] r\in[m] r ∈ [ m ] ρ r ∈ C r \rho_r\in C_r ρ r ∈ C r
w − ∑ r = 1 m α ˉ r z ρ r ≥ − β . (26) w-\sum_{r=1}^{m}\bar{\alpha}_r z_{\rho_r}\ge-\beta. \tag*{(26)} w − r = 1 ∑ m α ˉ r z ρ r ≥ − β . (26) Lemma C.2. Every representative lift (23) of a nontrivial facet (22) is facet-defining for conv ( B ) \operatorname{conv}(B) conv ( B )
Proof. We first prove validity. Let S ⊆ [ n ] S\subseteq[n] S ⊆ [ n ] J ( S ) : = { r ∈ [ m ] : S ∩ C r ≠ ∅ } J(S):=\{r\in[m]:S\cap C_r\ne\varnothing\} J ( S ) := { r ∈ [ m ] : S ∩ C r = ∅ } wd ( S ) = wd ( J ( S ) ) \operatorname{wd}(S)=\operatorname{wd}(J(S)) wd ( S ) = wd ( J ( S )) ∑ r = 1 m α ˉ r χ ρ r S ≤ ∑ r ∈ J ( S ) α ˉ r \sum_{r=1}^{m}\bar{\alpha}_r\chi^S_{\rho_r}\le\sum_{r\in J(S)}\bar{\alpha}_r ∑ r = 1 m α ˉ r χ ρ r S ≤ ∑ r ∈ J ( S ) α ˉ r α ˉ ≥ 0 \bar{\alpha}\ge0 α ˉ ≥ 0
wd ( S ) − ∑ r = 1 m α ˉ r χ ρ r S ≥ wd ( J ( S ) ) − ∑ r ∈ J ( S ) α ˉ r ≥ − β . \operatorname{wd}(S)-\sum_{r=1}^{m}\bar{\alpha}_r\chi^S_{\rho_r}
\ge\operatorname{wd}(J(S))-\sum_{r\in J(S)}\bar{\alpha}_r
\ge-\beta. wd ( S ) − r = 1 ∑ m α ˉ r χ ρ r S ≥ wd ( J ( S )) − r ∈ J ( S ) ∑ α ˉ r ≥ − β . Hence (23) is valid.
It remains to prove facetness. Fix any pair of a nontrivial facet (22) of conv ( B ‾ ) \operatorname{conv}(\overline{B}) conv ( B ) conv ( B ‾ ) \operatorname{conv}(\overline{B}) conv ( B ) m + 1 m+1 m + 1 ( wd ( J s ) , χ J s ) (\operatorname{wd}(J^s),\chi^{J^s}) ( wd ( J s ) , χ J s ) J s ⊆ 2 [ m ] J^s\subseteq2^{[m]} J s ⊆ 2 [ m ] s = 0 , … , m s=0,\ldots,m s = 0 , … , m s s s R s : = { ρ r ∈ C r : r ∈ J s } R^s:=\{\rho_r\in C_r:r\in J^s\} R s := { ρ r ∈ C r : r ∈ J s } wd ( R s ) = wd ( J s ) \operatorname{wd}(R^s)=\operatorname{wd}(J^s) wd ( R s ) = wd ( J s ) ( wd ( R s ) , χ R s ) (\operatorname{wd}(R^s),\chi^{R^s}) ( wd ( R s ) , χ R s ) s = 0 , … , m s=0,\ldots,m s = 0 , … , m ( w , z ρ 1 , … , z ρ m ) (w,z_{\rho_1},\ldots,z_{\rho_m}) ( w , z ρ 1 , … , z ρ m ) m + 1 m+1 m + 1
Now fix i ∈ C r ∖ { ρ r } i\in C_r\setminus\{\rho_r\} i ∈ C r ∖ { ρ r } r r r J s ⊆ 2 [ m ] J^s\subseteq2^{[m]} J s ⊆ 2 [ m ] conv ( B ‾ ) \operatorname{conv}(\overline{B}) conv ( B ) s s s R s ∪ { i } R^s\cup\{i\} R s ∪ { i } R s R^s R s i i i ρ r \rho_r ρ r ξ r \xi^r ξ r z i z_i z i ( wd ( R s ) , χ R s ∪ { i } ) (\operatorname{wd}(R^s),\chi^{R^s\cup\{i\}}) ( wd ( R s ) , χ R s ∪ { i } ) ( wd ( R s ) , χ R s ) (\operatorname{wd}(R^s),\chi^{R^s}) ( wd ( R s ) , χ R s ) z i z_i z i ( wd ( R s ) , χ R s ∪ { i } ) (\operatorname{wd}(R^s), \chi^{R^s\cup\{i\}}) ( wd ( R s ) , χ R s ∪ { i } ) i ∈ C r ∖ { ρ r } i \in C_r \setminus\{\rho_r\} i ∈ C r ∖ { ρ r } n − m n-m n − m m + 1 m+1 m + 1 n + 1 n+1 n + 1 conv ( B ) \operatorname{conv}(B) conv ( B )
Complete facet description
We can now extend the distinct-coordinate description to arbitrary one-dimensional instances.
Theorem C.3. Let C 1 , … , C m C_1,\ldots,C_m C 1 , … , C m ξ 1 < ⋯ < ξ m \xi^1 < \cdots< \xi^m ξ 1 < ⋯ < ξ m conv ( B ‾ ) \operatorname{conv}(\overline{B}) conv ( B ) r r r α ‾ r > 0 \overline{\alpha}_r > 0 α r > 0 ρ r ∈ C r \rho_r \in C_r ρ r ∈ C r C r C_r C r ρ r ∈ C r \rho_r \in C_r ρ r ∈ C r C r C_r C r conv ( B ) \operatorname{conv}(B) conv ( B )
Consequently, conv ( B ) \operatorname{conv}(B) conv ( B ) w ≥ 0 w \ge0 w ≥ 0 0 ≤ z i ≤ 1 0 \le z_i \le1 0 ≤ z i ≤ 1 i ∈ [ n ] i \in[n] i ∈ [ n ]
Proof. Lemma C.2 shows that every displayed representative lift is facet-defining and valid for conv ( B ) \operatorname{conv}(B) conv ( B )
It remains to show that these inequalities describe the entire polyhedron. Suppose ( w , z ) (w,z) ( w , z ) w ≥ 0 w \ge0 w ≥ 0 conv ( B ‾ ) \operatorname{conv}(\overline{B}) conv ( B ) r ∈ [ m ] r \in[m] r ∈ [ m ] y r : = max i ∈ C r z i y_r := \max_{i\in C_r} z_i y r := max i ∈ C r z i z i ≤ y r z_i \le y_r z i ≤ y r i ∈ C r i \in C_r i ∈ C r y r ≤ ∑ i ∈ C r z i y_r \le\sum_{i\in C_r} z_i y r ≤ ∑ i ∈ C r z i
Consider an arbitrary nontrivial facet for the reduced polyhedron conv ( B ‾ ) \operatorname{conv}(\overline{B}) conv ( B ) w − ∑ r = 1 m α ‾ r y r ≥ − β w-\sum_{r=1}^m \overline{\alpha}_r y_r \ge-\beta w − ∑ r = 1 m α r y r ≥ − β r r r ρ r ∈ arg max i ∈ C r z i \rho_r \in\arg\max_{i\in C_r} z_i ρ r ∈ arg max i ∈ C r z i ( w , z ) (w,z) ( w , z )
w − ∑ r = 1 m α ‾ r z ρ r = w − ∑ r = 1 m α ‾ r y r ≥ − β . w-\sum_{r=1}^m \overline{\alpha}_r z_{\rho_r}
=
w-\sum_{r=1}^m \overline{\alpha}_r y_r
\ge-\beta. w − r = 1 ∑ m α r z ρ r = w − r = 1 ∑ m α r y r ≥ − β . Thus ( w , y ) (w,y) ( w , y ) conv ( B ‾ ) \operatorname{conv}(\overline{B}) conv ( B ) ( w , y ) ∈ conv ( B ‾ ) (w,y) \in\operatorname{conv}(\overline{B}) ( w , y ) ∈ conv ( B ) ( w , z ) ∈ conv ( B ) (w,z) \in\operatorname{conv}(B) ( w , z ) ∈ conv ( B )
Hence the displayed inequalities form an exact description of conv ( B ) \operatorname{conv}(B) conv ( B ) conv ( B ) \operatorname{conv}(B) conv ( B )
An immediate structural consequence is worth recording.
Corollary C.4. Let w − α ⊤ z ≥ − β w-\alpha^\top z \ge-\beta w − α ⊤ z ≥ − β conv ( B ) \operatorname{conv}(B) conv ( B ) C r C_r C r C r C_r C r α ‾ r \overline{\alpha}_r α r α i = 0 \alpha_i=0 α i = 0 i ∈ C r i \in C_r i ∈ C r ρ r ∈ C r \rho_r \in C_r ρ r ∈ C r α ρ r = α ‾ r > 0 \alpha_{\rho_r}=\overline{\alpha}_r>0 α ρ r = α r > 0 α i = 0 \alpha_i=0 α i = 0 i ∈ C r ∖ { ρ r } i \in C_r\setminus\{\rho_r\} i ∈ C r ∖ { ρ r }
This also gives a direct lifting interpretation of duplicate points.
Remark C.5 (Zero-distance duplicates). Suppose ρ r ∈ C r \rho_r \in C_r ρ r ∈ C r α ‾ r \overline{\alpha}_r α r i ∈ C r ∖ { ρ r } i \in C_r \setminus\{\rho_r\} i ∈ C r ∖ { ρ r } z i z_i z i
Indeed, since the reduced facet is facet-defining, some tight support contains class r r r ρ r \rho_r ρ r S S S ρ r \rho_r ρ r i i i wd ( S ∪ { i } ) = wd ( S ) \operatorname{wd}(S \cup\{i\})=\operatorname{wd}(S) wd ( S ∪ { i }) = wd ( S ) i i i ρ r \rho_r ρ r S S S β \beta β
Theorem C.3 gives a direct extension of Algorithm 1: enumerating all reduced facets and all choices of representatives generates every nontrivial facet of the original repeated-coordinate instance.
Separation with repeated coordinates
The separation algorithm for repeated coordinates follows directly from the distinct-coordinate case. Given a point ( w ^ , z ^ ) (\widehat{w},\widehat{z}) ( w , z ) y ^ r : = max i ∈ C r z ^ i \widehat{y}_r := \max_{i\in C_r}\widehat{z}_i y r := max i ∈ C r z i C r C_r C r ξ 1 < ⋯ < ξ m \xi_1 < \cdots< \xi_m ξ 1 < ⋯ < ξ m ( w ^ , y ^ ) (\widehat{w},\widehat{y}) ( w , y ) ρ r ∈ arg max i ∈ C r z ^ i \rho_r \in\operatorname{arg\,max}_{i\in C_r}\widehat{z}_i ρ r ∈ arg max i ∈ C r z i y r y_r y r z ρ r z_{\rho_r} z ρ r C r C_r C r conv ( B ) \operatorname{conv}(B) conv ( B ) ( w ^ , z ^ ) (\widehat{w},\widehat{z}) ( w , z ) ( w ^ , y ^ ) (\widehat{w},\widehat{y}) ( w , y ) m m m
Computing Facet-admissible Right-hand-sides
Recall that the box-width function wd : 2 [ n ] → R + \operatorname{wd}:2^{[n]} \to\mathbb{R}_+ wd : 2 [ n ] → R + wd ( ∅ ) = wd ( { i } ) = 0 \operatorname{wd}(\varnothing) = \operatorname{wd}(\{i\}) = 0 wd ( ∅ ) = wd ({ i }) = 0 i ∈ [ n ] i \in[n] i ∈ [ n ]
We first show that β S ∗ \beta_S^* β S ∗ [ n ] [n] [ n ]
A parametric partition problem
For any λ ∈ R \lambda\in\mathbb{R} λ ∈ R
H S ( λ ) = min P ∈ Π ( S ) { ∑ A ∈ P ( wd ( A ) + λ ) } . (27) H_S(\lambda) = \min_{\mathcal{P}\in\Pi(S)} \left\{\sum_{A\in\mathcal{P}}\bigl(\operatorname{wd}(A)+\lambda\bigr)\right\}. \tag*{(27)} H S ( λ ) = P ∈ Π ( S ) min { A ∈ P ∑ ( wd ( A ) + λ ) } . (27) The one-block partition { S } \{S\} { S } wd ( S ) + λ \operatorname{wd}(S)+\lambda wd ( S ) + λ H S ( λ ) = wd ( S ) + λ H_S(\lambda) = \operatorname{wd}(S)+\lambda H S ( λ ) = wd ( S ) + λ P \mathcal{P} P
∑ A ∈ P wd ( A ) + ∣ P ∣ λ ≥ wd ( S ) + λ \sum_{A\in\mathcal{P}}\operatorname{wd}(A)+|\mathcal{P}|\lambda\ge\operatorname{wd}(S)+\lambda A ∈ P ∑ wd ( A ) + ∣ P ∣ λ ≥ wd ( S ) + λ ⟺ λ ≥ wd ( S ) − ∑ A ∈ P wd ( A ) ∣ P ∣ − 1 = β S ( P ) . \Longleftrightarrow\quad\lambda\ge\frac{\operatorname{wd}(S)-\sum_{A\in\mathcal{P}}\operatorname{wd}(A)}{|\mathcal{P}|-1} = \beta_S(\mathcal{P}). ⟺ λ ≥ ∣ P ∣ − 1 wd ( S ) − ∑ A ∈ P wd ( A ) = β S ( P ) . Consequently, λ ≥ β S ∗ \lambda\ge\beta_S^* λ ≥ β S ∗ β S ∗ \beta_S^* β S ∗ λ \lambda λ
We next establish a primal-dual characterization of H S ( λ ) H_S(\lambda) H S ( λ )
Lemma D.1 (Primal-dual characterization). For every λ ∈ R \lambda\in\mathbb{R} λ ∈ R H S ( λ ) = F S ( λ ) H_S(\lambda) = F_S(\lambda) H S ( λ ) = F S ( λ )
F S ( λ ) = max x ∈ R S x ( S ) F_S(\lambda) = \max_{x\in\mathbb{R}^S} x(S) F S ( λ ) = x ∈ R S max x ( S ) s.t. x ( T ) ≤ wd ( T ) + λ , ∅ ≠ T ⊆ S . \text{s.t.}\quad x(T) \le\operatorname{wd}(T)+\lambda,\quad\varnothing\ne T \subseteq S. s.t. x ( T ) ≤ wd ( T ) + λ , ∅ = T ⊆ S . Proof. The dual of ( P λ ) (P_\lambda) ( P λ )
min y ≥ 0 ∑ ∅ ≠ T ⊆ S ( wd ( T ) + λ ) y T s.t. ∑ T ∋ i y T = 1 , i ∈ S . \begin{aligned}
\min_{y\ge0}\quad&\sum_{\varnothing\ne T\subseteq S}(\operatorname{wd}(T)+\lambda)y_T\\
\text{s.t.}\quad&\sum_{T\ni i}y_T=1,\qquad i\in S.
\end{aligned} y ≥ 0 min s.t. ∅ = T ⊆ S ∑ ( wd ( T ) + λ ) y T T ∋ i ∑ y T = 1 , i ∈ S . ( D λ ) (D_\lambda) ( D λ )
The dual constraints are equalities because the primal variables x i x_i x i
Every partition P ∈ Π ( S ) \mathcal{P}\in\Pi(S) P ∈ Π ( S ) ( D λ ) (D_\lambda) ( D λ ) y T = 1 y_T=1 y T = 1 T ∈ P T\in\mathcal{P} T ∈ P y T = 0 y_T=0 y T = 0 ( D λ ) (D_\lambda) ( D λ ) S S S ( D λ ) (D_\lambda) ( D λ )
Among all optimal solutions of ( D λ ) (D_\lambda) ( D λ ) y ∗ y^* y ∗ ∑ ∅ ≠ T ⊆ S ∣ T ∣ 2 y T \sum_{\varnothing\ne T\subseteq S}|T|^2y_T ∑ ∅ = T ⊆ S ∣ T ∣ 2 y T ( D λ ) (D_\lambda) ( D λ )
We claim that the support L = { T ⊆ S : y T ∗ > 0 } \mathcal{L}=\{T\subseteq S:y_T^*>0\} L = { T ⊆ S : y T ∗ > 0 } A , B ∈ L A,B\in\mathcal{L} A , B ∈ L A ∩ B A\cap B A ∩ B A ∖ B A\setminus B A ∖ B B ∖ A B\setminus A B ∖ A
Let δ = min { y A ∗ , y B ∗ } > 0 \delta=\min\{y_A^*,y_B^*\}>0 δ = min { y A ∗ , y B ∗ } > 0 y A ∗ y_A^* y A ∗ y B ∗ y_B^* y B ∗ δ \delta δ y A ∩ B ∗ y_{A\cap B}^* y A ∩ B ∗ y A ∪ B ∗ y_{A\cup B}^* y A ∪ B ∗ δ \delta δ χ A + χ B = χ A ∩ B + χ A ∪ B \chi^A+\chi^B=\chi^{A\cap B}+\chi^{A\cup B} χ A + χ B = χ A ∩ B + χ A ∪ B
wd ( A ) + wd ( B ) + 2 λ ≥ wd ( A ∩ B ) + wd ( A ∪ B ) + 2 λ . \operatorname{wd}(A)+\operatorname{wd}(B)+2\lambda\ge\operatorname{wd}(A\cap B)+\operatorname{wd}(A\cup B)+2\lambda. wd ( A ) + wd ( B ) + 2 λ ≥ wd ( A ∩ B ) + wd ( A ∪ B ) + 2 λ . Thus the objective value does not increase. Since y ∗ y^* y ∗ ∑ T ∣ T ∣ 2 y T \sum_T|T|^2y_T ∑ T ∣ T ∣ 2 y T
δ ( ∣ A ∩ B ∣ 2 + ∣ A ∪ B ∣ 2 − ∣ A ∣ 2 − ∣ B ∣ 2 ) = 2 δ ∣ A ∖ B ∣ ∣ B ∖ A ∣ > 0 , \delta\left(|A\cap B|^2+|A\cup B|^2-|A|^2-|B|^2\right)=2\delta|A\setminus B||B\setminus A|>0, δ ( ∣ A ∩ B ∣ 2 + ∣ A ∪ B ∣ 2 − ∣ A ∣ 2 − ∣ B ∣ 2 ) = 2 δ ∣ A ∖ B ∣∣ B ∖ A ∣ > 0 , contradicting the choice of y ∗ y^* y ∗ L \mathcal{L} L
Restrict ( D λ ) (D_\lambda) ( D λ ) L \mathcal{L} L [ χ T ] T ∈ L [\chi^T]_{T\in\mathcal{L}} [ χ T ] T ∈ L L \mathcal{L} L
Extending this solution by zero outside L \mathcal{L} L ( D λ ) (D_\lambda) ( D λ ) S S S ( D λ ) (D_\lambda) ( D λ ) H S ( λ ) H_S(\lambda) H S ( λ ) F S ( λ ) = H S ( λ ) F_S(\lambda)=H_S(\lambda) F S ( λ ) = H S ( λ )
Existence of facet-admissible partitions
We now relate β S ∗ \beta_S^* β S ∗ conv ( B ) \operatorname{conv}(B) conv ( B )
Recall that a partition P = { S 1 , … , S k } \mathcal{P}=\{S_1,\ldots,S_k\} P = { S 1 , … , S k } S S S k ≥ 2 k\ge2 k ≥ 2 w − α ⊤ z ≥ − β w-\alpha^\top z\ge-\beta w − α ⊤ z ≥ − β conv ( B ) \operatorname{conv}(B) conv ( B ) S S S S i S_i S i
Theorem 6.7. For every S ⊆ [ n ] S\subseteq[n] S ⊆ [ n ] ∣ S ∣ ≥ 2 |S|\ge2 ∣ S ∣ ≥ 2 P ∈ Π ( S ) \mathcal{P}\in\Pi(S) P ∈ Π ( S ) β S ∗ \beta_S^* β S ∗ S S S
Proof. Fix S ⊆ [ n ] S\subseteq[n] S ⊆ [ n ] ∣ S ∣ ≥ 2 |S|\ge2 ∣ S ∣ ≥ 2 β S ∗ ≥ wd ( S ) / ( ∣ S ∣ − 1 ) ≥ 0 \beta_S^*\ge\operatorname{wd}(S)/(|S|-1)\ge0 β S ∗ ≥ wd ( S ) / ( ∣ S ∣ − 1 ) ≥ 0 β S ∗ \beta_S^* β S ∗ H S ( β S ∗ ) = wd ( S ) + β S ∗ H_S(\beta_S^*)=\operatorname{wd}(S)+\beta_S^* H S ( β S ∗ ) = wd ( S ) + β S ∗ ( P λ ) (P_\lambda) ( P λ ) λ = β S ∗ \lambda=\beta_S^* λ = β S ∗ x ∈ R S x\in\mathbb{R}^S x ∈ R S
x ( T ) ≤ wd ( T ) + β S ∗ , ∅ ≠ T ⊆ S , x(T)\le\operatorname{wd}(T)+\beta_S^*,\qquad\varnothing\ne T\subseteq S, x ( T ) ≤ wd ( T ) + β S ∗ , ∅ = T ⊆ S , x ( S ) = wd ( S ) + β S ∗ . x(S)=\operatorname{wd}(S)+\beta_S^*. x ( S ) = wd ( S ) + β S ∗ . Extend x x x α ∈ R n \alpha\in\mathbb{R}^n α ∈ R n α i = x i \alpha_i=x_i α i = x i i ∈ S i\in S i ∈ S α i = 0 \alpha_i=0 α i = 0 w − α ⊤ z ≥ − β S ∗ w-\alpha^{\top}z\geq-\beta_S^* w − α ⊤ z ≥ − β S ∗ conv ( B ) \operatorname{conv}(B) conv ( B )
Take any T ⊆ [ n ] T\subseteq[n] T ⊆ [ n ] T ∩ S ≠ ∅ T\cap S\ne\varnothing T ∩ S = ∅
α ( T ) = x ( T ∩ S ) ≤ wd ( T ∩ S ) + β S ∗ ≤ wd ( T ) + β S ∗ . \alpha(T)=x(T\cap S)\leq\operatorname{wd}(T\cap S)+\beta_S^*\leq\operatorname{wd}(T)+\beta_S^*. α ( T ) = x ( T ∩ S ) ≤ wd ( T ∩ S ) + β S ∗ ≤ wd ( T ) + β S ∗ . If T ∩ S = ∅ T\cap S=\varnothing T ∩ S = ∅ α ( T ) = 0 ≤ wd ( T ) + β S ∗ \alpha(T)=0\leq\operatorname{wd}(T)+\beta_S^* α ( T ) = 0 ≤ wd ( T ) + β S ∗ S S S
Now let P = { S 1 , … , S k } \mathcal{P}=\{S_1,\ldots,S_k\} P = { S 1 , … , S k } β S ∗ \beta_S^* β S ∗ β S ∗ \beta_S^* β S ∗
wd ( S ) + β S ∗ = ∑ i = 1 k ( wd ( S i ) + β S ∗ ) . \operatorname{wd}(S)+\beta_S^*=\sum_{i=1}^{k}\left(\operatorname{wd}(S_i)+\beta_S^*\right). wd ( S ) + β S ∗ = i = 1 ∑ k ( wd ( S i ) + β S ∗ ) . Since the S i S_i S i S S S ∑ i = 1 k x ( S i ) = x ( S ) \sum_{i=1}^{k}x(S_i)=x(S) ∑ i = 1 k x ( S i ) = x ( S ) S S S
0 = ∑ i = 1 k ( wd ( S i ) + β S ∗ − x ( S i ) ) . 0=\sum_{i=1}^{k}\left(\operatorname{wd}(S_i)+\beta_S^*-x(S_i)\right). 0 = i = 1 ∑ k ( wd ( S i ) + β S ∗ − x ( S i ) ) . Every summand is nonnegative by feasibility of x x x
x ( S i ) − β S ∗ = wd ( S i ) , i = 1 , … , k . x(S_i)-\beta_S^*=\operatorname{wd}(S_i),\qquad i=1,\ldots,k. x ( S i ) − β S ∗ = wd ( S i ) , i = 1 , … , k . Thus S , S 1 , … , S k S,S_1,\ldots,S_k S , S 1 , … , S k w − α ⊤ z ≥ − β S ∗ w-\alpha^{\top}z\geq-\beta_S^* w − α ⊤ z ≥ − β S ∗ P \mathcal{P} P
A polynomial-time algorithm for β S ∗ \beta_S^* β S ∗
By the parametrization in Section D.1, we need to search through λ \lambda λ λ \lambda λ H S ( λ ) = wd ( S ) + λ H_S(\lambda)=\operatorname{wd}(S)+\lambda H S ( λ ) = wd ( S ) + λ H S ( λ ) H_S(\lambda) H S ( λ ) β S ∗ \beta_S^* β S ∗
Lemma D.2. For any fixed λ ∈ R \lambda\in\mathbb{R} λ ∈ R H S ( λ ) H_S(\lambda) H S ( λ ) ∣ S ∣ |S| ∣ S ∣
Proof. Write S = { s 1 , … , s m } S=\{s_1,\ldots,s_m\} S = { s 1 , … , s m } E j = { s 1 , … , s j } E_j=\{s_1,\ldots,s_j\} E j = { s 1 , … , s j } E 0 = ∅ E_0=\varnothing E 0 = ∅
We construct a feasible solution of ( P λ ) (P_\lambda) ( P λ ) j j j x s 1 , … , x s j − 1 x_{s_1},\ldots,x_{s_{j-1}} x s 1 , … , x s j − 1
x s j = min A ⊆ E j − 1 { wd ( A ∪ { s j } ) + λ − x ( A ) } . (28) x_{s_j}=\min_{A\subseteq E_{j-1}}\{\operatorname{wd}(A\cup\{s_j\})+\lambda-x(A)\}. \tag*{(28)} x s j = A ⊆ E j − 1 min { wd ( A ∪ { s j }) + λ − x ( A )} . (28) This is a standard submodular-function minimization problem. Indeed, the function A ↦ wd ( A ∪ { s j } ) A\mapsto\operatorname{wd}(A\cup\{s_j\}) A ↦ wd ( A ∪ { s j }) E j − 1 E_{j-1} E j − 1 s j s_j s j x ( A ) x(A) x ( A )
We first verify that the resulting vector x x x ( P λ ) (P_\lambda) ( P λ ) T ⊆ S T\subseteq S T ⊆ S s j s_j s j T T T T = A ∪ { s j } T=A\cup\{s_j\} T = A ∪ { s j } A ⊆ E j − 1 A\subseteq E_{j-1} A ⊆ E j − 1
x ( T ) = x ( A ) + x s j ≤ x ( A ) + wd ( A ∪ { s j } ) + λ − x ( A ) = wd ( T ) + λ . x(T)=x(A)+x_{s_j}\leq x(A)+\operatorname{wd}(A\cup\{s_j\})+\lambda-x(A)=\operatorname{wd}(T)+\lambda. x ( T ) = x ( A ) + x s j ≤ x ( A ) + wd ( A ∪ { s j }) + λ − x ( A ) = wd ( T ) + λ . Next, let A j A_j A j T j = A j ∪ { s j } T_j=A_j\cup\{s_j\} T j = A j ∪ { s j }
x ( T j ) = x ( A j ) + x s j = wd ( T j ) + λ . x(T_j)=x(A_j)+x_{s_j}=\operatorname{wd}(T_j)+\lambda. x ( T j ) = x ( A j ) + x s j = wd ( T j ) + λ . Thus T j T_j T j ( P λ ) (P_\lambda) ( P λ ) s j ∈ T j s_j \in T_j s j ∈ T j j j j ⋃ j = 1 m T j = S \bigcup_{j=1}^m T_j = S ⋃ j = 1 m T j = S
We claim that the union of any two intersecting tight sets is also tight. Indeed, suppose A A A B B B A ∩ B ≠ ∅ A \cap B \ne\emptyset A ∩ B = ∅ x x x
x ( A ) + x ( B ) = wd ( A ) + wd ( B ) + 2 λ ≥ wd ( A ∪ B ) + wd ( A ∩ B ) + 2 λ ≥ x ( A ∪ B ) + x ( A ∩ B ) = x ( A ) + x ( B ) . \begin{aligned}
x(A) + x(B) &= \operatorname{wd}(A) + \operatorname{wd}(B) + 2\lambda\\
&\ge\operatorname{wd}(A \cup B) + \operatorname{wd}(A \cap B) + 2\lambda\\
&\ge x(A \cup B) + x(A \cap B) \\
&= x(A) + x(B).
\end{aligned} x ( A ) + x ( B ) = wd ( A ) + wd ( B ) + 2 λ ≥ wd ( A ∪ B ) + wd ( A ∩ B ) + 2 λ ≥ x ( A ∪ B ) + x ( A ∩ B ) = x ( A ) + x ( B ) . Hence all inequalities hold at equality, and in particular x ( A ∪ B ) = wd ( A ∪ B ) + λ x(A \cup B) = \operatorname{wd}(A \cup B) + \lambda x ( A ∪ B ) = wd ( A ∪ B ) + λ
Starting with T 1 , … , T m T_1,\ldots,T_m T 1 , … , T m S S S P λ = { B 1 , … , B k } P_\lambda= \{B_1,\ldots,B_k\} P λ = { B 1 , … , B k } S S S
Consequently,
x ( S ) = ∑ i = 1 k x ( B i ) = ∑ i = 1 k ( wd ( B i ) + λ ) ≥ H S ( λ ) . x(S) = \sum_{i=1}^{k} x(B_i) = \sum_{i=1}^{k} \bigl(\operatorname{wd}(B_i) + \lambda\bigr) \ge H_S(\lambda). x ( S ) = i = 1 ∑ k x ( B i ) = i = 1 ∑ k ( wd ( B i ) + λ ) ≥ H S ( λ ) . On the other hand, for any partition Q ∈ Π ( S ) Q \in\Pi(S) Q ∈ Π ( S ) x x x
x ( S ) = ∑ A ∈ Q x ( A ) ≤ ∑ A ∈ Q ( wd ( A ) + λ ) . x(S) = \sum_{A \in Q} x(A) \le\sum_{A \in Q} \bigl(\operatorname{wd}(A) + \lambda\bigr). x ( S ) = A ∈ Q ∑ x ( A ) ≤ A ∈ Q ∑ ( wd ( A ) + λ ) . Taking the minimum over Q Q Q x ( S ) ≤ H S ( λ ) x(S) \le H_S(\lambda) x ( S ) ≤ H S ( λ )
H S ( λ ) = x ( S ) = ∑ A ∈ P λ ( wd ( A ) + λ ) . H_S(\lambda) = x(S) = \sum_{A \in P_\lambda} \bigl(\operatorname{wd}(A) + \lambda\bigr). H S ( λ ) = x ( S ) = A ∈ P λ ∑ ( wd ( A ) + λ ) . Equivalently, assigning dual variable y A = 1 y_A = 1 y A = 1 A ∈ P λ A \in P_\lambda A ∈ P λ ( D λ ) (D_\lambda) ( D λ ) x x x
There are m m m (28) , and merging the resulting tight sets takes polynomial time. This proves the result.
The idea behind the parametrization is that the parameter λ \lambda λ λ \lambda λ P P P λ \lambda λ β S ( P ) \beta_S(P) β S ( P ) λ \lambda λ ∣ P ∣ |P| ∣ P ∣
Algorithm 2 accomplishes this using the constructive procedure from Lemma D.2 . In the algorithm, the subroutine MinPartition( S , λ ) (S,\lambda) ( S , λ ) H S ( λ ) H_S(\lambda) H S ( λ ) Lemma D.2 .
Algorithm 2 Computing β S ∗ \beta^{*}_{S} β S ∗
Require: S ⊆ [ n ] S \subseteq[n] S ⊆ [ n ] m = ∣ S ∣ ≥ 2 m = |S| \ge2 m = ∣ S ∣ ≥ 2
Ensure: β S ∗ \beta^{*}_{S} β S ∗
R ← { { i } : i ∈ S } \mathcal{R} \gets\{\{i\}: i \in S\} R ← {{ i } : i ∈ S }
λ ← wd ( S ) / ( m − 1 ) \lambda\gets\operatorname{wd}(S)/(m-1) λ ← wd ( S ) / ( m − 1 )
loop
P ← MinPartition ( S , λ ) \mathcal{P} \gets\operatorname{MinPartition}(S,\lambda) P ← MinPartition ( S , λ )
if ∑ A ∈ P ( wd ( A ) + λ ) = wd ( S ) + λ \sum_{A\in\mathcal{P}}(\operatorname{wd}(A)+\lambda)=\operatorname{wd}(S)+\lambda ∑ A ∈ P ( wd ( A ) + λ ) = wd ( S ) + λ then
return ( λ , R ) (\lambda,\mathcal{R}) ( λ , R )
end if
λ ← wd ( S ) − ∑ A ∈ P wd ( A ) ∣ P ∣ − 1 \lambda\gets\frac{\operatorname{wd}(S)-\sum_{A\in\mathcal{P}}\operatorname{wd}(A)}{|\mathcal{P}|-1} λ ← ∣ P ∣ − 1 wd ( S ) − ∑ A ∈ P wd ( A )
R ← P \mathcal{R} \gets\mathcal{P} R ← P
end loop
Now we are ready to prove Theorem 6.10.
Theorem 6.10. There exists an algorithm that computes β S ∗ \beta^{*}_{S} β S ∗ S ⊆ [ n ] S \subseteq[n] S ⊆ [ n ] ∣ S ∣ ≥ 2 |S| \ge2 ∣ S ∣ ≥ 2 O ( ∣ S ∣ 2 ) O(|S|^{2}) O ( ∣ S ∣ 2 )
Proof. We establish correctness and polynomial termination using the following loop invariants. At the beginning of every iteration, the current parameter λ \lambda λ R \mathcal{R} R
λ = β S ( R ) ≤ β S ∗ , (29) \lambda=\beta_{S}(\mathcal{R})\le\beta^{*}_{S}, \tag*{(29)} λ = β S ( R ) ≤ β S ∗ , (29) ∑ A ∈ Q wd ( A ) + ∣ Q ∣ λ ≥ wd ( S ) + λ ∀ Q ∈ Π ( S ) with ∣ Q ∣ ≥ ∣ R ∣ . (30) \sum_{A\in\mathcal{Q}}\operatorname{wd}(A)+|\mathcal{Q}|\lambda\ge\operatorname{wd}(S)+\lambda\quad\forall\mathcal{Q}\in\Pi(S)\text{ with }|\mathcal{Q}|\ge|\mathcal{R}|. \tag*{(30)} A ∈ Q ∑ wd ( A ) + ∣ Q ∣ λ ≥ wd ( S ) + λ ∀ Q ∈ Π ( S ) with ∣ Q ∣ ≥ ∣ R ∣. (30) Initialization. Initially, R \mathcal{R} R
λ = wd ( S ) m − 1 = β S ( R ) ≤ β S ∗ . \lambda=\frac{\operatorname{wd}(S)}{m-1}=\beta_{S}(\mathcal{R})\le\beta^{*}_{S}. λ = m − 1 wd ( S ) = β S ( R ) ≤ β S ∗ . Thus (26) holds. The only partition of S S S m m m R \mathcal{R} R
∑ A ∈ R wd ( A ) + m λ = m λ = wd ( S ) + λ . \sum_{A\in\mathcal{R}}\operatorname{wd}(A)+m\lambda=m\lambda=\operatorname{wd}(S)+\lambda. A ∈ R ∑ wd ( A ) + mλ = mλ = wd ( S ) + λ . Hence (27) also holds.
Termination criterion. Suppose the subroutine returns a partition P \mathcal{P} P
∑ A ∈ P ( wd ( A ) + λ ) = H S ( λ ) = wd ( S ) + λ . \sum_{A\in\mathcal{P}}(\operatorname{wd}(A)+\lambda)=H_{S}(\lambda)=\operatorname{wd}(S)+\lambda. A ∈ P ∑ ( wd ( A ) + λ ) = H S ( λ ) = wd ( S ) + λ . By construction, λ ≥ β S ∗ \lambda\ge\beta^{*}_{S} λ ≥ β S ∗ λ = β S ∗ \lambda=\beta^{*}_{S} λ = β S ∗ β S ( R ) = λ \beta_{S}(\mathcal{R})=\lambda β S ( R ) = λ R \mathcal{R} R β S ∗ \beta^{*}_{S} β S ∗
Preservation of the invariants. Suppose instead that H S ( λ ) < wd ( S ) + λ H_{S}(\lambda)<\operatorname{wd}(S)+\lambda H S ( λ ) < wd ( S ) + λ P \mathcal{P} P H S ( λ ) H_{S}(\lambda) H S ( λ )
∑ A ∈ P ( wd ( A ) + λ ) = H S ( λ ) < wd ( S ) + λ . \sum_{A\in\mathcal{P}}(\operatorname{wd}(A)+\lambda)=H_{S}(\lambda)<\operatorname{wd}(S)+\lambda. A ∈ P ∑ ( wd ( A ) + λ ) = H S ( λ ) < wd ( S ) + λ . The one-block partition cannot satisfy this strict inequality, so ∣ P ∣ ≥ 2 |\mathcal{P}| \ge2 ∣ P ∣ ≥ 2
λ < wd ( S ) − ∑ A ∈ P wd ( A ) ∣ P ∣ − 1 = : λ ′ . (31) \lambda< \frac{\operatorname{wd}(S)-\sum_{A\in\mathcal{P}}\operatorname{wd}(A)}{|\mathcal{P}|-1} =: \lambda'. \tag*{(31)} λ < ∣ P ∣ − 1 wd ( S ) − ∑ A ∈ P wd ( A ) =: λ ′ . (31) Thus, λ < λ ′ ≤ β S ∗ \lambda< \lambda' \le\beta_S^* λ < λ ′ ≤ β S ∗ β S ∗ \beta_S^* β S ∗ (29) .
We next show (30) . Fix a partition Q \mathcal{Q} Q ∣ Q ∣ ≥ ∣ P ∣ |\mathcal{Q}| \ge|\mathcal{P}| ∣ Q ∣ ≥ ∣ P ∣ P \mathcal{P} P H S ( λ ) H_S(\lambda) H S ( λ )
∑ A ∈ Q ( wd ( A ) + λ ) ≥ ∑ A ∈ P ( wd ( A ) + λ ) . \sum_{A\in\mathcal{Q}}(\operatorname{wd}(A)+\lambda) \ge\sum_{A\in\mathcal{P}}(\operatorname{wd}(A)+\lambda). A ∈ Q ∑ ( wd ( A ) + λ ) ≥ A ∈ P ∑ ( wd ( A ) + λ ) . Since ∣ Q ∣ ≥ ∣ P ∣ |\mathcal{Q}| \ge|\mathcal{P}| ∣ Q ∣ ≥ ∣ P ∣ λ ′ > λ \lambda' > \lambda λ ′ > λ
∑ A ∈ Q ( wd ( A ) + λ ′ ) ≥ ∑ A ∈ P ( wd ( A ) + λ ′ ) = wd ( S ) + λ ′ . \sum_{A\in\mathcal{Q}}(\operatorname{wd}(A)+\lambda') \ge\sum_{A\in\mathcal{P}}(\operatorname{wd}(A)+\lambda') = \operatorname{wd}(S)+\lambda'. A ∈ Q ∑ ( wd ( A ) + λ ′ ) ≥ A ∈ P ∑ ( wd ( A ) + λ ′ ) = wd ( S ) + λ ′ . where the last equality follows from the definition of λ ′ \lambda' λ ′ (31) . This establishes (30) .
Polynomial termination. At every unsuccessful iteration, the returned partition P \mathcal{P} P
∑ A ∈ P wd ( A ) + ∣ P ∣ λ = H S ( λ ) < wd ( S ) + λ . \sum_{A\in\mathcal{P}}\operatorname{wd}(A)+|\mathcal{P}|\lambda= H_S(\lambda) < \operatorname{wd}(S)+\lambda. A ∈ P ∑ wd ( A ) + ∣ P ∣ λ = H S ( λ ) < wd ( S ) + λ . By (30) , this is possible only if ∣ P ∣ < ∣ R ∣ |\mathcal{P}| < |\mathcal{R}| ∣ P ∣ < ∣ R ∣ R \mathcal{R} R
Initially, R \mathcal{R} R m m m m − 2 m-2 m − 2 m m m Lemma D.2 . Thus the total number is at most m ( m − 1 ) = O ( m 2 ) m(m-1)=O(m^2) m ( m − 1 ) = O ( m 2 )
Computing β min \beta_{\min} β m i n
We show that β min \beta_{\min} β m i n
For any λ ∈ R \lambda\in\mathbb{R} λ ∈ R
M ( λ ) = min ∅ ≠ S ⊆ [ n ] { wd ( S ) − λ ( ∣ S ∣ − 1 ) } . (32) M(\lambda)=\min_{\varnothing\ne S\subseteq[n]}\{\operatorname{wd}(S)-\lambda(|S|-1)\}. \tag*{(32)} M ( λ ) = ∅ = S ⊆ [ n ] min { wd ( S ) − λ ( ∣ S ∣ − 1 )} . (32) Since every singleton has zero width, M ( λ ) ≤ 0 M(\lambda)\le0 M ( λ ) ≤ 0 λ \lambda λ β min \beta_{\min} β m i n
M ( λ ) = 0 ⟺ wd ( S ) − λ ( ∣ S ∣ − 1 ) ≥ 0 ∀ S ⊆ [ n ] , ∣ S ∣ ≥ 2 M(\lambda)=0 \Longleftrightarrow\operatorname{wd}(S)-\lambda(|S|-1)\ge0 \quad\forall S\subseteq[n],\ |S|\ge2 M ( λ ) = 0 ⟺ wd ( S ) − λ ( ∣ S ∣ − 1 ) ≥ 0 ∀ S ⊆ [ n ] , ∣ S ∣ ≥ 2 ⟺ λ ≤ min S ⊆ [ n ] ∣ S ∣ ≥ 2 wd ( S ) ∣ S ∣ − 1 \Longleftrightarrow\lambda\le\min_{\substack{S\subseteq[n]\\|S|\ge2}}\frac{\operatorname{wd}(S)}{|S|-1} ⟺ λ ≤ S ⊆ [ n ] ∣ S ∣ ≥ 2 min ∣ S ∣ − 1 wd ( S ) ⟺ λ ≤ β min . (33) \Longleftrightarrow\lambda\le\beta_{\min}. \tag*{(33)} ⟺ λ ≤ β m i n . (33) Thus β min \beta_{\min} β m i n λ \lambda λ M ( λ ) = 0 M(\lambda)=0 M ( λ ) = 0
Although the box-width function is not submodular on all subsets, the parametric problem (32) can be reduced to ordinary submodular-function minimization by fixing an element of the subset.
Lemma E.1. For any fixed λ ∈ R \lambda\in\mathbb{R} λ ∈ R M ( λ ) M(\lambda) M ( λ ) M ( λ ) M(\lambda) M ( λ ) n n n
Proof. For every i ∈ [ n ] i \in[n] i ∈ [ n ]
min A ⊆ [ n ] ∖ { i } { wd ( A ∪ { i } ) − λ ∣ A ∣ } . (34) \min_{A \subseteq[n]\setminus\{i\}} \left\{\operatorname{wd}(A \cup\{i\})-\lambda|A|\right\}. \tag*{(34)} A ⊆ [ n ] ∖ { i } min { wd ( A ∪ { i }) − λ ∣ A ∣ } . (34) We first show that (34) is a submodular-function minimization problem. For any A , B ⊆ [ n ] ∖ { i } A,B \subseteq[n]\setminus\{i\} A , B ⊆ [ n ] ∖ { i } A ∪ { i } A \cup\{i\} A ∪ { i } B ∪ { i } B \cup\{i\} B ∪ { i }
wd ( A ∪ { i } ) + wd ( B ∪ { i } ) ≥ wd ( ( A ∩ B ) ∪ { i } ) + wd ( ( A ∪ B ) ∪ { i } ) . \operatorname{wd}(A \cup\{i\})+\operatorname{wd}(B \cup\{i\}) \ge\operatorname{wd}((A \cap B) \cup\{i\})+\operatorname{wd}((A \cup B) \cup\{i\}). wd ( A ∪ { i }) + wd ( B ∪ { i }) ≥ wd (( A ∩ B ) ∪ { i }) + wd (( A ∪ B ) ∪ { i }) . Hence the function A ↦ wd ( A ∪ { i } ) A \mapsto\operatorname{wd}(A \cup\{i\}) A ↦ wd ( A ∪ { i }) [ n ] ∖ { i } [n]\setminus\{i\} [ n ] ∖ { i } A ↦ λ ∣ A ∣ A \mapsto\lambda|A| A ↦ λ ∣ A ∣
Now every nonempty subset S ⊆ [ n ] S \subseteq[n] S ⊆ [ n ] i i i A = S ∖ { i } A=S\setminus\{i\} A = S ∖ { i }
wd ( S ) − λ ( ∣ S ∣ − 1 ) = wd ( A ∪ { i } ) − λ ∣ A ∣ . \operatorname{wd}(S)-\lambda(|S|-1)=\operatorname{wd}(A \cup\{i\})-\lambda|A|. wd ( S ) − λ ( ∣ S ∣ − 1 ) = wd ( A ∪ { i }) − λ ∣ A ∣. Consequently,
M ( λ ) = min i ∈ [ n ] min A ⊆ [ n ] ∖ { i } { wd ( A ∪ { i } ) − λ ∣ A ∣ } . (35) M(\lambda)=\min_{i\in[n]}\ \min_{A\subseteq[n]\setminus\{i\}}\left\{\operatorname{wd}(A\cup\{i\})-\lambda|A|\right\}. \tag*{(35)} M ( λ ) = i ∈ [ n ] min A ⊆ [ n ] ∖ { i } min { wd ( A ∪ { i }) − λ ∣ A ∣ } . (35) Thus M ( λ ) M(\lambda) M ( λ ) (34) once for each i ∈ [ n ] i \in[n] i ∈ [ n ] A i A_i A i i i i M ( λ ) M(\lambda) M ( λ ) A i ∪ { i } A_i \cup\{i\} A i ∪ { i } i ∈ [ n ] i \in[n] i ∈ [ n ] n n n
By (33) , computing β min \beta_{\min} β m i n λ \lambda λ M ( λ ) = 0 M(\lambda)=0 M ( λ ) = 0
We initialize λ \lambda λ ℓ 1 \ell_1 ℓ 1 i , j i,j i , j wd ( { i , j } ) = ∥ p i − p j ∥ 1 \operatorname{wd}(\{i,j\})=\lVert p_i-p_j\rVert_1 wd ({ i , j }) = ∥ p i − p j ∥ 1
β min ≤ min i , j ∈ [ n ] i < j wd ( { i , j } ) = min i , j ∈ [ n ] i < j ∥ p i − p j ∥ 1 . \beta_{\min}\le\min_{\substack{i,j\in[n]\\i<j}}\operatorname{wd}(\{i,j\})=\min_{\substack{i,j\in[n]\\i<j}}\lVert p_i-p_j\rVert_1. β m i n ≤ i , j ∈ [ n ] i < j min wd ({ i , j }) = i , j ∈ [ n ] i < j min ∥ p i − p j ∥ 1 . Starting from this upper bound, the algorithm repeatedly solves (32) . If a subset with negative objective value is found, its ratio in (21) provides a strictly smaller upper bound.
Theorem E.2. There exists an algorithm that computes β min \beta_{\min} β m i n (21) using at most O ( n 2 ) O(n^2) O ( n 2 ) d d d
Proof. We first prove correctness and then establish polynomial termination.
Loop invariants. At the beginning of every iteration, the current parameter λ \lambda λ R R R
λ = wd ( R ) ∣ R ∣ − 1 ≥ β min , (36) \lambda=\frac{\operatorname{wd}(R)}{|R|-1}\ge\beta_{\min}, \tag*{(36)} λ = ∣ R ∣ − 1 wd ( R ) ≥ β m i n , (36) λ ≤ min i , j ∈ [ n ] i < j wd ( { i , j } ) . (37) \lambda\le\min_{\substack{i,j\in[n]\\i<j}}\operatorname{wd}(\{i,j\}). \tag*{(37)} λ ≤ i , j ∈ [ n ] i < j min wd ({ i , j }) . (37) Both invariants hold at initialization: R R R λ = wd ( R ) \lambda=\operatorname{wd}(R) λ = wd ( R ) λ \lambda λ λ ≥ β min \lambda\ge\beta_{\min} λ ≥ β m i n
Termination criterion. Suppose the subset T T T
wd ( T ) − λ ( ∣ T ∣ − 1 ) = 0. \operatorname{wd}(T)-\lambda(|T|-1)=0. wd ( T ) − λ ( ∣ T ∣ − 1 ) = 0. Algorithm 3 Computing $\beta_{\min}$
Require: Points $p_1,\ldots,p_n \in \mathbb{R}^d$, $n \ge 2$
Ensure: $\beta_{\min}$ and a minimizing subset
1: Choose $R \in \arg\min_{\{i,j\}\subseteq[n],\,i<j} \operatorname{wd}(\{i,j\})$
2: $\lambda \gets \operatorname{wd}(R)$
3: loop
4: for $i=1,\ldots,n$ do
5: Compute $A_i \in \arg\min_{A\subseteq[n]\setminus\{i\}}\{\operatorname{wd}(A\cup\{i\})-\lambda|A|\}$
6: end for
7: Choose $i^* \in \arg\min_{i\in[n]}\{\operatorname{wd}(A_i\cup\{i\})-\lambda|A_i|\}$
8: $T \gets A_{i^*}\cup\{i^*\}$
9: if $\operatorname{wd}(T)-\lambda(|T|-1)=0$ then
10: return $(\lambda,R)$
11: end if
12: $\lambda \gets \frac{\operatorname{wd}(T)}{|T|-1}$
13: $R \gets T$
14: end loopBy Lemma E.1, T T T M ( λ ) M(\lambda) M ( λ ) M ( λ ) = 0 M(\lambda)=0 M ( λ ) = 0 (33) then gives λ ≤ β min \lambda\le\beta_{\min} λ ≤ β m i n λ = β min \lambda=\beta_{\min} λ = β m i n R R R
Preservation of the invariants. Suppose the algorithm does not terminate. Since every singleton has zero objective value, the optimal value of (29) must be negative:
wd ( T ) − λ ( ∣ T ∣ − 1 ) = M ( λ ) < 0. (38) \operatorname{wd}(T)-\lambda(|T|-1)=M(\lambda)<0. \tag*{(38)} wd ( T ) − λ ( ∣ T ∣ − 1 ) = M ( λ ) < 0. (38) In particular, ∣ T ∣ ≥ 2 |T|\ge2 ∣ T ∣ ≥ 2 λ ′ = wd ( T ) ∣ T ∣ − 1 \lambda'=\frac{\operatorname{wd}(T)}{|T|-1} λ ′ = ∣ T ∣ − 1 wd ( T )
wd ( T ) < λ ( ∣ T ∣ − 1 ) , \operatorname{wd}(T)<\lambda(|T|-1), wd ( T ) < λ ( ∣ T ∣ − 1 ) , λ ′ < λ . \lambda'<\lambda. λ ′ < λ . Furthermore, since λ ′ \lambda' λ ′ λ ′ ≥ β min \lambda'\ge\beta_{\min} λ ′ ≥ β m i n λ ′ < λ \lambda'<\lambda λ ′ < λ ( λ , R ) ← ( λ ′ , T ) (\lambda,R)\gets(\lambda',T) ( λ , R ) ← ( λ ′ , T )
Polynomial termination. We first observe that every subset T T T { i , j } \{i,j\} { i , j }
wd ( { i , j } ) − λ ≥ wd ( { i , j } ) − min r < s wd ( { r , s } ) ≥ 0. \operatorname{wd}(\{i,j\})-\lambda\ge\operatorname{wd}(\{i,j\})-\min_{r<s}\operatorname{wd}(\{r,s\})\ge0. wd ({ i , j }) − λ ≥ wd ({ i , j }) − r < s min wd ({ r , s }) ≥ 0. A singleton also has objective value zero. Hence a subset satisfying (35) must have cardinality at least three.
We next show that the cardinalities of the subsets returned at successive unsuccessful iterations strictly decrease. Suppose T T T λ \lambda λ k = ∣ T ∣ ≥ 3 k=|T|\ge3 k = ∣ T ∣ ≥ 3 λ ′ = wd ( T ) / ( k − 1 ) \lambda'=\operatorname{wd}(T)/(k-1) λ ′ = wd ( T ) / ( k − 1 ) T T T U ⊆ [ n ] U\subseteq[n] U ⊆ [ n ]
wd ( U ) − λ ( ∣ U ∣ − 1 ) ≥ wd ( T ) − λ ( k − 1 ) . \operatorname{wd}(U)-\lambda(|U|-1)\ge\operatorname{wd}(T)-\lambda(k-1). wd ( U ) − λ ( ∣ U ∣ − 1 ) ≥ wd ( T ) − λ ( k − 1 ) . Therefore, for any U U U ∣ U ∣ ≥ k |U| \ge k ∣ U ∣ ≥ k
wd ( U ) − λ ′ ( ∣ U ∣ − 1 ) = wd ( U ) − λ ( ∣ U ∣ − 1 ) + ( λ − λ ′ ) ( ∣ U ∣ − 1 ) ≥ wd ( T ) − λ ( k − 1 ) + ( λ − λ ′ ) ( ∣ U ∣ − 1 ) = ( λ ′ − λ ) ( k − 1 ) + ( λ − λ ′ ) ( ∣ U ∣ − 1 ) = ( λ − λ ′ ) ( ∣ U ∣ − k ) ≥ 0. \begin{aligned}
\operatorname{wd}(U)-\lambda^{\prime}(|U|-1)
&= \operatorname{wd}(U)-\lambda(|U|-1)+(\lambda-\lambda^{\prime})(|U|-1) \\
&\ge\operatorname{wd}(T)-\lambda(k-1)+(\lambda-\lambda^{\prime})(|U|-1) \\
&= (\lambda^{\prime}-\lambda)(k-1)+(\lambda-\lambda^{\prime})(|U|-1) \\
&= (\lambda-\lambda^{\prime})(|U|-k) \\
&\ge0.
\end{aligned} wd ( U ) − λ ′ ( ∣ U ∣ − 1 ) = wd ( U ) − λ ( ∣ U ∣ − 1 ) + ( λ − λ ′ ) ( ∣ U ∣ − 1 ) ≥ wd ( T ) − λ ( k − 1 ) + ( λ − λ ′ ) ( ∣ U ∣ − 1 ) = ( λ ′ − λ ) ( k − 1 ) + ( λ − λ ′ ) ( ∣ U ∣ − 1 ) = ( λ − λ ′ ) ( ∣ U ∣ − k ) ≥ 0. Consequently, at the updated parameter λ ′ \lambda^{\prime} λ ′ k k k (32) .
If the next iteration is unsuccessful, its minimizing subset T ′ T^{\prime} T ′ wd ( T ′ ) − λ ′ ( ∣ T ′ ∣ − 1 ) < 0 \operatorname{wd}(T^{\prime})-\lambda^{\prime}(|T^{\prime}|-1)<0 wd ( T ′ ) − λ ′ ( ∣ T ′ ∣ − 1 ) < 0 ∣ T ′ ∣ < k = ∣ T ∣ |T^{\prime}|<k=|T| ∣ T ′ ∣ < k = ∣ T ∣
Thus the cardinalities of the subsets returned at successive unsuccessful iterations form a strictly decreasing sequence of integers in { 3 , … , n } \{3,\ldots,n\} { 3 , … , n } n − 2 n-2 n − 2
By Lemma E.1, each iteration requires at most n n n n ( n − 1 ) = O ( n 2 ) n(n-1)=O(n^2) n ( n − 1 ) = O ( n 2 ) □ \square □
