27
votes
Accepted
List of Implementations for common OR problems
Let's make an inventory of example code for each common OR problem?
Vehicle Routing Problem
OptaPlanner: explanation + videos - source code (capacitated, time windows, multiple depots, ...)
...
20
votes
Accepted
Branch and Bound Implementation
Read the ph.d. thesis of Tobias Achterberg where he describes the solver Scip.
Have fun.
- 2,946
17
votes
List of Implementations for common OR problems
A good place to start is COIN-OR, which aims to "create for mathematical software what the open literature is for mathematical theory".
You can also take a look at Google's OR-Tools. It contains many ...
- 521
12
votes
List of Implementations for common OR problems
I would, for everything knapsack-like, always go to David Pisingers homepage. Here you can find very efficient codes for knapsack problems (COMBO), multiple-choice knapsack problems (Mcknap), and ...
- 6,222
10
votes
Branch and Bound Implementation
What makes any branch-and-bound implementation tick is the heuristics that accompany the algorithm, not branch-and-bound itself. I start by explaining branch-and-bound to frame why we need the ...
- 11.9k
10
votes
Branch and Bound Implementation
Check COIN-OR ALPS code (in C++) and Yan Xu's dissertation for explanation. He explains a scalable parallel branch and bound algorithm and presents experiments solving Knapsack instances with up to ...
- 101
8
votes
Paper suggestions on local search algorithms
Below are some papers from LocalSolver team members that detail local search approaches for diverse combinatorial optimization problems, with some focus on low-level implementation details:
T. Benoist,...
- 2,910
8
votes
Accepted
Column generation when intractable variables appear in the objective function
Suppose $K$ is the set of columns, where the $k$th column $x^k \in \{0,1\}^n$ satisfies $A(x^k) \le a$. Now express $x$ as a convex combination of the columns $x^k$. Explicitly, substitute $x_{i,j} =...
- 29.8k
6
votes
Accepted
Problem with big-M in CPLEX OPL
It is numerically safer to use a (small) data-dependent value for $M$. For your case, rewrite as:
...
- 29.8k
6
votes
Accepted
Check which constraints are violated (Concert - Cplex Studio 12.10 - C++)
You don't actually need to use the MIP start approach. Fix the upper and lower bounds for all your discrete variables to their values in the heuristic solution, then try to solve the model. Assuming ...
- 37.5k
6
votes
implementation of heuristics using C++ to solve operations research problems
The best paper we ever read about the implementation of heuristics for the TSP is "An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic" by Keld Helsgaun. This 70-...
- 2,910
5
votes
List of Implementations for common OR problems
A nice framework for heuristic optimization is provided by HeuristicLab. Several classical problems, such as Job Shop Scheduling, Knapsack, Bin Packing or
TSP are also integrated (https://dev....
5
votes
List of Implementations for common OR problems
I am sorry to advertise our own VRP solver, but may be it is what you are looking for:
https://vrpsolver.math.u-bordeaux.fr/
For knapsack, Pisinger's code is the best (mentioned above), however ...
- 1,394
5
votes
Accepted
Defining and comparing utilization rates for delivery service
One possibility is to look at idle time (time a driver spends waiting for the next order). If the drivers are on your payroll (as opposed to working on commission, i.e., doing "gig" work), idle time ...
- 37.5k
4
votes
Design choices on how to implement several algorithms for the same problem
It depends on how you choose to solve your master and slave problems (for your Lagrangian and Dantzig-Wolfe decompositions). Theoretically, you can solve everything with linear programs. In this case ...
- 12.8k
4
votes
Problem with big-M in CPLEX OPL
with CPLEX 12.10 your model gives a solution with objective 3
If you prefer not to use big M, you could use logical constraints and rewrite
...
- 3,980
4
votes
Accepted
implementation of heuristics using C++ to solve operations research problems
Regarding the last question (how to link C++ and CPLEX), CPLEX has a C++ API that is thoroughly documented in the user manual. They also provide quite a few C++ examples (source code).
- 37.5k
4
votes
Paper suggestions on local search algorithms
I'm not an expert in the field, but the paper An effective implementation of the Lin-Kernighan traveling salesman heuristic by Keld Helsgaun was mentioned in another question before.
- 2,306
4
votes
Paper suggestions on local search algorithms
This answer focuses on the "papers that go into the details of implementation on a given optimization problem" part of the question.
In "Variable neighborhood search for the $p$-median&...
- 6,222
4
votes
Accepted
Trouble implementing a line-search algorithm
Your bisection code is returning a tuple of [a,b] but in your main function you are only retrieving a, which should be causing ...
- 11.9k
3
votes
Tips for implementing Benders Decomposition in C++?
Recent versions of CPLEX (12.7 or later) have built in support for Benders. You can let CPLEX decide what to put in the master problem and what goes in the subproblems, or you can use annotations to ...
- 37.5k
3
votes
Paper suggestions on local search algorithms
Blot et al. (2018)1 did an extensive literature review on multi-objective LS algorithms. You may wish to take a look at Ishibuchi and Murata (2004)2 which focuses on issues in evolutionary algorithms.
...
- 5,341
3
votes
Accepted
Generating a different optimal solution from CPLEX for each run
CPLEX treats the seed as a parameter. The parameter name varies by API; for Python it seems to be "parameters.randomseed". The docs somewhat unhelpfully state that "[t]he default value ...
- 37.5k
3
votes
Branch and Bound Implementation
This Github repository has the Java implementation of the Branch and Bound for solving VRP.
- 31
3
votes
List of Implementations for common OR problems
For assembly line balancing problem, test problems, codes for several versions of problem and useful resources can be found at https://assembly-line-balancing.de.
- 746
2
votes
List of Implementations for common OR problems
I just want to mention the solvers that have been produced in recent years in the remit of the PACE (Parameterized Algorithms and Computational Experiments) challenge, see https://pacechallenge.org/.
...
- 25
2
votes
Recommended python solver for an online optimization problem
Assuming you are writing the norms as explicit mathematical expressions (e.g. $|x_1|+|x_2|...$) you can just use our own Octeract Engine. As of next Monday (15 Feb 2021) it's free for everyone, and it ...
- 11.9k
2
votes
Paper suggestions on local search algorithms
For what it's worth, here you can download our paper on Multithreaded Incremental Solving for Local Search (not to be confused with multi-walk solving (AKA multi-bet solving), multi-tentant solving or ...
- 4,685
1
vote
Tips for implementing Benders Decomposition in C++?
For example, If your problem is two-stages stochastic programming, then you can separate your problem into master problem and sub-problem by your hands.
Then you can use CPLEX to model both stages in ...
- 116
Only top scored, non community-wiki answers of a minimum length are eligible