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
Does the problem of P vs NP come under the category of Operational Research?
The short answer is yes, operations researchers care a lot about P vs NP. We deal in algorithms, and the complexity of those algorithms matters a lot to us.
The title of your question suggests you ...
- 12.9k
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
16
votes
Does the problem of P vs NP come under the category of Operational Research?
P vs. NP may come "under" the category of Operational Research (O.R.). But unlike theoretical computer science and algorithm analysis, in which P vs. NP may be a be all and end all, practical (non-...
- 12.2k
14
votes
Statistical tests for benchmark comparison
I know that you explicitly ask for a statistical test, but maybe this is because you don't know about alternatives that are rather established in the community. When comparing algorithms, my number ...
- 5,869
12
votes
Accepted
Finding minimum time for vehicle to reach to its destination
You can solve this with a mixed integer linear program. It has some similarities to job shop scheduling (with parallel machines) and multiprocessor scheduling, although it is not identical to either. ...
- 35.5k
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 ...
- 5,954
11
votes
Does the problem of P vs NP come under the category of Operational Research?
This goes against the grain of the other answers here, but I do not believe that the P vs NP problem would naturally be categorized as a question in operations research. Instead, I would argue that it ...
- 211
11
votes
Accepted
Neigbourhoods in Large Neighbourhood Search (LNS) algorithms
This paper by Pisinger and Ropke is particularly useful when working on (A)LNS, and provides great guidance and an overview of operators/neighborhoods. I would suggest this paper by Vidal et al. for ...
- 1,859
11
votes
Accepted
Performance of a branch and bound algorithm VS branch-cut-heuristics
If your outcome is confirmed by 10 runs with different random seeds (or 10 permutations of the input) on different instances of your problem, then you are facing a (rare) case where the default cuts ...
- 1,646
11
votes
Accepted
IPOPT with HSL vs MUMPS
This question happened to appear only a couple days after Byron Tasseff, Carleton Coffrin, Andreas Wächter, and Carl Laird (the last two are the original authors of IPOPT together with Larry Biegler) ...
- 1,055
10
votes
How to implement a "generic" solver for scheduling problems?
As you mentioned about "scheduling/production planning problems", I refer it to manufacturing planning and detailed schedule. Also, I know that there are specific methods to solve other planning and ...
- 7,271
10
votes
Optimization Solution Framework
Here are my notes about the various discrete optimization methods.
Combinatorial branch-and-bound
Manual implementation
Provides a bound
Works well when the bound is good
Rarely used nowadays
Mixed-...
- 2,231
10
votes
Julia JuMP successive optimization
Your question has a two-part answer: how JuMP handles successive solves, and how the solvers handle successive solves.
How JuMP handles successive solves
Recall that JuMP is a modeling layer, not an ...
- 3,988
9
votes
Accepted
Finding an optimal set without forbidden subsets
Your problem is equivalent to finding a maximum weighted independent set in a hypergraph, where each item is a vertex and every forbidden set is an hyperedge over the elements in the set.
This is a ...
- 1,472
9
votes
Algorithmic gap for Hochbaum's (greedy) algorithm for (metric) uncapacitated facility location
I'm looking at the algorithm as it's described in Hochbaum (1982), which works like this: Suppose we have enumerated all $2^n-1$ subsets of the customers. Subset $P_m$ has cost
$$C_m = \min_{j\in J} \...
- 12.9k
9
votes
Statistical tests for benchmark comparison
I think there are many different factors to consider. There's a very good paper by Coffin and Saltzman (Statistical Analysis of Computational Tests of Algorithms
and Heuristics, INFORMS JOC 12(1): 24-...
- 12.9k
9
votes
Was there something specific that caused graph cuts to lose popularity in the last 5 years?
Graph cuts were mainly used in computer vision, where since 2011 deep neural networks have taken over the field. The decline from 2015 on is attributable to a time delay in picking up neural networks.
...
- 91
9
votes
Specific algorithms to compute the LP-relaxation of the Set-Cover problem
Not sure about solving the LP relaxation, but you can get a closed-form lower bound from LP duality, without calling any solver. Let $y_j$ be the dual variable for constraint $j\in U$. The dual LP ...
- 27.1k
9
votes
Mixed-Integer Linear Programming With Free Variables
Here's another single-solve solution. Replace each original variable $x_n$ with a sum of two variables, $x_n=y_n + z_n$, where $y_n$ is integer-valued and $z_n\in [0,1]$. Now define $\lbrace z_1,\dots,...
- 35.5k
9
votes
Accepted
Optimization Solution Framework
You have to keep in mind that MIPs can return the optimal solution, provided enough computation time is given. So if time is not an issue, I would always go for a MIP. Also, MIPs are more flexible in ...
- 11.8k
8
votes
Many-to-many Breadth First Search
Since your graph is directed you can first compute the strongly connected components in linear time $O(n+m)$, contract the components, and then run BFS on the contracted graph. For each strongly ...
- 2,705
8
votes
Neigbourhoods in Large Neighbourhood Search (LNS) algorithms
These common neighborhoods for TSP/VRP might be useful:
2-opt, 3-opt, ..., k-opt
change 1 visit: remove 1 visit from a chain and insert it somewhere else in a chain
swap 2 visits
change a subchain of ...
- 4,645
8
votes
Accepted
Mixed-Integer Linear Programming With Free Variables
An alternative approach that requires only one solve and no modification of the model is to modify branch and bound to prune by integrality when at most one integer variable takes a fractional value (...
- 27.1k
7
votes
Is there any way to generate all the possible undirected graphs with unlabeled nodes?
See http://oeis.org/A000088, which gives a different number (34) for n = 5.
- 27.1k
7
votes
partitioning hub assignment models
Formulating as one big problem requires more memory, some way to recognize that the problem decomposes into disjoint subproblems, and some way to then solve the subproblems independently. At least ...
- 27.1k
7
votes
Finding an optimal set without forbidden subsets
Since this problem has exponentially many constraints, I suspect that most forbidden subset constraints (FSCs) will not be binding at optimality. Therefore, something which you could try is: (a) pick ...
- 1,112
7
votes
Accepted
Does the "prize-collecting shortest path problem" exist?
You can make the graph directed, push the prizes into the arcs and solve a shortest path problem with negative lengths (i.e. for an undirected graph $G=(V,E)$ with distances $d_e\geq 0$, $e\in E$ and ...
- 2,705
7
votes
Statistical tests for benchmark comparison
Options for you: McNemarNP, $t$ test (with variants)P, WilcoxonNP, sign testNP, FriedmanNP
Dietterich (1998)
Five statistical tests are compared primarily on the type I error produced. Emphasis mine.
...
- 5,271
7
votes
How to implement a "generic" solver for scheduling problems?
The "generic" aspect of the solver might just mean that management has, um, inflated expectations. That said, and focusing on the use of metaheuristics, I'll throw out a few ideas.
Where possible, ...
- 35.5k
Only top scored, non community-wiki answers of a minimum length are eligible