Hot answers tagged

35

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 ...


19

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-...


17

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


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 ...


16

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 ...


12

One of the best resource I know is the series of lectures on linear programming that was part of the CO@work workshop 2020. I especially recommend the lectures by Bob Bixby (he is the "bi" in "Gurobi"). They are freely available here, and you'll find some theoretical and practical viewpoints. As for presolving: it is fundamental for MIP, ...


12

The programming language used to setup the problem can matter under two circumstances. One is setup time of the problem this not only differs by programming language but also by the Gurobi interface used See page 30+. The other situations in which it might matter are user callbacks. If one programming language is slower at those time spent in these is not ...


12

Excel remains extensively used in industry for non-OR applications. That means that if you are doing an OR application that does not require access to a database, there's a good chance the data for the application will come to you in either an XLSX or CSV file. On the flip side, when it comes time to convey the solution provided by your application, it is ...


11

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 revised simplex method with lower and upper bounds that does not require standard form. You can get an idea of the computation forms used from "...


10

I suggest GLPK, which has the advantage of being fully open source and easily available everywhere (as a package on most Linux distribution). Run it from the command line with the --exact option. It is limited to LPs though (no MIPs), and not so easy to use directly from a programming language. From the release notes: GLPK 4.13 (release date: Nov 13, 2006) ...


10

There is a new open source solver that looks quite promising, HiGHS: https://www.maths.ed.ac.uk/hall/HiGHS/ But as pointed out by others, for mixed-integer programming problems, at the moment, open-source solvers can't compete on performance and reliability with commercial solvers.


9

Parma Polyhedra Library supports MIP on fractions. It's based on gmp and is used by gcc and Julia among other projects.


9

The videos linked in the other answers contain some of what I will write here but both my writing and the videos are still only scratching on the surface of actual simplex implementations. I'll try to directly answer the questions here: Dual simplex is the most important simplex algorithm right now (because of its performance when solving LPs and because of ...


9

This is where decomposition algorithms (specifically Dantzig-Wolfe can be quite useful). My thesis work and subsequent OSS in COIN provides APIs to do this kind of thing: https://projects.coin-or.org/Dip The basic idea is that the oracle is the graph implementation while the side constraints are modeled as the master constraints in the decomposition ...


9

Diagnosis: Cplex can not find a feasible solution. Interesting, as 1788 binary variables is not extremely large. You can play a bit with mipemphasis option. (In general, I am not a fan of using all kinds of solver options, but this option is one of the very few I use on a regular basis). May be fpheur (feasibility pump) is also worth looking at. There are ...


8

Unfortunately this is a very sparsely documented subject in optimisation literature. The only technical resource I am aware of in my field is this one. Tobias Achterberg's thesis is also a good resource for MILP solver development. The problem is that the number of people who are proficient in solver development is so small that the probability of one of us ...


8

If variable fixings can be derived automatically (e.g. you specified a constraint saying $2x_1=4$ and maybe another saying $x_1+x_2=1$), those variables will be fixed at known values. A smaller problem will then be solved, and we will restore the values for the fixed variables when we report the solution (e.g. in this case $x_1=2$ and $x_2=-1$). The cost of ...


8

MINTO has not been updated in many years. It was innovative in its day, but most of its ideas like fractional cuts and presolve were incorporated years ago into commercial MILP solvers like CPLEX and Gurobi. For most applications today, the best option is one of the major commercial solvers like CPLEX or Gurobi; these are available at no-cost for academic ...


7

I am not familiar with objective integrality cuts, but I know that CPLEX has the option to set the parameter absolute objective difference cutoff. If you set this parameter to 1, CPLEX will terminate the search if the difference between the best integer solution and the best bound is strictly less than 1.


7

In general ILP solvers are not as efficient in solving the Maximum Matching problem. A comparison of efficient matching algorithm implementations, as well as an ILP formulation for the Maximum Cardinality Matching Problem and the Minimum Weight perfect matching problem can be found in Figures 5 and 6 of this paper: Dimitrios Michail, Joris Kinable, Barak ...


7

Many many people know Excel and use Excel. So many OR projects start with some Excel spreadsheet. And that is why being able to read from and write to Excel is key. You may even start the project with the Excel solver. Moreover Excel is a common tool when companies choose plugin optimization instead of packages, custom or tailored optimization.


6

(Full disclosure: I run a solver company) The state of the art Unlike ML, in the optimisation space commercial software is unfortunately on average superior to open-source alternatives. This does not mean that open source can't be a perfectly viable choice. Open source solvers can and do solve very difficult problems. It just means that commercial solvers ...


6

You could also use polymake which includes a few exact linear programming libraries (including my own one). It should also be possible to compile SoPlex with GMP support, but I actually never tried it.


6

COUENNE An open-source deterministic global MINLP solver. BONMIN An open-source local MINLP solver. Octeract Engine (our own solver) is a commercial massively parallel deterministic global MINLP solver that is free for academics. What's more interesting is that starting next month the 1-core version of Octeract Engine will also be free for commercial ...


6

You could apply the following trick inside your objective function: x1 = min(x[1],x[2]) x2 = max(x[1],x[2]) Now x1 <= x2 automatically holds and you don't need the constraint. (Assuming you can live with <= instead of <).


6

The Mittlemann benchmarks are an excellent benchmark as ever in particular these two: Benchmark of Barrier LP solvers Large Network-LP Benchmark (commercial vs free) Note that Pyomo doesn't have bindings for most of these locally. If you are just looking for high-level modeling language and are not tied to Python you could use the JuMP modeling language ...


5

To fix a variable use x.fx(i) = 1. To unfix: x.lo(i) = 0; x.up(i) = 1;. To relax an integer/binary variable you can use: x.prior(i)=INF; Documentation of this can be found at the obvious place: https://www.gams.com/latest/docs/UG_Variables.html. Here is an example of how to use this.


5

I agree with Rob Pratt about QSopt-Exact. That's probably the right thing to do if you're doing larger scale solves. I think that you can also do exact LP in Sage (using fractions). Sage is based on Python, so this would be easy to code in, but you do have to download the whole Sage installation at this point. But I don't think this would be quite as ...


5

I think by MIP you mean MILP which stands for mixed integer linear program(ming). Q1. Is there any reasonable way to use MINLP engine instead of MIP to solve such problems? Of course you can use a MINLP solver, but such solvers may eventually use some form of linearization. I would first try to linearize a non-linear formulation (if possible) and then use a ...


5

Pushing @Erwin's idea further, I got faster solve times by instead introducing variables ry and qx: for j in b: for k in c: o += ry[j][k] == r[k] *(xsum(y[k][jj] for jj in b if jj <= j)) for j in b: for k in c: o += qx[j][k] == xsum(( xsum (q[i][k]* x[i][jj] for i in a )for jj in b if jj <=j)) for j in b: for k in c: ...


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