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

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


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


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


9

Aggressive cut generation will slow the processing of the root node (and other nodes, if cuts are generated beyond the root), so it's more likely to slow finding a feasible solution than to speed it up. Setting MIP_Strategy_Subalgorithm to 1 tells CPLEX to use primal simplex on node subproblems. To emphasize finding feasible solutions, you want to set ...


9

You can model this as a maxmin problem by introducing an auxiliary variable $\theta$: \begin{align} \max&\quad\theta &\\ \text{s.t.}&\quad\theta \leq \sum_{c=1}^C x_{uc}d_{uc} & \forall u=1,\dots,U \end{align} For future reference, if in contrast you had a minmax objective instead of a maxmin objective, you could apply the same trick: \begin{...


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

MIP solvers such as CPLEX & Gurobi indicate a gap (in %) between the current best solution and the current best dual bound (which is a lower bound for a minimization problem). In general, the optimum value is not known until, well, the problem is solved. Different solvers may use slightly different definitions: CPLEX: $$ g = \frac{|Z_{\rm dual} - Z_{\rm ...


8

In Pelánek (2011)1, Sudoku difficulty evaluation was investigated across four existing metrics. These are based on incidences of various logic techniques (see constant folding). Results based on Spearman's correlation coefficient are given in Table 1. Evaluation of difficulty through dynamical systems has also been explored2. In this setting, one considers ...


8

Has anyone tested this approach on a real world business problem? If the question is, more generally, "for a practical optimization problem, can ML somehow accelerate the performance of a state-of-the-art MIP solver, given that we have already solved a large number of similar instances in the past?", then the answer is yes. In the reference below, ...


7

Modern CPUs are very complex and have at least two features that limit their scaling capability. The first one is a turbo feature that increases the clock speed when not all cores are utilized. The second one is that all cores share the same memory bus and the same L2 and L3 cache. If you solve the same problem in parallel (so start Python twice and let each ...


7

You need to distinguish between threads and (physical) cores. Is it possible that the cores you see in your machine are actually just hyperthreads, i.e. 2 cores resemble one physical core? Furthermore, using many cores is not always very helpful to solve a MIP. You may want to try something like Concurrent Optimization in Gurobi to exploit performance ...


7

For a test problem, check manually (outside GAMS) that the solution satisfies all constraints. If not, your GAMS model may be wrong. If all constraints are satisfied, try using a different solver and see if the same objective value is achieved. If the other solver gets a better result, your current runs may be stopping short of optimality. If the objective ...


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

While it does not deliberately transform the problem before exporting it, using the LP file format means that double precision coefficients are being converted to character strings (and, in the process, truncated and/or rounded). So there will frequently be a little loss of precision, and sometimes that "little" loss of precision can turn into big ...


6

In Python, with pulp and networkx : import pulp import networkx as nx G = nx.Graph() # define your graph here #... # define the problem prob = pulp.LpProblem("MinimumSetVertexCover", pulp.LpMinimize) # define the variables x = pulp.LpVariable.dicts("x", G.nodes(), cat=pulp.LpBinary) z = pulp.LpVariable.dicts("z", G.edges(), ...


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

Maximize an auxiliary variable $z$ subject to the constraints $z\le \sum_{c=1}^C d_{u,c}x_{u,c}\ \forall u$.


6

To be clear, you have a set $S$ of nodes of a graph $G=(V,A)$, with $S\subseteq V$, which must be visited. There is a special node $O$, which must be the starting point of a tour. A tour visiting the nodes in $S$ starting from $O$ (but not returning to $O$) at minimum length must be found? If that is the case, I think the easiest way is to compute an all-...


6

There are many useful references that can be found by googling. In the following you can find some of them: IBM ILOG CPLEX Optimization Studio OPL Language User’s Manual Introduction to Computational Optimization Models for Production Planning in a Supply Chain A Deep Dive into Strategic Network Design PS: About the first mentioned reference, it is about (...


6

If you export the model, then by default, Cplex will export your original, unaltered model. When you solve a model, Cplex will, by default, first invoke a presolve,during which it will attempt to simplify and tighten your model, e.g. by removing redundant constraints, solving for logical implications, etc. As per this SO post, you can then also export the ...


6

Integer programming models solved by CPLEX (or most other solvers) require linear or, in certain very limited cases, quadratic constraints. Your constraint 9 involves dividing a parameter (h) by an integer variable (man), which results in a nonlinear expression. Multiplying both sides by man will not help, since that produces an equation with products of ...


5

Collecting things in a parameter is actually very simple. set run /.../; parameter objresult(run,*); loop(run, solve m .... objresult(run,"obj") = m.objval; objresult(run,"bestbound") = m.objest; objresult(run,"absgap") = abs(m.objval-m.objest); );


5

By default, Gams/Cplex will try to calculate duals by fixing the integer variables and then resolving as an LP. This is the "final solve". Usually the objectives are the same. In rare cases the final lp can be infeasible or the objective can be different because of an artifact in Cplex (mind-numbing detail: it can return mip solutions obeying the ...


5

Gaps are typically tied to specific models and solution methods. The gap reflects the difference between the best known bound and the objective value of the best solution produced by a particular algorithm. How that is computed depends in part on whether you are minimizing and maximizing, in part on whether you want the gap as a fraction of the best solution ...


5

The augmented $\varepsilon$-constraint method is designed to generate all non-dominated outcome vectors to a bi-objective (or multi objective) optimization problem, whereas a lexicographic optimization approach is designed to generate one particular non-dominated outcome vector to bi-objective (or multiobjective) problem. So it all depends on what you want ...


5

According to the docs, IloNumArrays constructor signature is public IloNumArray(const IloEnv env, IloInt n, IloNum f0, IloNum f1, ...) which creates an array of n floating point objects for use in a model. Note that the constructor is a C-Style variadic function due to the ... parameter. Thus, you can assign your values while calling the constructor, i.e. ...


5

I don't know why the version number jumped. I will say that I found the creeping pace documented in Mark's comment odd from a marketing perspective -- it might lead a consumer to think IBM was just patching the occasional bug while competitors (with faster moving version numbers) were making technological "leaps". Maybe someone at IBM had the same ...


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