MIP: Slow Performance on "Small" Problem
357 views
Skip to first unread message
Mathieu Vandenberghe
Mar 31, 2017, 5:48:23 AM3/31/17
to Gurobi Optimization
Hello,
I'm doing research into a scheduling problem and using Gurobi to solve it, but I'm seeing a very low level of performance that doesn't really make sense to me.
The scheduling problem I have consists of determining the optimal order of M tasks that are scheduled on N machines. The tasks come pre-assigned to machines, so the model just has to figure out an optimal order for the M/N tasks assigned to it.
To simplify the model down to what I think is useful:
- The main decision variable is a binary precedence matrix Y, and Y_{ij} determines whether operation i is scheduled before j. As scheduling order only has meaning within a particular room, the Y matrix is a block diagonal matrix that has N blocks with information (each room's schedule) and 0 elsewhere.
- The set of precedence relations Y is 'multiplied' by their respective durations and place in the schedule, which leads to a set of completion times C_i.
- The objective function is something of the form: minimize C_j - C_i for all i,j; i.e. minimise the largest interval between completion times. (In my problem some i,j are excluded due to various criteria, but that will take us rather far afield.)
I'm testing out a small problem now (3 machines, which have 5 tasks each; 15 total), and Gurobi has a really hard time dealing with it.
I find this strange because there are only 5!*5!*5! (=1.7 million) possible schedules to consider, which is relatively limited. As I'm typing now, Gurobi has been searching for over an hour and is nearing 2 million explored nodes. I think that a brute force search would have finished calculating all the possible permutations by now, so I'm confused why GUROBI seems to be overcomplicating things.
Here's the final part of the log:
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
1646325 44201 infeasible 90 25.13500 18.10467 28.0% 40.2 3500s
1647434 43785 18.10467 36 77 25.13500 18.10467 28.0% 40.2 3506s
1651829 44232 infeasible 67 25.13500 18.10467 28.0% 40.2 3510s
1652667 43721 infeasible 83 25.13500 18.10467 28.0% 40.2 3516s
1655063 44149 infeasible 44 25.13500 18.10467 28.0% 40.2 3520s
1657652 44660 18.10467 57 72 25.13500 18.10467 28.0% 40.2 3526s
1660090 44957 infeasible 82 25.13500 18.10467 28.0% 40.2 3530s
1662427 44807 infeasible 78 25.13500 18.10467 28.0% 40.2 3535s
1663120 44458 18.10467 62 75 25.13500 18.10467 28.0% 40.2 3540s
1665567 44558 infeasible 66 25.13500 18.10467 28.0% 40.2 3546s
1667816 44584 infeasible 52 25.13500 18.10467 28.0% 40.2 3550s
1670435 44650 18.10467 62 70 25.13500 18.10467 28.0% 40.2 3555s
1671107 44396 18.10467 66 41 25.13500 18.10467 28.0% 40.2 3560s
1673811 44494 infeasible 85 25.13500 18.10467 28.0% 40.2 3565s
1674469 44206 18.10467 70 54 25.13500 18.10467 28.0% 40.3 3570s
1677689 44392 18.10700 87 57 25.13500 18.10467 28.0% 40.2 3575s
1680965 44644 18.10467 54 59 25.13500 18.10467 28.0% 40.2 3581s
1684244 44234 infeasible 98 25.13500 18.10467 28.0% 40.2 3586s
1686888 44543 infeasible 71 25.13500 18.10467 28.0% 40.2 3590s
1689337 44441 infeasible 50 25.13500 18.10467 28.0% 40.2 3595s
1690120 43938 infeasible 75 25.13500 18.10467 28.0% 40.2 3600sMy observations:
1) Gurobi probably found the optimal solution already (25.135) but is having trouble terminating. While in this particular case I could manually terminate, I want to be able to solve larger instances than this so I actually want to get to optimality (or a good chance of it).
2) Gurobi seems obsessed with finding solutions that are very close to the theoretically possible lower bound that I gave him (18.104), but he seems to waste a lot of time on nodes which are either infeasible, or reach the theoretical lower bound but violate lots of (54, 57, 59) integrality constraints while doing so. I'm assuming these integrality constraints are mainly values of Y.
3) The bound is not moving at all, but I guess this is because of the way the problem is structured (it's hard to put a tight lower bound on C_j - C_i without going through all the possible combinations...).\
My sense is that with some more detailed instructions, Gurobi could solve things much faster. Something like: "O is the critical decision variable; don't violate too many integrality constraints because it's pointless" etc.
I've tried experimenting with different solver variables (MIPFocus, VarBranch, Heuristics) and assigning a higher BranchPriority to Y, but I'm not sure what else to try.
Suggestions greatly appreciated!
Cheers,
Mathieu
Tobias Achterberg
Mar 31, 2017, 6:04:15 AM3/31/17
to gur...@googlegroups.com
Hi Mathieu,
scheduling is very hard for MIP technology, because the main work-horse (the LP
relaxation) is pretty much useless for scheduling. This is because the LP
relaxation can just squeeze jobs together in some fractional form, which makes
it easy to find feasible LP solutions that have very good objective values, even
though there is no feasible integer solution in the neighborhood of these LP
solutions.
If this is really a pure scheduling problem, then you might be better off using
a CP solver. Scheduling is the one problem class (maybe the only one?) where CP
is better suited than MIP (for the above reasons). But if you have other
constraints (like the assignment to the machines), then it can already be better
to use MIP.
In your particular model, does the problem decompose? I.e., can you just solve
the scheduling problems for each of the machines separately? If so, you should
do it. Even though Gurobi will detect and exploit this structure, it is still
better to solve three individual problems than one with three blocks.
Finally, I would be very interested in your problem instance, if you are willing
to share it. You could also contribute it to the new MIPLIB 2017:
https://miplibsubmissions.zib.de/
Best regards,
Tobias
On 03/31/17 11:28, Mathieu Vandenberghe wrote:
> Hello,
>
> I'm doing research into a scheduling problem and using Gurobi to solve it, but
> I'm seeing a very low level of performance that doesn't really make sense to me.
>
> The scheduling problem I have consists of determining the optimal order of M
> tasks that are scheduled on N machines. The tasks come pre-assigned to machines,
> so the model just has to figure out an optimal order for the M/N tasks assigned
> to it.
> To simplify the model down to what I think is useful:
> - The main decision variable is a _binary precedence matrix Y_, and Y_{ij}
> 167110744396 18.10467 66 41 25.13500 18.10467 28.0% 40.23560s
> 167768944392 18.10700 87 57 25.13500 18.10467 28.0% 40.23575s
> 168096544644 18.10467 54 59 25.13500 18.10467 28.0% 40.23581s
> 168424444234infeasible 98 25.13500 18.10467 28.0% 40.23586s
> 168688844543infeasible 71 25.13500 18.10467 28.0% 40.23590s
> 168933744441infeasible 50 25.13500 18.10467 28.0% 40.23595s
> 169012043938infeasible 75 25.13500 18.10467 28.0% 40.23600s
>
> ---
> You received this message because you are subscribed to the Google Groups
> "Gurobi Optimization" group.
> To unsubscribe from this group and stop receiving emails from it, send an email
> to gurobi+un...@googlegroups.com <mailto:gurobi+un...@googlegroups.com>.
> For more options, visit https://groups.google.com/d/optout.
scheduling is very hard for MIP technology, because the main work-horse (the LP
relaxation) is pretty much useless for scheduling. This is because the LP
relaxation can just squeeze jobs together in some fractional form, which makes
it easy to find feasible LP solutions that have very good objective values, even
though there is no feasible integer solution in the neighborhood of these LP
solutions.
If this is really a pure scheduling problem, then you might be better off using
a CP solver. Scheduling is the one problem class (maybe the only one?) where CP
is better suited than MIP (for the above reasons). But if you have other
constraints (like the assignment to the machines), then it can already be better
to use MIP.
In your particular model, does the problem decompose? I.e., can you just solve
the scheduling problems for each of the machines separately? If so, you should
do it. Even though Gurobi will detect and exploit this structure, it is still
better to solve three individual problems than one with three blocks.
Finally, I would be very interested in your problem instance, if you are willing
to share it. You could also contribute it to the new MIPLIB 2017:
https://miplibsubmissions.zib.de/
Best regards,
Tobias
On 03/31/17 11:28, Mathieu Vandenberghe wrote:
> Hello,
>
> I'm doing research into a scheduling problem and using Gurobi to solve it, but
> I'm seeing a very low level of performance that doesn't really make sense to me.
>
> The scheduling problem I have consists of determining the optimal order of M
> tasks that are scheduled on N machines. The tasks come pre-assigned to machines,
> so the model just has to figure out an optimal order for the M/N tasks assigned
> to it.
> To simplify the model down to what I think is useful:
> determines whether operation i is scheduled before j. As scheduling order only
> has meaning within a particular room, the Y matrix is a block diagonal matrix
> that has N blocks with information (each room's schedule) and 0 elsewhere.
> - The set of precedence relations Y is 'multiplied' by their respective
> durations and place in the schedule, which leads to a set of completion times C_i.
> - The objective function is something of the form: minimize C_j - C_i for all
> i,j; i.e. minimise the largest interval between completion times. (In my problem
> some i,j are excluded due to various criteria, but that will take us rather far
> afield.)
>
> I'm testing out a small problem now (3 machines, which have 5 tasks each; 15
> total), and Gurobi has a really hard time dealing with it.
> I find this strange because there are only 5!*5!*5! (=1.7 million) possible
> schedules to consider, which is relatively limited. As I'm typing now, Gurobi
> has been searching for over an hour and is nearing 2 million explored nodes. I
> think that a brute force search would have finished calculating all the possible
> permutations by now, so I'm confused why GUROBI seems to be overcomplicating things.
>
> Here's the final part of the log:
>
> |
> ExplUnexpl| Obj DepthIntInf|Incumbent BestBd Gap|It/NodeTime
>
> 164632544201infeasible 90 25.13500 18.10467 28.0% 40.23500s
> 164743443785 18.10467 36 77 25.13500 18.10467 28.0% 40.23506s
> has meaning within a particular room, the Y matrix is a block diagonal matrix
> that has N blocks with information (each room's schedule) and 0 elsewhere.
> - The set of precedence relations Y is 'multiplied' by their respective
> durations and place in the schedule, which leads to a set of completion times C_i.
> - The objective function is something of the form: minimize C_j - C_i for all
> i,j; i.e. minimise the largest interval between completion times. (In my problem
> some i,j are excluded due to various criteria, but that will take us rather far
> afield.)
>
> I'm testing out a small problem now (3 machines, which have 5 tasks each; 15
> total), and Gurobi has a really hard time dealing with it.
> I find this strange because there are only 5!*5!*5! (=1.7 million) possible
> schedules to consider, which is relatively limited. As I'm typing now, Gurobi
> has been searching for over an hour and is nearing 2 million explored nodes. I
> think that a brute force search would have finished calculating all the possible
> permutations by now, so I'm confused why GUROBI seems to be overcomplicating things.
>
> Here's the final part of the log:
>
> |
> ExplUnexpl| Obj DepthIntInf|Incumbent BestBd Gap|It/NodeTime
>
> 164632544201infeasible 90 25.13500 18.10467 28.0% 40.23500s
> 165182944232infeasible 67 25.13500 18.10467 28.0% 40.23510s
> 165266743721infeasible 83 25.13500 18.10467 28.0% 40.23516s
> 165506344149infeasible 44 25.13500 18.10467 28.0% 40.23520s
> 165765244660 18.10467 57 72 25.13500 18.10467 28.0% 40.23526s
> 165266743721infeasible 83 25.13500 18.10467 28.0% 40.23516s
> 165506344149infeasible 44 25.13500 18.10467 28.0% 40.23520s
> 166009044957infeasible 82 25.13500 18.10467 28.0% 40.23530s
> 166242744807infeasible 78 25.13500 18.10467 28.0% 40.23535s
> 166312044458 18.10467 62 75 25.13500 18.10467 28.0% 40.23540s
> 166242744807infeasible 78 25.13500 18.10467 28.0% 40.23535s
> 166556744558infeasible 66 25.13500 18.10467 28.0% 40.23546s
> 166781644584infeasible 52 25.13500 18.10467 28.0% 40.23550s
> 167043544650 18.10467 62 70 25.13500 18.10467 28.0% 40.23555s
> 166781644584infeasible 52 25.13500 18.10467 28.0% 40.23550s
> 167110744396 18.10467 66 41 25.13500 18.10467 28.0% 40.23560s
> 167381144494infeasible 85 25.13500 18.10467 28.0% 40.23565s
> 167446944206 18.10467 70 54 25.13500 18.10467 28.0% 40.33570s
> 167768944392 18.10700 87 57 25.13500 18.10467 28.0% 40.23575s
> 168096544644 18.10467 54 59 25.13500 18.10467 28.0% 40.23581s
> 168424444234infeasible 98 25.13500 18.10467 28.0% 40.23586s
> 168688844543infeasible 71 25.13500 18.10467 28.0% 40.23590s
> 168933744441infeasible 50 25.13500 18.10467 28.0% 40.23595s
> 169012043938infeasible 75 25.13500 18.10467 28.0% 40.23600s
> |
>
> My observations:
>
> 1) Gurobi probably found the optimal solution already (25.135) but is having
> trouble terminating. While in this particular case I could manually terminate, I
> want to be able to solve larger instances than this so I actually want to get to
> optimality (or a good chance of it).
> 2) Gurobi seems obsessed with finding solutions that are very close to the
> theoretically possible lower bound that I gave him (18.104), but he seems to
> waste a lot of time on nodes which are either infeasible, or reach the
> theoretical lower bound but violate lots of (54, 57, 59) integrality constraints
> while doing so. I'm assuming these integrality constraints are mainly values of Y.
> 3) The bound is not moving at all, but I guess this is because of the way the
> problem is structured (it's hard to put a tight lower bound on C_j - C_i without
> going through all the possible combinations...).\
>
> My sense is that with some more detailed instructions, Gurobi could solve things
> much faster. Something like: "O is the critical decision variable; don't violate
> too many integrality constraints because it's pointless" etc.
> I've tried experimenting with different solver variables (MIPFocus, VarBranch,
> Heuristics) and assigning a higher BranchPriority to Y, but I'm not sure what
> else to try.
>
> Suggestions greatly appreciated!
>
> Cheers,
> Mathieu
>
> --
>
> My observations:
>
> 1) Gurobi probably found the optimal solution already (25.135) but is having
> trouble terminating. While in this particular case I could manually terminate, I
> want to be able to solve larger instances than this so I actually want to get to
> optimality (or a good chance of it).
> 2) Gurobi seems obsessed with finding solutions that are very close to the
> theoretically possible lower bound that I gave him (18.104), but he seems to
> waste a lot of time on nodes which are either infeasible, or reach the
> theoretical lower bound but violate lots of (54, 57, 59) integrality constraints
> while doing so. I'm assuming these integrality constraints are mainly values of Y.
> 3) The bound is not moving at all, but I guess this is because of the way the
> problem is structured (it's hard to put a tight lower bound on C_j - C_i without
> going through all the possible combinations...).\
>
> My sense is that with some more detailed instructions, Gurobi could solve things
> much faster. Something like: "O is the critical decision variable; don't violate
> too many integrality constraints because it's pointless" etc.
> I've tried experimenting with different solver variables (MIPFocus, VarBranch,
> Heuristics) and assigning a higher BranchPriority to Y, but I'm not sure what
> else to try.
>
> Suggestions greatly appreciated!
>
> Cheers,
> Mathieu
>
>
> ---
> You received this message because you are subscribed to the Google Groups
> "Gurobi Optimization" group.
> To unsubscribe from this group and stop receiving emails from it, send an email
> to gurobi+un...@googlegroups.com <mailto:gurobi+un...@googlegroups.com>.
> For more options, visit https://groups.google.com/d/optout.
Mathieu Vandenberghe
Mar 31, 2017, 9:59:31 AM3/31/17
to Gurobi Optimization
Hi Tobias,
Thank you for your comments, even though you confirm my fears :)
The problem is indeed purely a scheduling problem (at the current stage of research, anyway).
And unfortunately, as the objective function is about minimizing the intervals between the completion times of different rooms, I haven't found a way of decomposing the problem.
It is after all the interaction of the room's schedules that creates the objective function.
So it does seem that CP solvers might be worth a shot, thank you for that suggestion!
Are there any particular ones you would recommend?
I'd be happy to contribute the problem instance as well.
I guess you need more information than just the .lp file though? If so it will take some time :)
Kind regards,
Mathieu
Op vrijdag 31 maart 2017 11:48:23 UTC+2 schreef Mathieu Vandenberghe:
Op vrijdag 31 maart 2017 11:48:23 UTC+2 schreef Mathieu Vandenberghe:
Tobias Achterberg
Mar 31, 2017, 12:10:20 PM3/31/17
to gur...@googlegroups.com
Gecode is said to be good, but I have no experience with this:
http://www.gecode.org/
Regards,
Tobias
http://www.gecode.org/
Regards,
Tobias
WG Gerwig
Mar 28, 2018, 6:35:11 AM3/28/18
to Gurobi Optimization
Hey Mathieu,
can you please share your experience with using gecode? i am currently struggeling with a very similar problem and i am very interested in how you made it work :)
Kind regards
Christin
can you please share your experience with using gecode? i am currently struggeling with a very similar problem and i am very interested in how you made it work :)
Kind regards
Christin
Reply all
Reply to author
Forward
0 new messages