Suppose we have variables x 1 , x 2 , y ∈ { 0 , 1 } such that y = 1 if and only if x 1 = x 2 = 1 and we want maximize the value of y. I know that this reduces to the following Integer programming problem: max y x 1 , x 2 , y ∈ { 0 , 1 } y ≤ x 1 y ≤ x 2 . The linear relaxation of this problem is then given by: max y 0 ≤ x 1 , x 2 , y ≤ 1 y ≤ x 1 y ≤ x 2 . Now in the relaxation we will simply get y = min { x 1 , x 2 }. I was wondering whether there is some alternative formulation for the Integer Program such that, when we take the linear relaxation of the problem, the solution y is stricly smaller than min { x 1 , x 2 }.

Question

Suppose we have variables       x    1    ,      x    2    ,  y  ∈  {  0  ,  1  } such that   y  =  1 if and only if       x    1    =      x    2    =  1 and we want maximize the value of   y. I know that this reduces to the following Integer programming problem:                    max        y                                            x          1                ,                  x          2                ,        y        ∈        {        0        ,        1        }                            y        ≤                  x          1                                    y        ≤                  x          2                .            The linear relaxation of this problem is then given by:                    max        y                                  0        ≤                  x          1                ,                  x          2                ,        y        ≤        1                            y        ≤                  x          1                                    y        ≤                  x          2                .            Now in the relaxation we will simply get   y  =  min  {      x    1    ,      x    2    }. I was wondering whether there is some alternative formulation for the Integer Program such that, when we take the linear relaxation of the problem, the solution   y is stricly smaller than   min  {      x    1    ,      x    2    }.

Kathryn Moody · Accepted Answer

This reformulation relies on the optimality condition that   y is maximized. The constraints enforce only   y  ≤  min  (      x    1    ,      x    2    ), and   y  &amp;lt;  min  (      x    1    ,      x    2    ) is feasible but not optimal. If your problem has a different objective, you can instead impose an additional linear constraint   y  ≥      x    1    +      x    2    −  1 to enforce   (      x    1    =  1  ∧      x    2    =  1  )    ⟹    y  =  1

Suppose we have variables x 1 </msub> , x 2 </msub> , y

Answered question

Answer & Explanation

New Questions in High school geometry