2

I am solving a Mixed Integer Programming (MIP) problem by using the GNU glpk solver. The problem contains about 1,625 columns and 507 rows which I believe it is not a large-scale problem. However, glpk was not able to provide a solution after more than 9 hours solving the problem.

I was wondering if anyone ever encounters a similar problem or have any suggestion to speed up the calculation. Otherwise, do you have any other MIP solver for recommending that I can try with few changes in my source code?

Arton Dorneles
  • 1,629
  • 14
  • 18
sensenli
  • 59
  • 1
  • 5
  • Do you solve a (Mixed) _Integer_ Program, as stated in the title and your first sentence, or just a _linear_ program (lp), as you are looking for an lp-solver? – Gregor Jul 22 '14 at 08:28
  • Without more details about the formulation, it would be tough for us to give specific recommendations about how to improve your model to make it faster. The rest of the question appears to be asking for suggested solvers, which is off-topic for SO. – josliber Jul 22 '14 at 13:57

2 Answers2

7

First of all, even smaller MIPs than yours can be difficult to solve. glpk generally scores towards the bottom mixed-integer benchmarks. If you are looking for free solvers, you should probably try one of the others mentioned in the benchmark, like coin-or's cbc, or the partially free scip.

If you are an academic, or the problem is important for you to solve, you can try one of the commercial solvers. Gurobi is free for academics. It, cplex (IBM) and xpress (FICO) are the main commercial solvers.

The solution time of solving a MIP is a strong function of the quality of your formulation. You don't have any specifics about your model, but depending on the type of model you are solving, there might be a lot of publications on good MIP formulations for your problem.

Community
  • 1
  • 1
David Nehme
  • 21,379
  • 8
  • 78
  • 117
  • Do you have any recommendation on good example of MIP formulation which will make the solver run faster? thx – sensenli Jul 23 '14 at 02:15
2

I'm not guaranteeing a solution, but it could be numerical instability issues.

I've seen an MIP model run indefinitely as you describe, but looking at the log it's within 1e-7 of optimal. In my case, changing the data caused the problem to run immediately (<2 secs.). Some data sets terminate quickly, some never finish. I believe this is a known issue with glpk (and python).

Alternatively, try removing constraints 1 at a time. If it speeds up, you know where to work on reformulation.

Dylan Cross
  • 544
  • 2
  • 6
  • 14