48
votes
Accepted
Optimization Problem Libraries
Quadratic assignment problem
Vehicle routing problem also at HEC
Traveling salesman
Graph partitioning
Quantified Boolean formulas
Constraint solvers
Shortest paths
Mixed integer programming
Train ...
- 2,705
37
votes
Accepted
In an integer program, how I can force a binary variable to equal 1 if some condition holds?
If $x$ is binary: Then the "if" condition really means either "$x = 0$" or "$x=1$".
To enforce "if $x=0$ then $y=1$": use
$$y \ge 1-x.$$
To enforce "if $x=1$ then $y=1$": use
$$y \ge x.$$
If you ...
- 13.1k
33
votes
Accepted
Why is open source operations research software so far behind open source statistics and machine learning software?
As someone who uses a lot of commercial/open-source OR software and incidentally tried coding my own solver, the underlying question is that of continued funding and support.
As mentioned in another ...
- 4,068
30
votes
Accepted
Why is it important to choose big-M carefully and what are the consequences of doing it badly?
The following answer presumes some familiarity with the limitations of floating-point arithmetic (rounding, truncation and representation errors), which I will lump together as “rounding error”. It is ...
- 37.9k
28
votes
Feeding known lower bounds to solvers
Interesting topic (the question was raised several times by my students as well).
My short answer is that adding the lower bound through a cut seems a good idea at first glance, but it creates a ...
- 1,656
27
votes
Dual bounds of integer programming problems
The notions of dual bound and primal bound originate a bit more generally, I think. We typically call an (iterative optimization) algorithm primal when it maintains a feasible solution in every ...
- 5,909
26
votes
Accepted
What are the tradeoffs between "exact" and Reinforcement Learning methods for solving optimization problems
As far as I understand it, all machine learning approaches used for solving (combinatorial) optimization problems, and in particular reinforcement learning, work as follows:
Use a greedy algorithm to ...
- 5,909
26
votes
Optimization Problem Libraries
Here is a start. Please add to this.
BOLIB: Bilevel Optimization LIBrary of Test Problems https://eprints.soton.ac.uk/436854/1/BOLIBver2.pdf
CBLIB: The Conic Benchmark Library: http://cblib.zib.de/ . ...
- 13.2k
25
votes
Accepted
What is the "big-M" method? And are there two of them?
People do use the term "big-$M$ method" to mean two different things. In both cases, the name refers to the use of a large constant, often denoted $M$.
The first use of the term refers to a method ...
- 13.1k
25
votes
What are good reference books for introduction to operations research?
For books with a focus on industrial applications, see this other question of this forum
As textbooks, I would recommend to have a look at:
General Intro to OR:
W. Winston. Operations Research: ...
21
votes
Reference for column generation applications
A nice comprehensive collection on applications can be found in the book by Desaulniers, Desrosiers and Solomon: Column Generation. It features articles about
Shortest Path Problems with Resource ...
- 2,737
21
votes
Accepted
How much can we expect to increase the speed of mixed integer programming in the next 10 years?
I work at a solver company (SAS Institute Inc.) and can probably weigh in on this a little bit.
The problem with saying anything about performance is that there is a lot of variability between ...
- 3,168
21
votes
Accepted
Using Neural Networks For Solving Optimization Problems
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, ...
- 3,168
20
votes
When to use indicator constraints versus big-M approaches in solving (mixed-)integer programs
Here is the advice in the IBM CPLEX documentation. So this pertains to CPLEX. I don't know to what extent it applies to other solvers.
First of all, indicator constraints may not be available in all ...
- 13.2k
20
votes
Accepted
"Best practices" for formulating MIPs
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 ...
- 5,909
20
votes
How to evaluate the performance of open source solver?
The pitfall is to only focus on performance, will ignoring scalability, maintenance, integration and reliability. Some of these are easier to measure than others:
Performance: if I give 2 constraint ...
- 4,675
20
votes
Accepted
How to compare two different formulations of a problem?
Even if the decision variables differ, you may still be able to prove that one of the formulations is stronger than the other by introducing an appropriate mapping.
Take for example a flow ...
- 6,063
19
votes
Stochastic programming MIP solvers
If you have access to MATLAB, I can recommend Marietta (I am a developer of this toolbox), with which you can solve general risk-averse optimal control problems (a ...
19
votes
Accepted
Modeling floor function exactly
It is not possible to model the floor function as a constraint without modeling strict inequality. To prove this, I will show how the floor function can be used to model strict inequalities.
Thanks ...
- 1,482
19
votes
Accepted
Algorithms vs LP or MIP
As mentioned earlier, all algorithms are constructed using loops and conditional statements, including the algorithms employed by LP/MIP solvers. There are plenty of problems where it is more ...
- 2,080
19
votes
Why is open source operations research software so far behind open source statistics and machine learning software?
Disclaimer: although I work for Gurobi, the views in this post are entirely my own.
I believe there are a few reasons for this trend:
First of all, the industries were "born" in different ...
- 3,459
18
votes
Accepted
How can I best handle symmetries in my MIP?
You can add symmetry elimination constraints, like saying that the you want solutions with lower index. For example, you can say something like if $x_{i+1}$ is used, then $x_i$ must also be used. Note ...
- 1,235
18
votes
How can I best handle symmetries in my MIP?
I think that the best survey of symmetry in IP was given by Francois Margot:
https://link.springer.com/chapter/10.1007/978-3-540-68279-0_17
- 1,024
18
votes
Accepted
Difference between lazy callbacks and using lazy constraints directly
Lazy constraints will only be checked when an MIP solution satisfying all other constraints, including integrality, is found.
If you provide all your lazy constraints in advance to CPLEX, for ...
- 671
18
votes
"Best practices" for formulating MIPs
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 ...
- 3,459
17
votes
Single reference for Mixed Integer Programming formulations to linearize, handle logical constraints and disjunctive constraints, do Big M, etc?
Here is a nice, succinct,and easy to understand reference for how to do all this and more. Answers to many future questions can be handled by referencing the appropriate section number in this ...
- 13.2k
17
votes
Accepted
When to use indicator constraints versus big-M approaches in solving (mixed-)integer programs
For Gurobi there seems to be a dual advantage of using general constraints (http://www.gurobi.com/documentation/8.1/refman/constraints.html#subsubsection:GeneralConstraints):
Benefit number one - ...
- 1,333
17
votes
Accepted
How does a warm start work in LP/MIP?
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 ...
- 3,168
17
votes
Accepted
Can presolve reductions change the value of the linear programming relaxation?
the answer is even worse than "no"; I recently used SCIP to compute an LP relaxation, and the outcome (the value of the dual bound) depended on the branching rule I ...
- 5,909
16
votes
Accepted
Branching rules in commercial MIP solvers
Tobias Achterberg's thesis includes a review of MIP solver technology from around 2009, including branching decisions and node selection.
- 2,316
Only top scored, non community-wiki answers of a minimum length are eligible