# Tag Info

40

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 not turn my answer into a marketing and sales pitch. For my PhD thesis I developed the academic solver SCIP, which is still actively maintained and developed by ...

35

@Rob wrote a great and extensive answer, but I would like to add two systems. MiniZinc is a high level CP system that is great for learning CP, prototyping problems as well as testing different solvers. MiniZinc first flatten a MiniZinc (.mzn) model to FlagZinc format (.fzn) and there are quite a few CP solvers that supports the FlatZinc format, e.g. Gecode,...

26

Interesting topic (the question was raised several times by my students as well). My short answer is that adding the lower bound through a cut seems a good idea at first glance, but it creates a very large “unnatural” face where your search is trapped for a long while. Essentially you lose the objective function grip, and do not gain anything. Let me ...

26

... Do you have a set constraint programming solver that you always use, no matter which global constraint you actually need (implementing the needed global constraint yourself if needed)? Find one that is well supported, that you understand to some extent, and that is powerful enough (speed and expressiveness) to suit your future needs. Invest your time in ...

25

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. For instance we solve some huge problems in this GitHub tutorial in a moderate amount of time. Saying some about the solution time based of some simple ...

21

There was an excellent lecture by Bob Bixby in 2015 at the Zuse Institute Berlin (ZIB) as part of Combinatorial Optimization at Work 2015. Bixby founded CPLEX and Gurobi, 2 of the 3 leading commercial MILP+ solvers. The lecture is divided into 3 videos, and gives the actual nitty gritty about what makes LP Simplex family solvers work effectively on large-...

20

OpenSolver is an LP/IP/NLP solver that plugs into Microsoft Excel. I used it for some classroom stuff a while back and was quite pleased with it. If you are interested in metaheuristics, there are quite a few open-source contributions floating around (about which I mostly know nothing). I have used the Watchmaker Framework for Evolutionary Computation (i.e.,...

20

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 changes to a model may have more impact in the end. There are, I think, some guidelines that may help, from algorithmics and theory. Why do we choose "big $M$ as ...

19

Mittelmann benchmarks a number of (LP-)Solvers, some of which are open source. A recent new open source solver is HiGHS.

19

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 L1_sixm1000obs, with 3,082,940 constraints, 1,426,256 variables, and 14,262,560 non-zero elements in the constraint matrix. This problem is solved within the ...

18

Here is the advice in the IBM CPLEX documentation. So this pertains to CPLEX. I don't know to what extent it applies to other solvers. First of all, indicator constraints may not be available in all situations: Indicator Constraints in Optimization The constraint must be linear; a quadratic constraint is not allowed to have an indicator constraint. ...

18

If you have access to MATLAB, I can recommend Marietta (I am a developer of this toolbox), with which you can solve general risk-averse optimal control problems (a generalization of both stochastic and minimax problems), and impose risk constraints (which can serve as convex approximations of probabilistic constraints). As Larry commented above, PYOMO is ...

18

There is a series of three lectures of Robert Bixby (the Bi in Gurobi) on Solving Linear Programs: The Dual Simplex Algorithm. Have a look at the third part Implementing the algorithm where he talks about many details and tricks for implementing general bounds, finding a feasible basis, pricing, and solving linear systems. In particular at about 38:00 he ...

18

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 here): through what I thought was a super-clever reformulation, I was able to remove 85% of the variables in the problem, and I thought that this would make it ...

18

The pitfall is to only focus on performance, will ignoring scalability, maintenance, integration and reliability. Some of these are easier to measure than others: Performance: if I give 2 constraint solvers a - for example a VRP - dataset with 100 visits, which one is better after 5 minutes. See Marco's answer on this question and my blog post on ...

17

Lazy constraints will only be checked when an MIP solution satisfying all other constraints, including integrality, is found. If you provide all your lazy constraints in advance to CPLEX, for example, then your main benefit is that these constraints are only checked against solutions that would otherwise be feasible. However, you may have an exponential ...

17

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 commercial solver will allow you to push back the limit of the size of the problem you are tackling, and to solve the small ones very fast. If you checkout for ...

17

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 and nonlinear). For Linear Programming it's less abrupt but it still exists. You can see empirical results in e.g. the Mittelmann benchmarks for Optimization ...

17

QSopt-Exact by Applegate, Cook, Dash, and Espinoza

16

I compiled a list of solvers I could find last year. Several are COIN-OR-affiliated, but others include Mini-CP, DSP, BiqBin, OSQP, ECOS, and Dakota. (Edit - not all are dedicated LP, see comments below)

16

First of all, usually implementations are centered around the revised dual simplex, not the primal (even though solvers will still use a primal simplex method implementation for some tasks in the solution process). According to Huangfu and Hall and Koberstein, the most important non-textbook techniques for the dual revised simplex appear to be: Dual ...

16

For the evaluation of several solvers you need several solvers a testset of instances a performance measure Several solvers you probably already have in mind. The testset of instances is a bit tricky, because ideally, this is a not too small, not too large, not trivial, not too hard, still representative set of instances (that is, LPs or MIPs) that you ...

16

You may be interest in the blog by @prubin, which has many interesting CPLEX posts: OR in an OB World. I think the best way to become better at using solvers, is by actually using them in your own projects. An interesting project could be to solve a problem with Benders decomposition, or with multithreaded callbacks. This blog post from the above-mentioned ...

16

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 local minimum." When we say that a (meta)heuristic gets "stuck in a local minimum," we are referring to a local minimum as defined by the search neighborhood. ...

15

For Gurobi there seems to be a dual advantage of using general constraints (http://www.gurobi.com/documentation/8.1/refman/constraints.html#subsubsection:GeneralConstraints): Benefit number one - models are easier to create and can be interpreted easily: If a model contains general constraints, then Gurobi adds the respective MIP formulations for those ...

15

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 minutes. Recently, my PhD student Hamid solved an LP with 65 million variables, 65 million constraints, and 325 million nonzeros. It took 5 days to solve ...

15

If your problem is reasonably small then one relatively simple approach is to reformulate the objective as a MIP, under a big-M assumption. Suppose that our objective is to maximize $$\sum_i g_i(x),$$ where each $g_i(x):=\max_j a_j^{i\top} x+b^i_j$ is the maximum of some affine functions. We can model this by introducing auxilliary variables $\theta_i$ such ...

14

Numerical stability (computations going sideways) and numerical tolerances are related but not identical. Floating point arithmetic being subject to rounding and truncation errors (unavoidably), every solver will need to treat things that are "nearly nonnegative", "nearly zero" or "nearly integer" as if they are in fact nonnegative / zero / integer. That ...

14

First of all, the log output of a solver should not change your mind about the formulation you use. Most of the times, one can not imagine how such geometric spaces look like and it is hard to guess the reason for these 'cuts'. However, before formulating a MILP, I guess there are some steps one should follow. Depending on the comments/suggestions I get, I ...

14

I've not seen any efficient use from GPU's for metaheuristics - only experiments that proved their inefficiency for these algorithms. So not the right tool for the job, apparently. Maybe there's a undiscovered technique to make them work efficiently. (I have seen/build efficient use of multiple CPU cores for metaheuristics, even on Local Search with ...

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