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


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


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

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


19

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, either using ML or some other form of automatic tuning. MIP solvers make many decisions while solving a problem and I guess it's quite natural to assume that ...


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


17

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 to a variety of optimization solvers including Gurobi and CPLEX. This allows an optimization model to be formulated once and then a user can experiment with ...


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

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


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


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

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


14

@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 with the hassle of collection all MIP solutions in CPLEX's solution pool. While this doesn't exactly answer your question, it still might provide helpful insights ...


14

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 your model: \begin{equation} \sum_{j\in J}y_j - \sum_{t\in T}y_t \leq |J|-1 \end{equation} where $J$ is the set of indices where $y_j = 1$, i.e. $J = \{j\mid y_j = ...


14

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 best if the starting basis is already primal feasible (for the primal simplex algorithm) or dual feasible (for the dual simplex) because that eliminates the ...


13

OR-Tools is a set of solver: A very popular Routing Library built on top of a traditional constraint programming solver An award winning CP-SAT solver that combines Constraint Programming techniques, SAT solver search and Boolean centric approach, MIP solver techniques like cuts and linear relaxation, and Large Neighborhood search A Simplex solver: GLOP A ...


13

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 following properties: the subsystem represented by the IIS is infeasible, and if any of the constraints or bounds of the IIS is removed, the subsystem ...


13

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 variable to branch on, which node to select, which primal heuristic to run... Many of these decisions are based on some sort of score. When several entities (like ...


12

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.


12

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://www-01.ibm.com/support/docview.wss?uid=swg1RS03137 The bug was fixed in version 12.9, which was released earlier in the year.


12

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 for Cplex’s Spatial Branch-and-Bound Solver for Global Nonconvex (Mixed Integer) Quadratic Programs ABSTRACT: MILP solvers have been improving for more than ...


12

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 of variables is not really huge) you can declare the LP to be a MIP with no integer variables (or add a fictitious one), start with few randomly-chosen constraints and use lazycallback to add the ...


11

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 correspondence between extreme rays of the original cone and extreme points of the polytope. IIRC, there are programs for computing all extreme points of a ...


11

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://www.cs.mcgill.ca/~fukuda/soft/polyfaq/node41.html. If the dimension is large, then you probably can't enumerate all extreme rays, there are likely to be too ...


11

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 forever. That said, sophisticated solvers have all kinds of tricks to avoid "getting stuck", meaning not having any progress for a long time. One such trick ...


11

Depending on the journal, CPLEX may be so well known that it is acceptable to omit the reference. It is always important to include a version number ("we use CPLEX 12.9"), as performance can differ significantly between versions.


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


11

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 heuristics, branching, tuning) are superior. Therefore, that paper actually makes a very sound comparison: "What if we had a machine figure out the heuristics ...


10

Perhaps you are only talking about MILPs, but you don't say, so I will say something of interest for MINLPs. Regarding point 1: Suppose your model has a convex nonlinear inequality constraint, $f(x) \le c$, i.e., $f(x)$ is convex. and It is known that the constraint will be active at the optimum, of any continuous relaxation i.e., $f(x) = c$, for ...


10

In addition to previous answers, I like to cite the following book, which discuss in details several different options (and kind of good practices) to model different common applications: Model Building in Mathematical Programming, by H. Paul Williams. March, 2013. ISBN: 978-1-118-44333-0. Every chapter is very interesting and is worth of (re)reading ...


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