Skip to main content
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, ...) ...
21 votes
Accepted

Branch and Bound Implementation

Read the ph.d. thesis of Tobias Achterberg where he describes the solver Scip. Have fun.
ErlingMOSEK's user avatar
  • 3,206
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 ...
mrBen's user avatar
  • 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 ...
Sune's user avatar
  • 6,657
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 ...
Nikos Kazazakis's user avatar
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 ...
aykutbulut's user avatar
9 votes

Paper suggestions on local search algorithms

Below are some papers from Hexaly team members that detail local search approaches for diverse combinatorial optimization problems, with some focus on low-level implementation details: T. Benoist, B. ...
Hexaly's user avatar
  • 2,986
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} =...
RobPratt's user avatar
  • 33.1k
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: ...
RobPratt's user avatar
  • 33.1k
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 ...
prubin's user avatar
  • 39.8k
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-...
Hexaly's user avatar
  • 2,986
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....
Janis Neufeld's user avatar
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 ...
Ruslan Sadykov's user avatar
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 ...
prubin's user avatar
  • 39.8k
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 ...
Kuifje's user avatar
  • 13.6k
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 ...
Alex Fleischer's user avatar
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).
prubin's user avatar
  • 39.8k
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.
Robert Schwarz's user avatar
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&...
Sune's user avatar
  • 6,657
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 ...
Nikos Kazazakis's user avatar
3 votes
Accepted

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 ...
prubin's user avatar
  • 39.8k
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. ...
TheSimpliFire's user avatar
  • 5,442
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 ...
prubin's user avatar
  • 39.8k
3 votes

Branch and Bound Implementation

This Github repository has the Java implementation of the Branch and Bound for solving VRP.
Parth Ghadge's user avatar
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.
kur ag's user avatar
  • 825
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/. ...
steven kelk's user avatar
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 ...
Nikos Kazazakis's user avatar
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 ...
Geoffrey De Smet's user avatar
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 ...
ytsao's user avatar
  • 411

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