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.










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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.