Tag Info

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

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

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

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

Performing parallel operations deterministically often leads to some overhead and threads waiting or idling - this is the spin time. A non-deterministic or opportunistic parallel mode does not have this overhead but also does not guarantee reproducibility - this is enabled via Method=3. EDIT: When solving very similar models you should also just check what ...

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

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

12

You can use model.write("mymodel.lp") to generate an LP file (similarly for .mps and other common formats) that you can pass in open source solvers, provided that they can read that respective format. Since LP files are also human readable it is not too hard to transform a gurobipy model script into a script using only plain Python file operations that ...

12

I can't address the specifics of Python, Pyomo, Gurobi or GAMS, but I can address the general question of using a modeling language (such as GAMS) versus building the model directly in a general programming language (such as Python) via a solver API. Models written in a modeling language (say GAMS) tend to be easier to read and easier to relate to a problem ...

11

Here is the complete implementation for the above-mentioned model. from gurobipy import * import numpy as np # Parameters needed are: # (1) the total number of jobs (n). Here I denote it by "NumofJobs" # (2) the total number of machines (m). Here I denote it by "NumofMachines" # (3) the processing times. Here I use a numpy matrix: "...

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

I don't think directly, but one way to model that would be to: define a parameter as the vector of the possible values: $p = [0,50,100]$ define three binary decision variables that each correspond to whether a value in the set is selected ($y_i \in \{0,1\}, i = 1,2,3$) enforce constraints: $\sum_{i\in \{1,2,3\} } y_i = 1$ (select exactly 1 of the values ...

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

Complementing the other good answers, please note that presolve is concerned with problem input data and tries to eliminate variables using logical reductions. While a huge reduction in the number of variables as in your case might indicate that the model is not as compact as you would desire, input data could be the reason as well. For example, consider a ...

10

Dual simplex is the method of choice for resolving an LP if you have an optimal solution and you change the problem by modifying the feasible region. Ranging the RHS, adding cuts or branching in MIP, Benders decomposition, etc. are examples where that happens. Some other problems are easy to start in the dual method, for example, when all variables have ...

10

Assuming you are using more than a single thread, then Gurobi performs all work you code in the callbacks with a single thread. All remaining threads process the branch and bound nodes (without doing the callbacks). When your user cuts are added is then determined by some black box magic of Gurobi. To be specific, suppose we have 4 threads. Then, 3 of the ...

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

MILPs are NP-hard. People make a big deal about NP-hardness for a reason - in the worst case they are very, very hard to solve. There is a short, easy to understand exposition of this by @Johan Löfberg : Why is my MILP not finishing Johan provides an example: For a MILP with 72 binary variables, in the worst case, a MILP solver will have to solve $2^{72}$ ...

9

If you do a lot of looping in Python to build your model, then model building is going to be slow. We have illustrated this for Pyomo (and the same undoubtedly holds for Pulp) in a notebook that implements the socalled Wasserstein model. Note this shows Mosek Fusion and Cvxpy is much faster than Pyomo for this particular model. We tried to use the fast ...

9

There exist various reasons why a solver could not find the optimal solution. You must always check why a solver terminated. Typical reasons are: optimal solution was found termination criteria was reached, e.g. time limit or a limit on the optimality gap solver proved that problem is infeasible Popular solvers such as cplex/gurobi can report their status ...

9

You could try changing the parameter mipfocus to 2 or 3 (https://www.gurobi.com/documentation/9.0/refman/mipfocus.html) in order to let Gurobi focus more on improving the bound or proving optimality. You can also try to set Cuts (https://www.gurobi.com/documentation/9.0/refman/cuts.html) to 2 in order to let Gurobi be more aggressive with the Cuts. But ...

9

If you have a recent enough version of Gurobi, there is a tuning tool that tries to find better parameter sets than the default settings. For best results, run it for a while (at least overnight) and run it with a few different instances of your problem. Here is some example code you can use to run it. def tune(model, time_limit=-1, trials_per_setting=3): ...

8

Based on the documentation, this level of information retrieval from a specific branch-and-bound node is currently not available. If this was possible, we'd have to use a callback function (python documentation, python examples) to get the information from the relevant MIP branch-and-bound tree. We'd need where == GRB.Callback.MIPNODE since we want ...

8

In addition to @Michael's comment you have to distinguish between the algorithm used to solve the root node of a problem and the algorithm used for the nodes in the branch-and-bound tree. gurobi (and very likely also other commercial solvers) offer parameters to specify this separately: Method for changing the algorithm used at the root node. If you have ...

8

Not an expert on simplex, but here's my attempt on an answer: In general, the solution of the (previous) LP Relaxation will no longer be primal feasible when the primal LP is tightened (e.g. new cut in branch & bound). In the dual simplex, new primal cuts correspond to new dual variables, which are initialized as nonbasic, and thus the previous ...

8

In addition to @Richard's answer: The time for setting up the model, i.e. declaring variables and constraints, surely depends on the programming language you use. After the model is ready, solving does no longer depend on the language unless you use callbacks while doing the optimization. This is a more advanced technique where for example you provide the ...

8

Once it’s passed to the underlying C library, it does not matter which API it came from. However, there may be some overhead when you are retrieving the solution through the API (for the same reasons that you ready mentioned).

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