23 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 ...
user avatar
16 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 ...
user avatar
  • 511
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-...
user avatar
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 ...
user avatar
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. ...
user avatar
  • 29.6k
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 ...
user avatar
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 ...
user avatar
11 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 ...
user avatar
  • 5,357
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 ...
user avatar
10 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) ...
user avatar
  • 1,045
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-...
user avatar
  • 1,581
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 ...
user avatar
  • 3,283
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 ...
user avatar
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} \...
user avatar
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-...
user avatar
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. ...
user avatar
9 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 ...
user avatar
  • 5,805
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 ...
user avatar
  • 22.2k
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,...
user avatar
  • 29.6k
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 ...
user avatar
  • 2,665
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 ...
user avatar
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 (...
user avatar
  • 22.2k
8 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 ...
user avatar
  • 10.2k
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.
user avatar
  • 22.2k
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 ...
user avatar
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 ...
user avatar
  • 22.2k
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 ...
user avatar
  • 2,665
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. ...
user avatar
  • 5,185
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, ...
user avatar
  • 29.6k

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