# Binary Integer Programming Problem

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$

• I have some questions: (1) Is this a homework assignment? (2) What are $h$, $u_{1}$, and $u_{2}$? – Doug Chatham Aug 15 '11 at 0:47
• 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? – Gerry Myerson Aug 15 '11 at 0:47
• Not a homework assignment – ben Aug 15 '11 at 1:57
• @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. – ben Aug 15 '11 at 2:22
• 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)$. – Gerry Myerson Aug 15 '11 at 2:55

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.

• 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. – ben Aug 15 '11 at 2:43
• @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$? – user12998 Aug 15 '11 at 3:02
• $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). – ben Aug 15 '11 at 3:15
• if $h\geq u_1+u_2$ then your function will always return negative values. – user12998 Aug 15 '11 at 3:25
• @ben Are you trying to minimize the number of unworked hours for each individual per week? – user12998 Aug 15 '11 at 3:27