Hot answers tagged

33

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


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

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


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

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

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


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

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


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

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


13

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

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


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


12

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


12

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


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


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


10

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 biggest solved had 500,000,000 variables and constraints, but took only 41000 iterations. So, highly specialised problems and solution method, and far from reality! ...


10

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


10

Gurobi and CPLEX use (very sophisticated) variants of the branch-and-bound algorithm. In Mixed Integer Programs, there can be both continuous and integer variables. It turns out that the integer variables are the complicating factor: without integer variables, what remains is a Linear Program (LP). LPs are always convex, which implies that every local ...


10

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.


10

CPLEX has a conflict refiner. The instructions for invoking it are at How to invoke the conflict refiner.


10

You have it almost all right, with a few caveats. Let's say I want to implement a Foo Lazy Constraint: #include <ilocplex/ilocplex.h> #include <ilocplex/ilocplexi.h> struct Foo : IloCplex::LazyConstraintCallbackI { // Your code goes here... }; There are three main things you need to put inside your class; two of these are documented (more or ...


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