Gap, Rounding and Integer Decomposition I general Andrs Seb, CNRS (G-SCOP) Grenoble Gap Ax b (Amxn,b,c) max cTx easy Duality theorem | yA = c

y0 min yTb = LIN x integer - gap = | =: LIN duality (integrality) duality (integrality)

gap gap gap gap y integer | - |= min { yTTb : yA = c , y 0} - LIN Your future Gap=0: illustrated definitions, related notions Examples: TU and generalizations, matroids, cyclic interval matrices

general stable sets in special graphs special stable sets in general graphs bin packing Properties: adding columns, projection, applications Gap=1: bins, matchings, common indep. of 2 matroids Algorithmic and other uses gap = 0 : Integer Rounding (IR) Ax b (Amxn,b,cn) max cTx yA = c y0 min yTb easy

Duality theorem = =: LIN(c) The system Ax b or (A,b) integer rounding, if c : {min yTb, yA = c, y 0, y integer } = LIN(c) Nothing to round : TDI The system Ax b or (A,b) integer rounding, if cn : {min yTb, yA = c, y 0, y integer}= LIN(c) The system Ax b totally dual integral (TDI), if cn : {min yTb, yA = c, y 0, y integer} = LIN(c) So: integer rounding & LIN(c) is integer c = TDI TDI system = IR system & integer polyhedron

Exemple : IR ?, TDI ? TDI x(S) 1 x0 Not TDI, not even integer: Add x(V(C55)) 2 5 25 233

22 6 3 2 Hint: 3 IR TDI 4 24 Exercise 1 : Prove these Exercise 2: Prove TDI for even circuits and their complements;

IR for odd circuits and their complements; TDI if x(V) 2 is added (x(V) n-1 / 2 for complements). b=0 : Hilbert bases The system Ax 0 TDI (or IR ) if cn : {min yT0, yA = c, y 0, y integer} = LIN(c) 0 if c cone(A) := cone (rows of A) LIN(c) = if c cone(A) The rows of A form a Hilbert basis if Ax 0 is TDI, i.e. for all c cone(A) n : c is a nonnegative integer combination of rows of A. (normal semigroup) Testing for Hb : coNP-complete (J. Pap 07) A Hilbert basis

0 -5 2 -3 1 -1 0 0 -1 1 -2 3 -5 Adding redundant inequalities to -5x1+2x2 0 3x1 -5x2 0 get a TDI system. IR, TDI depend on syst. and not polyh.

