Skip to main content

# Tag Info

## Hot answers tagged algorithms

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 ...
• 13.1k
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-...
• 13.5k
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,929
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. ...
• 39.9k
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,657
12 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,095
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,696
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 ...
• 9,103
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,643
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,502
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} \...
• 13.1k
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-...
• 13.1k
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. ...
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 ...
• 33.1k
9 votes

• 5,442
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, ...
• 39.9k
7 votes

### How to implement a "generic" solver for scheduling problems?

Before you even start worrying about algorithms, you need to figure out the solver's architecture. You can do so by posing and answering questions such as the ones I ask below. The answers will be a ...
• 12.2k

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