Problems with constraint. Alternative for JuMP variable in if statement

Specific Domains Optimization (Mathematical)
1

Hey. So I need to implement the following:

Let’s say that we have 10 workers. If they work in the weekend then they want to work both days of the weekend or none. If they work only one day of the weekend then we add a penalty to the objective function.
I have made a variable x[w=1:10,d=1:7] which is equal to 1 if worker w works at day d. Another variable is y[w=1:10] of which will be equal to 1 if worker w works one day of the weekend (or maybe the opposite of that if it would make the constraint easier to make).

The problem is; I need a constraint that is equivalent to
@constraint([w=1:10], y[w] == (x[w,6] + x[w,7] == 1 ? 1 : 0).
That is: for all workers going from 1 to 10, if working on either day 6 or 7 then y[w]=1 otherwise 0.
The problem here is that I can’t use JuMP variable in if statements, so I will need to work around that somehow.

2

I believe you can do the following trick:

Make y a binary variable (if it is not already).

@constraint([w=1:10], y[w] >= x[w, 6]/2 + x[w, 7]/2)

With the constraint above y will be 1 if the worker works any days in the weekend.

In the objective function, add the double of the penalty if y is 1 and subtract the penalty one time if x[w, 6] is one and another time if x[w, 7] is one.

@objective(model, ... + 2*penalty*y[w] - penalty*x[w, 6] - penalty*x[w, 7])

This way:

  1. The penalty is not added if the worker does not work in the weekend (all extra terms are evaluated to zero).
  2. The penalty is not added if the worker works both days of the weekend (y term will add the double penalty but it will be removed by both x terms).
  3. The penalty will be added if the worker works only one day of the weekend (y term will add the double penalty but one of the x terms will subtract half of it).

P.S.: I forgot again, Welcome to our community! :confetti_ball:

2 Likes
3

Many thanks for the quick response Henrique!
Excellent solution, it looks promising!
This has bothered me all evening. I’m very excited to try it out it the morning.

And thanks for welcoming me!
Goodnight from here :blush:

4

You can write XOR using four linear inequalities:

model = Model()
@variable(model, x[1:2], Bin)
@variable(model, y, Bin)
# Constraint to model:
# y = (x[1] + x[2] == 1 ? 1 : 0)
# Construct truth table:
# x[1] x[2] y
#  F    F   F
#  T    F   T
#  F    T   T
#  T    T   F
@constraints(model, begin
    y <= x[1] + x[2]
    y >= x[1] - x[2]
    y >= x[2] - x[1]
    y <= 2 - x[1] - x[2]
end)
2 Likes
5

This is basically the same idea, but cleaner. It trades four times the number of constraints for no extra terms in the objective. Maybe the relaxation is better?

6

You would have to try it out to see. The benefit of the explicit XOR approach is that it will work if y appears elsewhere in the model, not just as a penalty term in the objective.

2 Likes
7

Very clever solutions. Many thanks!

8

You might also want to have a look at: my constraint solver GitHub - Wikunia/ConstraintSolver.jl: ConstraintSolver in Julia: Blog posts -> which is still in its very early stage.
In that case:

@constraint([w=1:10], y[w] == (x[w,6] + x[w,7] == 1 ? 1 : 0)

can be expressed as

@constraint([w=1:10], y[w] := { x[w,6] + x[w,7] == 1 })

If it’s very slow or if you encounter other problems I would appreciate when you open an issue with a full example as I’m very eager to improve that solver :smile:

2 Likes