[Gurobi] Approximating Solve Time for Binary Integer Problem with 100,000 variables, 1,000 constraints?

[Chris]

I am considering trying to solve a scheduling problem using Gurobi
Cloud. However, I am just getting started with linear programming,
and I am trying to understand whether Gurobi can solve a problem of
the size I am dealing with. The size of the problem is:

All of the variables I am solving for are 0 or 1, they represent
decisions to use or not use a particular schedule. My objective
function would have around 100,000 of these 0 or 1 variables, each
with a coefficient representing the score for that decision, like:

752*x1 + 537*x2 + ... 432*x100,000

I'd like to maximize the overall function. Many of my constraints
will be pure equality, like:

x1 + x5 + ... x9,324 = 2 (or some other small number)

There will be around 100 constraints like that, each with around 1000
variables, and another 800 constraints like that, each with 3000 to
6000 variables

I would also have around 100 constraints with inequalities and around
1000 variables, like:

x2 + x10 + ... x9,720 < 10

My question is - how likely is it that Gurobi can solve a problem like
this in less than 12 hours on AWS? Is my problem obviously workable
in that time frame? Obviously unworkable?

Thanks,
Chris






--
Subscription settings: http://groups.google.com/group/gurobi/subscribe?hl=en

[Greg Glockner]

Unfortunately, there's no way to predict the time it will take Gurobi to solve this instance on any computer, including the EC2 cloud. That's the nature of integer programming. Here are some suggestions:

1) Create some smaller test problems and gauge how long they take to solve
2) Set the TimeLimit parameter
3) Set the MIPGap or MIPGapAbs parameters

You may also be able to improve MIP performance by following the advice in the MIP model parameter guidelines, which can be found at:

http://www.gurobi.com/doc/30/refman/node492.html

[Chris]

Thanks very much for taking the time to respond. I wasn't sure if the
size of my problem was obviously prohibitive. It sounds like it could
go either way, and in that case it is worth trying. I will give it a
try on the cloud in the next few weeks and see what kinds of results
it produces.

Thanks,
Chris

[Greg Glockner]

Unfortunately, there's really no way to know. There are models with 100K variables and 1K constraints that solve in seconds, and there are models that large that cannot be solved to optimality in days. Such is the nature of integer programming, which is NP-hard.