Exercise 1: Lin indep. full dim : Hb Their determinant is 1 Exercise 2: If H is a pointed Hilbert basis, for any n-1 element Hb in H a facet there exists an n-th so that det =1. Exercise 3: If H is a 2 dim Hb it is Integer Caratheodory (IC).Hint: delete an extreme ray, prove that it remains a Hb, and induction. Results & problems on Integer Caratheodory Thm: (S. 90) If n=3, Integer Caratheodory property is true Thm: (Bruns, Gubeladze 98) Not true in 6 dim Problem: Integer Caratheodory number of Hilbert cones Thm: (Gijswijt 2010) True for matroid bases. Problem: For rooted arborescences ? Exercise: (CFS86) True for optimal w-coloring in perfect graphs, in particular maximum stable-sets form a `Caratheodory Hb. Thms: (Eisenbrand, Shmonin 2005) Caratheodory bounds

without the Hilbert (or ID) property, for integer cones IR & Hb The system Ax b or (A,b) IR, if c : {min yTb, yA = c, y 0, y integer } = LIN(c) H n Hb if h cone(H) n : h is a nonnegative integer combination of rows of A. Thm:(Giles, Orlin 1981) IR rows of A, b form a Hb. 0, 1 Integer Decomposition (ID) Set of integer vectors P n has the ID property, if v k conv(P) n & k v= v1 + + vk , v1 , , vn P Matrix A is ID if the row-set of A is so. Fact: P=set of all integer points of the convex hull P of

integer points ; if P is a polyhedron, it is integer. Def: A polyhedron P is ID iff P is integer and Pn is ID v kPn & k v= v1 + + vk, v1 ,, vnPn ID of A ~ I R for b=1 The rows of A are ID , if v k conv(A) n & k v= v1 + + vk , v1 , , vn rows of A rows of A, 1 form a Hb The system Ax 1 is I R if c: LIN(c) = {min yT1, yA = c, y 0 } A, 1

rows of form a Hb . 0, 1 I R for b=1 or 0 ~ ID of extended A The system Ax 1, Bx 0 integer rounding, if c: {min yT1, yA+zB = c, y,z 0, y,z integer } = LIN(c) A, 1 rows of B, 0 form a Hb . 0, 1 A, 1 rows of B, 0 form a Hb (if (0,1) is in the intcone of the rest)

Useful example : B = -Id, and A has a non-neg row. Then (0, 1) is in the integer cone of the other rows. A+mxn , x 0, b=1 : IR ID Ax 1 (A+mxn,c+n ) x0 max cTx yA c y0 min yT1 Assume: rows of A contain every integer vector in the downhull of their convex (inessential if 0-1) hull. min yT1, yA c, y integer = LIN(c) ck conv (A) n can be written as c=a1 + + ak

A-mxn , x 0, b=-1 : IR ID Ax 1 (A+mxn,c+n ) x0 min cTx yA c y0 max yT1 Imagine: rows of A contain every integer vector in the uphull of their convex (inessential if 0-1) hull. max yT1, yA c, y integer = LIN(c) ck conv (A) n can be written as c=a1 + + ak The assumption always holds for us Ax 1 x0

Assume: rows of A contain every integer vector in the downhull of their convex (inessential if 0-1) hull. Ax 1 x0 Imagine: rows of A contain every integer vector in the uphull of their convex (inessential if 0-1) hull. +k Integer Rounding +1 of the systems = MIR Integer Decomposition +1 of the rows of A. MID +k

Direct check in a glance: MID = MIR (enough to check IR for LIN) Examples : not ID and ID not ID: Loose examples for ID: matchings in bipartite graphs, consec 1 polyhedra , stable sets in perfect graphs, (uphull of) rooted arborescences in digraphs, TDI Relevant examples for ID: matchings in special graphs, (common) indep in (spec) matroids, TU polyhedra, IR circular intervals, cyclic stable sets, bin patterns, Gap, Rounding and Integer Decomposition II. nonnegative matrices, nonnegativity constraints

Andrs Seb, CNRS (G-SCOP) Grenoble IR , ID The system Ax b is IR, if c: {min yTb, yA = c, y 0, y integer } = LIN(c) Def: A polyhedron P is ID, if k , v kPn v= v1 + + vk, v1 ,, vkPn We will also say that the integer points of P have ID . A++nn Ax 1 Ax 1 x0 x0 If A itself is the set of integer points of a hereditary integer

polyhedron P , the two are the same. IR = ID Ax 1 x0 A++nn Rows of A hereditary , If A is a 0-1 matrix : for instance stable sets: +k MIR Integer Rounding +1 of the system = Integer Decomposition +1 of the rows of A. MID

+k Direct check in a glance: MID = MIR (enough to check IR for LIN) Examples : not ID and ID not ID: Loose examples for ID: matchings in bipartite graphs, consec 1 polyhedra , stable sets in perfect graphs, (uphull of) rooted arborescences in digraphs, TDI Relevant examples for ID: matchings in special graphs, (common) indep in (spec) matroids, TU polyhedra, IR circular intervals, cyclic stable sets, bin patterns, Bin packing (Cutting Stock) INPUT : 0 s11, , sdd 1 item sizes,

b11, , bdd IN item multiplicities Pack them to a min number of bins of capacity 1 dd ++ pattern : p such that p11s11+ + pddsdd 1 pattern inequality : p11x11 + + pddxdd 1 modified sizes dd ++ : x :

P : = the rows are the patterns Pattern Inequalities 1/3 d pattern : p ++d such that p11s11+ + pddsdd 1 pattern inequality : p11x11 + + pddxdd 1 modified sizes: 11/40 d x 11/40 ++d :

OPT= 3 11/40 11/40 11/40 11/40 11/40 11/40 11/40 LIN = 7/3

modified sizes: 1/3 Pattern Inequalities d d pattern : p ++ such that p11s11+ + pddsdd 1 1/3 pattern inequality : p11x11 + + pddxdd 1 d modified sizes : x ++d :

Gilmore-Gomory LP of all pattern inequalities : Px 1 (P +big x d ) x0 d T max b x (b + ) Max of total modified size yP b y0 = min yT1 Bin packing

Marcottes example (1985) d=3 s=(1/2, 1/3, 1/5) b=(1, 2, 4) b 2 0 0 1 1 0 1 P= 0 3 0 1 0 2 2 0 0 5 0 2 1 4 SIZE = 59/30 LIN = + 2/3 + 4/5 = 59/30 OPT= 2 or33 ?

For squeezing into 2 bins, we can spoil only 1/30, but hard to write 29/30 = 15/30 x + 10/30 y + 6/30 z With x, y, z integers . d=2 : McCormick, Smallwood, Spieksma P + b big x 2 : 2 + dd

++ pattern : p yP = b y0 min yT1 such that p11s11+ + pddsdd 1 Thm: {(p,1): p P} is a Hb Proof: Any 3 lin indep forming a lifted simplex is a Hb (i.e. is unimodular). Stable sets I : matchings M (G):=conv(matchings of G) PM(G):=conv (perfect m.) .

Thm (Knig ) G bipartite : they are ID. Conjecture (Lovsz ) : G without Petersen minor : they are ID Conjecture (Goldberg, Seymour ) : MID = ID +1 x k M (G) x = M1 + + Mk+1 Exercise : Determine cone (M(G), 1) . Prove the Stable sets that are ID Problem : Characterize graphs whose stable sets are ID Difficult, but : Are h-perfect (t-perfect) graphs among them ? Independent sets of matroids (Edmonds) Ax 1 (A+mxn,c+n) x0 max cTx

yA c y0 min yT1 M= (S, F ) matroid, rows of A: {I {0,1}S: I independent} A is integer rounding so integer decomposition, and : k conv( A ) = {xS : x(U) k r(U) U S} box-TDI that is, has an integer solution adding upper bounds ID + k box TDI M= (S , F ) matroid

x(U) k r(U) U S xii 1 i S Theorem (variant of Edmonds matroid partition) max union of k independent sets = min {|X| + k r(S \ X) : X S } Conjecture (Aharoni) : Matroid intersection is MID List coloring Theorems Theorem (Galvin): G bipartite. If it can be k-edge-colored, Then it can also be list-edge-colored if the lists are k. Exercise: M=(S,F) matroid. If it is the union of k indep sets then it can be also list-independent colored if the lists are k. (Seymour) Hint: Define matroid M1, , Mk on the sets Si := {eS: e has colour i in its list}. Check the condition of the matroid partition theorem using that S can be

covered by k independent sets of M. TU polyhedra are ID Theorem (Baum and Trotter 1977) A is TU Q:={x n : Ax b} is ID Proof : Let xk kQ. We are looking for x : (i) x Q , (ii) xk - x (k-1) Q Exercise : Check that for fixed xk both (i) and (ii) are linear systems with matrix A, and altogether x has a unimodular coeff matrix. Note that (i), (ii) is feasible : xk/k is a feasible solution. So, since x has a unimod coeff matrix an integer solution exists and can be computed. The projection project Is the projection of ID polyhedra ID ? If YES, then new examples !

If NO, then is it true for TU ? Applications ? Projection of ID is not necessariIy ID ID Q = conv(triangles containing IRV Projecting out : P = conv(edges) sum of edges 3 P but not sum of 3 edges

Obstacle: lift up is 3/2 in ) Projection Proposition : If A is TU, then projections of Q:= {x : Ax b} are ID. (S. 2008) Proof : Q Zn, let n < n and P:= {(y1, , yn ) : y Q } Let z kP , z integer . z/k P , so z: (z/k, z) Q , i.e. (z, kz) kQ kz is a solution of Ax b (= kb zA(. ;1,...,n)) So kz can be chosen to be integer. DONE Chains, antichains in posets Dilworth theorem (1950): max

stable set (antichain) = min { |P| : P partition into paths } Greene-Kleitman theorem (1976): max union of k stable sets (antichain), =min {|X| + k|P| : XV,P set of disj paths (chains) X = vertices uncovered by P} DIGRAPHS max stable Gallai-Milgram (1960): max stable set

min partition into paths IN A STRONG DIGRAPH Bessy-Thomass (2007),Gallais conj: max stable set min cycle cover DIGRAPHS max k- colored subgraphs Berge-Linial conjecture (1981): Schrijver, Prob 5 max union of k stable sets min {|X| + k|P| : XV, P set of disj paths, X uncovered }

Strongly connected version: max union of k stable sets min {|X| + k|C| : XV, C set of circuits, X uncovered} (Whose conjecture ?) Stable sets in graphs II : cyclic stable sets From ID + k box TDI for cyclic stable sets : Theorem (S. 2007) G strongly connected max union of k stable sets min {|X| + k|C| : C set of circuits

X = vertices uncovered by C } Connexions ? : IR of cyclic sets Applications of the projection : minmax IR property- for particular (cyclic) stable sets (S: JCT/B 2007) and their relation to path partitions in arbitrary or to cycle-covers in strongly connected graphs. (S: Survey Ref 4.) Nearly unimodular: add a row of a unimodular matrix to the others. Application cyclic interval constraints. (Gijswijt 2005: Ref 3.) Maximum stable sets in (fuzzy) circular interval graphs (3 organizers and a would-be participant) Multiflows in rings (Cedric Bentz thesis, 2006) Nearly unimodular matrices

mxn n Def : U unimodular, U ,u . M= U + C, where the T u rows of C are integer multiples of u : nearly unimodular (NU) Thm(Gijswijt) Let M NU: PM,b:= {xn: Mxb} is ID. Proof: PM,b,s := PM,b {x : uTx = s} is ID (Baum,Trotter) Claim: PM,b {q uTx q+1} is ID q q+1

. q Let x , kxn . uT(kx)=qk + r, 0 < r < q Then x= y + (1-)z , yPM,b,q+1 , zPM,b,q kx= ky + (k- k)z , yPM,b,q+1 , zPM,b,q k=r x kx= ry + (k- r)z , yPM,b,q+1 , zPM,b,q x y z : xn fixed, y , z CBCn : y r PM,b,q+1

, x - y (k-r) PM,b,q+1 unimodular system for y. Q.E.D. Problem: Other operations getting to new ID systems ? How far does TU reach ? Conclusion IR (with integral vetices: TDI) the same as ID for nonneg matrices, nonnegativity constraints : ID Classical examples, operations, Cyclic combinatorial objects Pol alg : direct comb algs or ellipsoids if A explicitly given MID (ID +1): Matching, matroid intersection and Bin packing (comb approach, general Lemmas, consequence

BONUS : BACK TO BINS m:=LIN = integer (ID=IR) Critical instances Start of proof: b-lexicographically minimal counterexample to what ? We call an instance I critical , if for any pattern P : LIN (I \ P) > LIN (P) 1 Another kind of minimality : If we decrease b lexicographically, one less bin is enough. NFD order quite good, but simplest proofs from : m+2 th bin lex min, then m+1th bin lex min, : OPT= m+2 In the last bin: only the smallest item s.

m:=SIZE d-2 Lemma 1: All bins have m-2 items, s 1/m-1.

~~
~~ ~~ 1+ (m-2)s, and SIZE > m) ~~

~~
~~() The method : assign then weights summing to > m (If m=5 (d 7) for items in 2-bins, except the smallest of them, 1/3 for those in 3-bins, except the 3 smallest, including s. Altogether TOTAL MODIFIED SIZE > m for the m+1 bins + s) GAP 0 for bin packing mxd Px 1 (P + ) x0 d max bTx (b + ) yP b

y0 = min yTb 2i 22ii ++ 2 2 ii 2j Marcotte (1985) , Rizzi (1997) : gap0 Scheithauer & Ternos(1997) conjecture : gap=1 MIRUP (Modified integer rounding property) , proved for d 6 Shmonin, S. (2006 - ) Combinatorial properties of critical instances, implies MIRUP for d 7, simpler for Karmarkar, Karp (82) additive error log2 d (AFPTAS) Results on cutting stock LIN

: ~ P ellipsoid method; knapsack separation d= 2 : P McCormick, Smallwood, Spieksma (93) d = fix : OPT +1 P Jansen, Solis-Oba, (10) d=fix not necessary : If GAP 1, then OPT LIN +1 always, and LIN+1 P AFPTAS : Karmarkar, Karp additive error log2 d (82) These and Marcottes examples support MIRUP (Modified integer rounding property) , stated by Scheithauer Terno (1997) : gap=1

Results on MIRUP d=2 & : McCormick, Smallwood, Spieksma (93) d=3,4,5,6 : MIRUP Scheithauer and Terno (97) Towards a critical combinatorial structure implying : d 7: MIRUP with polynomial algorithm (Shmonin,S.06) General combinatorial lemmas Structure when all bins are of size at most 3. All sizes > 1/4 (Eisenbrand, Plvlgyi, Rothvoss 2010: constant gap reduced to (specialized ? Generally false) conjecture of Beck.) Questions on bin packing For d = 3 P ? For d = 8 GAP = 1 ? 3 partition ?

~ All sizes > Relations between GAP=1 problems OPT+1 ? Fix dim P by Jansen, Solis-Oba, (10)

~~
~~