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
    I have some questions: (1) Is this a homework assignment? (2) What are $h$, $u_{1}$, and $u_{2}$?2011-08-15
  • 0
    I take it $u_1,u_2,h$ are given, but are they also binary, or what?Anyway, there are only 64 possibilities for your unknowns, and a lot of those are wiped out by the constraints, so why not just run through them all?2011-08-15
  • 0
    Not a homework assignment2011-08-15
  • 0
    @Doug Chatham--Not a homework assignment. h, u1, u2, are given (non-negative real). Perhaps if I explain: This is a work shift scheduling problem. For each worker x,y,z there is an equation to minimize. u is a shift , ie no. hrs. to be worked at particular place *and* day of the week (in the above simplified version, there is just one place and two days; in a real problem u would be double indexed). h is the total work hours worked by each worker in the week.The constraints prohibit workers from being in more than one place at a time, and from doubling up on any single shift.2011-08-15
  • 0
    It looks like you've edited $x_2$, $y_2$, and $z_2$ right out of the formulas for $f(x)$, $f(y)$, and $f(z)$.2011-08-15
  • 0
    Thanks! Have no idea how that happened. But now it's fixed.2011-08-15
  • 0
    As currently stated, the equations are insoluble. The first three constraints give $x_1 + x_2 + y_1 + y_2 + z_1 + z_2 = 3$ and the last two constraints give $x_1 + y_1 + z_1 + x_2 + y_2 + z_2 = 2$.2011-08-15
  • 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
    Thanks for the answer. Unfortunately it doesn't work for me, but that is my fault as I didn't state the problem clearly. The equations to be minimized have a lower bound at 0, i.e. are non-negative, so -h is unacceptable. I will edit my original post and try to make this clearer. Sorry.2011-08-15
  • 0
    @ben re: edit. The constraints that you have chosen still only permit the six equivalent solutions in my answer. Also, what are the (magnitude) relations between $u_1,u_2$, and $h$? $u_1=u_2>h$?2011-08-15
  • 0
    $u_1, u_2$ don't have to be the same but will generally be somewhere around 8 (work hours). And $h\geq u_1+u_2$. The u's are individual shifts (workdays) while h is the maximum number of hours each worker is contracted to work in the week (in this simplified version of the problem there are only two days in the workweek).2011-08-15
  • 0
    if $h\geq u_1+u_2$ then your function will always return negative values.2011-08-15
  • 0
    @ben Are you trying to minimize the number of unworked hours for each individual per week?2011-08-15
  • 0
    Ok, I've realized I need to think about this problem some more before I can clearly state it. I thank everyone for their comments. Probably best for me to just delete the question and start from scratch when I have a clearer idea of it. If I try to respond to comments and questions on the fly like this things might get very convoluted. Again thanks everyone.2011-08-15
  • 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