Hot answers tagged

62 votes
Accepted

What are the advantages of commercial solvers like Gurobi or Xpress over open source solvers like COIN-OR or CVXPY?

Disclaimer: I am currently working for a commercial solver company (Gurobi) and have worked before on another commercial solver (IBM CPLEX). Hence, my opinion may be biased, but still I am trying to ...
Tobias Achterberg's user avatar
27 votes

What instances can be solved today by modern solvers (pure LP)?

For sure Julian Hall meant sparse problems. It is possible to solve huge sparse LP problems. If they have sufficiently nice structure your can solve problems with up 231 constraints or variables. ...
ErlingMOSEK's user avatar
  • 3,101
23 votes

What are the advantages of commercial solvers like Gurobi or Xpress over open source solvers like COIN-OR or CVXPY?

No, the situation isn´t the same for OR libraries. There are several reasons for this, among them being Performance: The difference is relevant, with an emphasis on Mixed Integer Programming (linear ...
dhasson's user avatar
  • 1,667
22 votes

What is the purpose of libraries like Pyomo and Google OR tools?

Pyomo is an algebraic modeling language and allows users to easily represent optimization problems at a high-level (by defining variables, constraints, objective, etc.). Pyomo then provides interfaces ...
Bethany Nicholson's user avatar
22 votes

What are the advantages of commercial solvers like Gurobi or Xpress over open source solvers like COIN-OR or CVXPY?

I think the short answer is: speed. Most optimization problems solved in the OR world are computationally intractable, they cannot be solved in reasonable time as the size of the data increases. A ...
Kuifje's user avatar
  • 13.2k
21 votes
Accepted

Using Neural Networks For Solving Optimization Problems

Regarding the paper, it's important to remember that general purpose MIP solvers are meant to be general purpose, hence it's not surprising that they can be improved by tailoring them to the test set, ...
Philipp Christophel's user avatar
20 votes
Accepted

"Best practices" for formulating MIPs

This is an extremely interesting question. I agree with @Richard that you have to try it out. I have seen that tiny changes to a model can make huge differences, but in my experience, more general ...
Marco Lübbecke's user avatar
20 votes

What is the purpose of libraries like Pyomo and Google OR tools?

OR-Tools is a set of solver: A very popular Routing Library built on top of a traditional constraint programming solver An award winning ...
Laurent Perron's user avatar
19 votes

What instances can be solved today by modern solvers (pure LP)?

Hans Mittelmann maintains a well-respected website with benchmarks for optimization software. For LP problems, both simplex and barrier methods are compared. The first instance on the barrier page is ...
Kevin Dalmeijer's user avatar
18 votes

"Best practices" for formulating MIPs

I’m assuming that we want our models to be solved as quickly as possible. If that is the case, then the honest answer is: you need to try the models out and see. To give you a concrete example (see ...
Richard's user avatar
  • 3,459
17 votes

What instances can be solved today by modern solvers (pure LP)?

A couple years ago, I solved an integer program with more than 11,000,000 variables as part of a Kaggle competition. To solve the IP, the MIP solver first solved the LP relaxation, which took about 45 ...
Austin Buchanan's user avatar
17 votes
Accepted

How does a warm start work in LP/MIP?

For the simplex algorithms, warmstarting a solver typically means installing a near-optimal basis and using that as a starting point instead of doing a crash or slack basis as a first step. This works ...
Philipp Christophel's user avatar
16 votes

What do solvers like Gurobi and CPLEX do when they run into hard instances of MIP?

The term "local optimum" is a little misleading here. Assuming your MIP is linear (or at least convex), every local minimum is also a global minimum, so there is no such thing as "getting stuck in a ...
LarrySnyder610's user avatar
15 votes
Accepted

Where can I find resources to learn mathematical modelling for real life operation research problems like combinatorial optimization?

you may get many different answers but the one I have used for 20+ years is Model Building in Mathematical Programming by H.P.Williams Many models are in the OPL CPLEX examples and some other here
Alex Fleischer's user avatar
14 votes
Accepted

Using CPLEX "solution pool" to count feasible points

@prubin has this neat (possibly slightly dated) series of blog posts, Finding All Solutions (or Not), Finding "All" MIP Optima: The CPLEX Solution Pool Solution Pool: "All" Is Not All, which deals ...
fbahr's user avatar
  • 1,016
14 votes

Using CPLEX "solution pool" to count feasible points

The only way (to my knowledge) to get all feasible points for the binary components of a MIP is as follows: Solve the problem. Let $y$ denote the optimal solution Add the following integer cut to ...
Richard's user avatar
  • 3,459
14 votes

CPLEX, number of threads and solving time

What you encounter is called performance variability, it was first (?) observed by Emilie Danna. Yes, B&B is an exact method, but during the run, a lot of heuristic decisions are taken, which ...
Marco Lübbecke's user avatar
13 votes
Accepted

CPLEX non-convex Quadratic Programming algorithms

The best publicly available CPLEX global QP algorithm description I am aware of is the tutorial presentation by Ed Klotz of IBM at the March 2018 INFORMS Optimization conference. Performance Tuning ...
Mark L. Stone's user avatar
13 votes

What do solvers like Gurobi and CPLEX do when they run into hard instances of MIP?

As pointed out by others here, in principle a branch-and-cut based solver can't get stuck, it can just continue until in the worst case it enumerated all integer solutions. Of course that might take ...
Philipp Christophel's user avatar
13 votes
Accepted

Why is there not a feasible solution for a MIP?

Yes - such a question can be answered by looking at the irreducible inconsistent subsystem (IIS). From the Gurobi documentation: An IIS is a subset of the constraints and variable bounds with the ...
CMichael's user avatar
  • 1,333
13 votes

Using Neural Networks For Solving Optimization Problems

SCIP is not slow. SCIP's code is roughly as fast as the commercial alternatives. What makes SCIP seem slower to the user is that, by comparison, the commercial solver heuristics (cuts, primal ...
Nikos Kazazakis's user avatar
12 votes
Accepted

How to get the best bound of large LP problems in CPLEX?

One option I think is to use CPXbaropt (barrier method) that produces intermediate dual (lower, for minimization) bounds. If you are brave enough (and the number ...
Matteo Fischetti's user avatar
12 votes
Accepted

Warm start CPLEX using google or-tools

See answer on https://github.com/google/or-tools/issues/1444 This is not implemented. I welcome pull requests. You can have a look at the code in the Gurobi or Scip interface files.
Laurent Perron's user avatar
12 votes

CPLEX exceeds time limit issue

It could be that you faced the issue described in this bug report. RS03137: CPLEX MAY IGNORE TIME LIMITS ON HIGHLY SYMMETRIC MODELS ON WHICH A NEW INCUMBENT IS FOUND CLOSE TO THE TIME LIMIT. http://...
Xavier Nodet's user avatar
12 votes
Accepted

How can I implement a user-written lazy constraint callback in concert CPLEX with C++?

You have it almost all right, with a few caveats. Let's say I want to implement a Foo Lazy Constraint: ...
Alberto Santini's user avatar
12 votes
Accepted

Do LP solvers convert LPs to standard form?

No, state of the art LP solvers do not do that. They do bring the problem into a computational form that suits the algorithm used. Note that in the case of simplex algorithms, modern solvers use the ...
Philipp Christophel's user avatar
12 votes
Accepted

CPLEX gives different solutions of MILP every run

There are a number of decisions CPLEX makes that can be affected by "randomness". In some cases, CPLEX is actually using a random number generator to make decisions (such as breaking ties). ...
prubin's user avatar
  • 38.8k
11 votes

What instances can be solved today by modern solvers (pure LP)?

The instances I referred to are stochastic LPs (for unit commitment problems)1. We developed a parallel simplex solver exploiting the block structure and used a special hot start procedure. The ...
SparseRunner's user avatar
11 votes

Generating all extreme rays

I'm assuming that your variables ($x$) are nonnegative. If you take a cross-section of the cone by adding a constraints such as $\sum_i x_i = 1$, you get a polytope, and I believe that there is a 1-1 ...
prubin's user avatar
  • 38.8k
11 votes
Accepted

Generating all extreme rays

What is the dimension of your set? If it is not "too big" then you should be googling "double description algorithm". A list of codes that do polyhedral computation is at: https://...
Jeff Linderoth's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible