IntroductionLogarithmic FormulationsPiecewiselinear FunctionsComputational ResultsFinal RemarksIntroduction Logarithmic Formulations Piecewiselinear Functions Computational Results Final RemarksModeling Disjunctive Constraints with aLogarithmic Number of Binary Variables andConstraintsJuan Pablo Vielma George L. NemhauserH. Milton Stewart School of Industrial and Systems EngineeringGeorgia Institute of TechnologyINFORMS Annual Meeting 2008 Washington, DCIntroduction Logarithmic Formulations Piecewiselinear Functions Computational Results Final RemarksOutline1Introduction2Logarithmic Formulations3Piecewiselinear Functions4Computational Results5Final RemarksIntroduction Logarithmic Formulations Piecewiselinear Functions Computational Results Final RemarksConstraints: Only some subsets of variables can benon-zero at the same timeSOS1: λ ∈ [0, 1]nsuch that at most one λjis non-zero.SOS2: (λj)nj=0∈ [0, 1]n+1such that at most two λj’s arenon-zero. Two non-zero λj’s must be adjacent:√(0, 1,12, 0, 0) X (0, 1, 0,12, 0)In general, for finite set J and finite family {Si}i∈I⊂ Jλ ∈[i∈IQ(Si) ⊂ [0, 1]Jwhere Q(Si) =λ ∈ [0, 1]J: λj≤ 0 ∀j /∈ Si.For “simplicity” we restrict to the simplex∆J:= {λ ∈ RJ+:Pj∈Jλj≤ 1}.Standard MIP models have |I| binaries and |J| extraconstraints.Introduction Logarithmic Formulations Piecewiselinear Functions Computational Results Final RemarksConstraints: Only some subsets of variables can benon-zero at the same timeSOS1: λ ∈ [0, 1]nsuch that at most one λjis non-zero.SOS2: (λj)nj=0∈ [0, 1]n+1such that at most two λj’s arenon-zero. Two non-zero λj’s must be adjacent:√(0, 1,12, 0, 0) X (0, 1, 0,12, 0)In general, for finite set J and finite family {Si}i∈I⊂ Jλ ∈[i∈IQ(Si) ⊂ [0, 1]Jwhere Q(Si) =λ ∈ [0, 1]J: λj≤ 0 ∀j /∈ Si.For “simplicity” we restrict to the simplex∆J:= {λ ∈ RJ+:Pj∈Jλj≤ 1}.Standard MIP models have |I| binaries and |J| extraconstraints.Introduction Logarithmic Formulations Piecewiselinear Functions Computational Results Final RemarksConstraints: Only some subsets of variables can benon-zero at the same timeSOS1: λ ∈ [0, 1]nsuch that at most one λjis non-zero.SOS2: (λj)nj=0∈ [0, 1]n+1such that at most two λj’s arenon-zero. Two non-zero λj’s must be adjacent:√(0, 1,12, 0, 0) X (0, 1, 0,12, 0)In general, for finite set J and finite family {Si}i∈I⊂ Jλ ∈[i∈IQ(Si) ⊂ ∆Jwhere Q(Si) =λ ∈ ∆J: λj≤ 0 ∀j /∈ Si.For “simplicity” we restrict to the simplex∆J:= {λ ∈ RJ+:Pj∈Jλj≤ 1}.Standard MIP models have |I| binaries and |J| extraconstraints.Introduction Logarithmic Formulations Piecewiselinear Functions Computational Results Final RemarksConstraints: Only some subsets of variables can benon-zero at the same timeSOS1: λ ∈ [0, 1]nsuch that at most one λjis non-zero.SOS2: (λj)nj=0∈ [0, 1]n+1such that at most two λj’s arenon-zero. Two non-zero λj’s must be adjacent:√(0, 1,12, 0, 0) X (0, 1, 0,12, 0)In general, for finite set J and finite family {Si}i∈I⊂ Jλ ∈[i∈IQ(Si) ⊂ ∆Jwhere Q(Si) =λ ∈ ∆J: λj≤ 0 ∀j /∈ Si.For “simplicity” we restrict to the simplex∆J:= {λ ∈ RJ+:Pj∈Jλj≤ 1}.Standard MIP models have |I| binaries and |J| extraconstraints.Introduction Logarithmic Formulations Piecewiselinear Functions Computational Results Final RemarksOne-to-One correspondence between elements of I andvectors in {0, 1}log2|I|0 0 0 0...1 0 0 0...0 1 0 0...1 1 1 1...1 1 0 0.........123...4I |I|log2|I||I| = 2kIn general, an injective function:B : I → {0, 1}dlog2|I|eEasy to get a formulation withdlog2|I|e binary variables and|I| extra constraints (e.g.Ibaraki 1976).Introduction Logarithmic Formulations Piecewiselinear Functions Computational Results Final RemarksLog number of binary variables and extra constraints forSOS1 over λ ∈ ∆J⊂ R4+, (I = J = {1, . . . , 4})0 01 00 11 1SiB(i){1}{2}{3}{4}i1234x1x2λ1+ λ2≤ (1 − x2)λ3+ λ4≤ x2∈ {0, 1}λ1+ λ2+ λ3+ λ4≤ 1, λ1, λ2, λ3, λ4≥ 0Introduction Logarithmic Formulations Piecewiselinear Functions Computational Results Final RemarksLog number of binary variables and extra constraints forSOS1 over λ ∈ ∆J⊂ R4+, (I = J = {1, . . . , 4})0 01 00 11 1SiB(i){1}{2}{3}{4}i1234x1x2λ1+ λ2≤ (1 − x2)λ3+ λ4≤ x2∈ {0, 1}λ1+ λ2+ λ3+ λ4≤ 1, λ1, λ2, λ3, λ4≥ 0Introduction Logarithmic Formulations Piecewiselinear Functions Computational Results Final RemarksLog number of binary variables and extra constraints forSOS1 over λ ∈ ∆J⊂ R4+, (I = J = {1, . . . , 4})0 01 00 11 1SiB(i){1}{2}{3}{4}i1234x1x2λ1+ λ2≤ (1 − x2)λ3+ λ4≤ x2∈ {0, 1}λ1+ λ2+ λ3+ λ4≤ 1, λ1, λ2, λ3, λ4≥ 0Introduction Logarithmic Formulations Piecewiselinear Functions Computational Results Final RemarksLog number of binary variables and extra constraints forSOS1 over λ ∈ ∆J⊂ R4+, (I = J = {1, . . . , 4})0 01 00 11 1SiB(i){1}{2}{3}{4}i1234x1x2λ2+ λ4≤ x1λ1+ λ2≤ (1 − x2)λ3+ λ4≤ x2∈ {0, 1}λ1+ λ2+ λ3+ λ4≤ 1, λ1, λ2, λ3, λ4≥ 0Introduction Logarithmic Formulations Piecewiselinear Functions Computational Results Final RemarksLog number of binary variables and extra constraints forSOS1 over λ ∈ ∆J⊂ R4+, (I = J = {1, . . . , 4})0 01 00 11 1SiB(i){1}{2}{3}{4}i1234x1x2λ2+ λ4≤ x1λ1+ λ2≤ (1 − x2)λ3+ λ4≤ x2∈ {0, 1}λ1+ λ2+ λ3+ λ4≤ 1, λ1, λ2, λ3, λ4≥ 0Introduction Logarithmic Formulations Piecewiselinear Functions Computational Results Final RemarksLog number of binary variables and extra constraints forSOS1 over λ ∈ ∆J⊂ R4+, (I = J = {1, . . . , 4})0 01 00 11 1SiB(i){1}{2}{3}{4}i1234x1x2λ2+ λ4≤ x1λ1+ λ3≤ (1 − x1)λ1+ λ2≤ (1 − x2)λ3+ λ4≤ x2∈ {0, 1}λ1+ λ2+ λ3+ λ4≤ 1, λ1, λ2, λ3, λ4≥ 0Introduction Logarithmic Formulations Piecewiselinear Functions Computational Results Final RemarksLog number of binary variables and extra constraints forSOS1 over λ ∈ ∆J⊂ R4+, (I = J = {1, . . . , 4})0 01 00 11 1SiB(i){1}{2}{3}{4}i1234x1x2λ2+ λ4≤ x1λ1+ λ3≤ (1 − x1)∈ {0, 1}λ1+ λ2+ λ3+ λ4≤ 1, λ1, λ2, λ3, λ4≥ 0Introduction Logarithmic Formulations Piecewiselinear Functions Computational Results Final RemarksLog number of binary variables and extra constraints forSOS1 over λ ∈ ∆J⊂ R4+, (I = J = {1, . . . , 4})0 01 00 11 1SiB(i){1}{2}{3}{4}i1234x1x2λ2+ λ4≤ x1λ1+ λ3≤ (1 −