# 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

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

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, ...

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

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

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

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{...

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 ...

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

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

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 ... 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. 6 While other answers have focused on the question whether "P vs. NP" can be considered to be in OR, I will instead look at the parts about this topic that I think are most relevant to study in the context of OR. The basics Before you can even properly understand what "$\mathsf{P}=\mathsf{NP}$" or "$\mathsf{P}\neq \mathsf{NP}$" means, you need to know what ... 6 Choosing is loosing. We should be collecting raw benchmarks results at a grand scale, independent of how we evaluate them. And we should have a free, open, objective website hosting all that data, from different researchers and different vendors. I'd love to help build out an open datawarehouse of benchmarks, using our benchmark toolkit on top of ... 6 A good thing for you to invoke in your case is the Central Limit Theorem. It states, roughly speaking, that you can assume a normal distribution (a special case of the Gaussian Function) provided your sample size is "large enough." Usually "large enough" is taken to mean$n\ge30$. You can use a Two Sample$t$-test for this. You want to show that Algorithm$...

6

There are many algorithms suggested for converting the "external" representation of a polyhedron (i.e., the set of solutions to a finite set of linear inequalities) into an "internal" one (i.e., a finite set of generators, extreme points and extreme rays). At it's core there often is some sort of finding all (discrete) solutions to a set of linear ...

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