4
$\begingroup$

I originally asked a question here and they suggested that I crosspost it to the OR stack exchange, so that is what I am doing (hopefully correctly?). Here is the question I asked there:

"I know it depends on the specific problem instance, but approximately how large of an MIP problem can we write and still be guaranteed that an optimization solver will find a solution? For instance, if we have a mixed integer program with 1,000 variables and 1,000 constraints, can we be guaranteed that no matter what the variables and constraints are, modern optimization software will be able to spit out a solution in a reasonable time frame (defined as 1 month or less on a standard computer)? What about 1 million variables and constraints, or a billion variables and a million constraints, etc."

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ No mtter how good the solver, worst case is always possible. Read yalmip.github.io/slowmilp . "with our solver we might, in the worst case, only manage to solve a problem with 72 binary variables if we are given the age of the universe to finish. " $\endgroup$
    – Mark L. Stone
    Dec 28, 2022 at 19:18
  • $\begingroup$ With integer variables, even 3 variables might be enough $\endgroup$
    – fontanf
    Dec 28, 2022 at 20:14

1 Answer 1

Reset to default
2
$\begingroup$

Basically modern solvers like Gurobi have no limit in terms of capacity (talking of full license). While I wasn't able to find a specific reference in Gurobi Manual but found this confirmation. CPLEX also has no meaningful limit. Solving time depends upon machine RAM, sparsity of constraint matrix, linearity of the objective, integer variables, Python API calls like access/manipulation on Pandas and specific class of problems that are NP-Hard like Travelling Salesman Problem with hundreds of nodes and edges.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ At some point, the use of 16 bit integers to index things will impose an implicit limit on number of rows and columns. It's likely the part about getting a solution centuries after the problem owner has shuffled off this mortal coil will kick in first. $\endgroup$
    – prubin ♦
    Dec 28, 2022 at 19:03
  • 4
    $\begingroup$ @prubin Solvers have started using 64-bit integers to get beyond 2 billion nonzeros. $\endgroup$
    – Erwin Kalvelagen
    Dec 28, 2022 at 22:57
  • $\begingroup$ Yes that's what I read in CPLEX manual. Hello Erwin, are you the same Erwin from Amsterdam optimization? $\endgroup$
    – Sutanu
    Dec 28, 2022 at 23:05
  • $\begingroup$ @Sutanu, Dr. Kalvelagen profile can be found here. :) $\endgroup$
    – A.Omidi
    Dec 30, 2022 at 21:32
  • $\begingroup$ Thank you Abbas. Pleasant to interact with you and Dr. Kalvelagen. I refer a lot to yetanothermathprogramming consultant blog. $\endgroup$
    – Sutanu
    Dec 30, 2022 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy