Meeting deadlines and breaking simmetry
Andrea Taverna
inside a few building sites.
There are different objectives, the first being the global amount of
work done, expressed as the sum of advancement inside each site.
Advancements are expressed as the ratio between the work done and the
expected amount of workload.
Here is the first problem. Each building site has a deadline which may
lie beyond the current period of optimization. More precisely, the
period, is broken, for efficiency, into sub-periods and the program
optimizes iteratively each sub-period. As a consequence, I cannot
set any deadline to be met by imposing total completion for each
working site after its deadline.
So I fell back on weighting sites' advancements with priorities,
defined as as 1/(e - d), where e is the working site's deadline and d
the last day of the current subperiod. It works well, but it doesn't
guarantee that deadlines will be met.
The second problem is tied to another objective: minimizing workers'
turn variation. Turn variations are defined as the number of times a
worker changes working site from a day to the next one. In formula:
f(x) = sum{ worker in W, site in S, d in Day} |x[w,s,d] - x[w,s,d-1]|
where x is a binary variable s.t. x[w,s,d] = 1 --> worker w is
assigned to site s on day d.
Problem formulation w.r.t. the objective shows symmetry, which makes
the solver (CPLEX) generate a huge amount of branching nodes till
memory exhaustion, even for periods shorts as 7 days.
It looks like optimally breaking symmetry is hard, if not impossible.
Any advice?
TIA
Andrea
Paul Rubin
> I've got the following problem: optimize the scheduling of workers
> inside a few building sites.
>
> There are different objectives, the first being the global amount of
> work done, expressed as the sum of advancement inside each site.
> Advancements are expressed as the ratio between the work done and the
> expected amount of workload.
>
> Here is the first problem. Each building site has a deadline which may
> lie beyond the current period of optimization. More precisely, the
> period, is broken, for efficiency, into sub-periods and the program
> optimizes iteratively each sub-period. As a consequence, I cannot
> set any deadline to be met by imposing total completion for each
> working site after its deadline.
> So I fell back on weighting sites' advancements with priorities,
> defined as as 1/(e - d), where e is the working site's deadline and d
> the last day of the current subperiod. It works well, but it doesn't
> guarantee that deadlines will be met.
You might be better off setting progress goals for each site in each of
the subperiod problems and working on other objectives. If a final
deadline is not met, adjust some of the earlier progress requirements
upward and solve again. If it is met with time to spare, maybe adjust
some of the earlier progress requirements downward and repeat. It's
time-consuming and not guaranteed to produce an optimal solution, but it
should ultimately get you solutions that meet completion deadlines
(assuming that's possible). Your current approach is also not guaranteed
to produce globally optimal solutions.
>
> The second problem is tied to another objective: minimizing workers'
> turn variation. Turn variations are defined as the number of times a
> worker changes working site from a day to the next one. In formula:
>
> f(x) = sum{ worker in W, site in S, d in Day} |x[w,s,d] - x[w,s,d-1]|
>
> where x is a binary variable s.t. x[w,s,d] = 1 --> worker w is
> assigned to site s on day d.
>
> Problem formulation w.r.t. the objective shows symmetry, which makes
> the solver (CPLEX) generate a huge amount of branching nodes till
> memory exhaustion, even for periods shorts as 7 days.
> It looks like optimally breaking symmetry is hard, if not impossible.
> Any advice?
>
Recent work on orbital branching and orbital pruning might help. I
found the following two tech reports quite interesting:
@TECHREPORT{Ostrowski2007,
author = {James Ostrowski and Jeff Linderoth and Fabrizio Rossi and
Stefano Smriglio},
title = {Constraint Orbital Branching},
institution = {Lehigh University Department of Industrial and Systems
Engineering},
year = {2007},
month = {November},
url = {http://www.optimization-online.org/DB_HTML/2008/01/1867.html}
}
@TECHREPORT{Ostrowski2006,
author = {James Ostrowski and Jeff Linderoth and Fabrizio Rossi and
Stefano Smriglio},
title = {Orbital Branching},
institution = {Lehigh University Department of Industrial and Systems
Engineering},
year = {2006},
number = {06T-007},
month = {November},
url = {http://www.optimization-online.org/DB_HTML/2006/11/1527.html}
}
I believe they contain references to work done by Francois Margot on
symmetry in IPs; if not, Google is your friend.
It may also be possible for you to add some constraints that remove a
considerable portion of the symmetry. If all the workers are identical,
you can eliminate a bit of symmetry by requiring that first-day
assignments satisfy lexicographic order: worker w > 1 can be assigned
to site s > 1 on the first day only if some worker w' < w has been
assigned to site s-1 on the first day. (Worker 1 must be assigned to
site 1 the first day.) If not all sites necessarily get workers on the
first day, you have to modify this a bit. After the first day, it gets
a bit trickier.
HTH,
Paul