1
$\begingroup$

Below I need solve for the binary variables $x_1,x_2,y_1,y_2,z_1,z_2$ that minimize the functions $f(x), f(y), f(z)$, subject to the 5 constraints that follow. By binary I mean they can only be 1 or 0. [Edit: $u_1,u_2,h$ are non-negative real valued. The functions to be minimized must also be non-negative. This is a much reduced version of a big workshift scheduling problem.]

I appreciate any advice as to what sort of strategy I might use. Thanks.

$x_1u_{1}+x_2u_{2}-h=f(x)$

$y_1u_{1}+y_2u_{2}-h=f(y)$

$z_1u_{1}+z_2u_{2}-h=f(z)$

$s.t.$

$x_1+x_2=1$

$y_1+y_2=1$

$z_1+z_2=1$

$x_1+y_1+z_1=1$

$x_2+y_2+z_2=1$

  • 0
    May I suggest that you use a more descriptive question title than "Binary Integer Programming Problem".2013-12-29

1 Answers 1

3

Assuming that $u_1,u_2,h \gt 0$

WLOG set $x_1=x_2=0$, $y_1=1$, $y_2=0$, $z_1=0$, and $z_2=1$.

This gives $f(x)=-h$, $f(y)=u_1-h$, $f(z)=u_2-h$

However, there are 5 other solutions that are equivalent to this one i.e. 3 choices for a variable to have both of its terms set to 0 and 2 choices of which remaining variable has its sub 1 equal to 1.

These 6 solutions appear to be the only ones that satisfy the constraints and for fixed $u_1,u_2,h$ they are all the same.

  • 0
    In general an optimization problem should have a single objective. You can't usually minimize three different objectives: a solution that minimizes one will not minimize the others. You may need to settle for some sort of trade-off: see http://en.wikipedia.org/wiki/Multi-objective_optimization2011-08-15