<html>
<head>
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#FFFFFF">
Hi Mona,<br>
<br>
I did some experiments with CPLEX and CBC for a (nurse) rostering
problem. <br>
<br>
Santos, Haroldo G.; Toffolo, Túlio A.M.; Gomes, Rafael A.M. and
Ribas, Sabir. <a
href="http://www.decom.ufop.br/haroldo/papers/Santos2014.pdf">Integer
programming techniques for the nurse rostering problem. Annals of
Operations Research</a>, 2014.<br>
<br>
Recent versions of CBC have the zero half cuts, which usually give
one improvement for scheduling formulations. Rewrite your problem in
terms of stronger constraints may help... <br>
<br>
AFAIK CBC is the fastest open source MIP solver. There is SCIP which
is very fast, but it is not free for commercial use.<br>
<br>
Cheers,<br>
<br>
<div class="moz-cite-prefix">On 15-06-2015 11:15, Mona Rahn wrote:<br>
</div>
<blockquote
cite="mid:CAJW3XALfTB1GNGosoK8BiSbjjFw1F7ORDU_6ZuEtQf9Ge2t4gg@mail.gmail.com"
type="cite">
<div dir="ltr"><span
style="font-family:Arial,Helvetica,sans-serif;font-size:13px">Hi
all,</span>
<div
style="margin:0px;padding:0px;border:0px;vertical-align:baseline;font-family:Arial,Helvetica,sans-serif;font-size:13px"><br>
</div>
<div
style="margin:0px;padding:0px;border:0px;vertical-align:baseline;font-family:Arial,Helvetica,sans-serif;font-size:13px">I
am trying to program software for automated roster planning.
My program works fine if I use CPLEX, but the final goal is to
use CBC (or some other free solver). I have several cases
which CPLEX solves in about half a minute, while CBC is still
not done after 10 minutes.</div>
<div
style="margin:0px;padding:0px;border:0px;vertical-align:baseline;font-family:Arial,Helvetica,sans-serif;font-size:13px"><br>
</div>
<div
style="margin:0px;padding:0px;border:0px;vertical-align:baseline;font-family:Arial,Helvetica,sans-serif;font-size:13px">Do
you have a tip how to make CBC run faster? I.e., is it better
to add constraints / variables? Or to remove them? Or can I
influence the solver in any other way? Or is there another
free solver which might run faster?</div>
<div
style="margin:0px;padding:0px;border:0px;vertical-align:baseline;font-family:Arial,Helvetica,sans-serif;font-size:13px"><br>
</div>
<div
style="margin:0px;padding:0px;border:0px;vertical-align:baseline;font-family:Arial,Helvetica,sans-serif;font-size:13px">Here
are some more details about the model: I use MIPs,</div>
<div
style="margin:0px;padding:0px;border:0px;vertical-align:baseline;font-family:Arial,Helvetica,sans-serif;font-size:13px">
<ul>
<li style="line-height:17px">the variables are essentially
binary variables, one for each tuple (worker, time, task)<br>
</li>
<li style="line-height:17px">the constraints consist of</li>
<ul>
<li style="line-height:17px"><span
style="margin:0px;padding:0px;border:0px;vertical-align:baseline;line-height:normal">the
intuitive roster constraints such as "there is at most
one task for each worker at each time", "each task
must be executed by exactly one worker", etc.</span><br>
</li>
<li style="line-height:17px"><span
style="margin:0px;padding:0px;border:0px;vertical-align:baseline;line-height:normal">additional
constraints such as "for every worker, Task X must
take at most 30% of his time" (where Task X is some
unpleasant task)</span></li>
<li style="line-height:17px"><span
style="margin:0px;padding:0px;border:0px;vertical-align:baseline;line-height:normal">additional
constraints such as "after doing Task X, every worker
has to take a break", "Task Y is forbidden after Task
X"</span></li>
</ul>
<li style="line-height:17px"><span
style="margin:0px;padding:0px;border:0px;vertical-align:baseline;line-height:normal">the
objective function - which is to be minimized - can be</span></li>
<ul>
<li style="line-height:17px"><span
style="margin:0px;padding:0px;border:0px;vertical-align:baseline;line-height:normal">the
number of additional workers needed to make the
schedule feasible, or (once there is a feasible
schedule)</span></li>
<li style="line-height:17px">the maximum percentage of
Task X any worker has to do.</li>
</ul>
</ul>
<div
style="margin:0px;padding:0px;border:0px;vertical-align:baseline">Thank
you in advance!</div>
</div>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
Cbc mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Cbc@list.coin-or.org">Cbc@list.coin-or.org</a>
<a class="moz-txt-link-freetext" href="http://list.coin-or.org/mailman/listinfo/cbc">http://list.coin-or.org/mailman/listinfo/cbc</a>
</pre>
</blockquote>
<br>
<pre class="moz-signature" cols="72">--
==================================================
Haroldo Gambini Santos
D.Sc, Computer Science
Universidade Federal de Ouro Preto
<a class="moz-txt-link-freetext" href="http://www.decom.ufop.br/haroldo/">http://www.decom.ufop.br/haroldo/</a></pre>
</body>
</html>