# Tag Info

21

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 are asking whether P-vs-NP is contained within OR (although the body of your question does not). I would not say that P-vs-NP is contained within OR; rather, it ...

16

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-academic) O.R. people are not necessarily fixated on it. In some circles, NP Hard is essentially considered to mean unsolvable. However, there are several ...

15

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, ...) LocalSolver: explanation + source code (same with time windows) OR-tools: explanation + source code Jsprit: source code - company website (capacitated, time windows, ...

15

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 algorithms for specific problems (like knapsack or max flow) and also generic LP and CP solvers.

14

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 one is performance profiles. They were introduced in this article: Elizabeth D. Dolan and Jorge J. Moré, Benchmarking optimization software with performance ...

12

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. In one approach, you create continuous variables for each vehicle representing the time the vehicle begins charging, the time it ends charging, and the time it ...

11

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 and heuristics are not needed and actually slow-down the solver (of course this can happen, as the default setting is not perfect in all cases).

11

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 is a quintessential example of a question belonging to the TCS (theoretical computer science) field. As others have pointed out, a solution of the P vs NP ...

11

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 quadratick knapsack problems (quadknap) among others. I don't know if it qualifies as a "common OR problem" but for linear vector optimization (and therefore also ...

11

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 more genetic search inspired aspects.

10

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) uploaded the following paper in arXiV. The paper compares the different Linear Solvers (and potential parallelization schemes) performance within IPOPT. They ...

9

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 hard problem, not just NP-hard (since it is a generalisation of the NP-hard weighted independent set problem), but also NP-hard to approximate within a constant ...

9

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} \left(\sum_{i\in P_m} c_{ij} + f_j\right),$$ i.e., the fixed plus transportation cost if we choose the best facility for the set $P_m$ of customers. At each ...

9

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-44, 2000) that discusses this issue in detail.

9

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 is to maximize $\sum_j y_j$ subject to \begin{align} \sum_{j \in s_i} y_j &\le 1 &&\text{for $i\in \{1,\dots,m\}$} \\ y_j &\ge 0 &&\text{...

9

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, z_n\rbrace$ to be a type 1 special ordered set (SOS1). Assuming the solver supports SOS1 constraints, you'll end up with a solution in which at least $n-1$ of ...

8

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 connected component with $c$ nodes this saves you $c-1$ BFS calls. Also, the resulting graph is a DAG, so processing it in reverse topological order the reachable ...

8

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 visits: remove a number of sequential visits from a chain and insert it somewhere else in a chain, sometimes reversed swap 2 subchains ruin&recreate

8

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 scheduling problems. (E.g. vehicle routing problem variants). Planning and Scheduling, specifically in the real application, will need to survey from some ...

8

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 function of the goals of the project, the help & know-how of the people who employ you and, crucially, what you can realistically do in 6 months. Keep in ...

8

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 (rather than the usual requirement that all integer variables are integer-valued). You would also need to disable any presolve/cut routines that assume ...

7

See http://oeis.org/A000088, which gives a different number (34) for n = 5.

7

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 a promising set of FSCs to add apriori and (b) add the remaining forbidden constraints via lazy callbacks, where you add the "most violated" constraint at each ...

7

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 one commercial solver (SAS) looks for such structure after presolve and suggests using the decomposition algorithm in that case. The decomposition algorithm ...

7

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 prizes $p_v\geq 0$, $v\in V$, construct a directed graph $G'=(V,A)$, where $A$ is obtained by replacing each edge $e=\{u,v\}\in E$ of length $d_e$ by two arcs $(... 7 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. Two widely used statistical tests are shown to have high probability of type I error in certain situations and should never be used: a test for the difference ...

7

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. Specifically, graph cuts were used for inferring maximum probable states in Markov Random Fields (MRF), with input costs coming from hand-tuned features. ...

7

The following isn't meant to be exhaustive. It usually depends on the structure of the matrix because that impacts the way you choose it. In general there are sparse variants for many of the general matrix decompositions you see LU, QR, SVD and what not. There are also sparse Kyrlov methods such as the shifted Block Lanczos method. If it isn't symmetric then ...

6

As others already said, the PCSPP described resorts to a simple SPP with potentially negative costs. It would still be solvable in poly time if no cycles of negative weight are present. Otherwise, you could impose elementary constraints and solve it as an elementary shortest path problem which, however, is NP-hard, and for which several algorithms exist ...

6

I think there is some work on this, for the context of vehicle routing problem solvers using branch and price. The subproblem (or pricing) becomes an price collecting path problem. A good starting point for references for that might be Chapter 3.5 of "Vehicle Routing: Problems, Methods, and Applications" by Paolo Toth and Danielle Vigo.

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