Marcus Ritt
  • Member for 2 years, 8 months
  • Last seen more than a month ago
  • Porto Alegre, Brazil
Optimization Problem Libraries
Accepted answer
47 votes

Quadratic assignment problem Vehicle routing problem also at HEC Traveling salesman Graph partitioning Quantified Boolean formulas Constraint solvers Shortest paths Mixed integer programming Train ...

View answer
Simplex-Implementations in professional Solvers
18 votes

There is a series of three lectures of Robert Bixby (the Bi in Gurobi) on Solving Linear Programs: The Dual Simplex Algorithm. Have a look at the third part Implementing the algorithm where he talks ...

View answer
Prove that these linear programming problems are bounded by $O(k^{1/2})$
Accepted answer
13 votes

Your linear program is similar to a mathematical formulation of a bounded Knapsack problem and has a similar linear relaxation. First note that $x_1$ is only restricted by $x_1\geq -1$ and thus $x_1=-...

View answer
Small Traveling Salesman Problem instance
Accepted answer
13 votes

There is a paper of Ahammed and Moscato on finding hard instances for Concorde using Lindenmeyer systems. They were able to find small instances with about 1500 cities that took (in 2011) more than 4 ...

View answer
Why is the programming code of many algorithms not public in the OR community?
11 votes

I think the five answers (up to now) give a representative sample of the different reasons for not publishing code in the OR community. That answers your question. To provoke a bit, I would say most ...

View answer
Feeding known lower bounds to solvers
11 votes

Branch-and-bound solvers often use node lower bounds to select the next node to process, e.g. in a best-first search. An external lower bound can lead to a different search order, and thus you may ...

View answer
The curse of the benchmark instances
Accepted answer
11 votes

To complement Michael's answer, which I think made the main points already: First, an obvious strategy is to separate the data set used for testing and tuning, from the data set that are used in ...

View answer
Relationship between the Assignment Problem and the Stable Marriage Problem
10 votes

You don't get a minimum-weight (perfect) matching by giving preference to smaller weights in the stable marriage problem. Consider $\mathcal{I}=\{a,b\}$ and $\mathcal{J}=\{1,2\}$ and weights $w_{a1}=2$...

View answer
McCormick envelopes and nonlinear constraints
10 votes

For real $x\in[l,u]$ and binary $b\in\{0,1\}$ the McCormick envelope gives you bounds on $w=xy$ $$\begin{align} lb & \leq w \leq ub,\\ ub+x-u& \leq w\leq x+lb-l. \end{align}$$ By case ...

View answer
Are there any efficient algorithms to solve the longest path problem in networks with cycles?
9 votes

As observed by Kevin Dalmeijer, you cannot expect an efficient method unless $\sf{P=NP}$. Since you're asking explicitly for dynamic programming: define $C(s,t,V)$ as the longest path from $s$ to $t$ ...

View answer
Many-to-many Breadth First Search
8 votes

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

View answer
Simplest way to eliminate redundant constraints due to a new cut
Accepted answer
8 votes

As a partial answer, Telgen (1977) has shown that eliminating all redundant inequalities is LP-equivalent, i.e. in general not easier than solving linear programs. Clearly, this does not exclude ...

View answer
Does the "prize-collecting shortest path problem" exist?
Accepted answer
7 votes

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

View answer
Relationship between Benders’ decomposition and Dantzig-Wolfe decomposition
7 votes

"Benders’ decomposition is Dantzig-Wolfe decomposition applied to the dual" is the first sentence of Section 10.3 in Dantzig & Thapa's Linear programming 2: theory and extensions, which then ...

View answer
Classics in Operations Research from around WW II?
7 votes

Not a written document, but maybe interesting: an episode of the INFORMS podcast, Looking Back at the Origins of O.R. on "the first time the term Operations Research was employed, and some of the ...

View answer
Are there reusable formulations/heuristics shared with the community?
6 votes

For biased random-key genetic algorithms (BRKGA) there is a paper of Toso & Resende and accompanying software. In a BRKGA the solution is represented as vector $v\in\mathbb{R}^n$ of real "keys" ...

View answer
The effect of choosing big M properly
6 votes

The practical study Analysis of Strength and Weaknesses of a MILP Model for Revising Railway Traffic Timetables includes an analysis of the influence of big M constraints. The conclusion is mixed, ...

View answer
Assignment problem using Hungarian method
Accepted answer
5 votes

I assume you're applying the matrix version of the algorithm. When you happen to have only one $0$ for A and D the matrix is \begin{align*} \pmatrix{2&9&0&8&8\\2&1&6&0&...

View answer
Units in the EOQ problem
5 votes

The coefficient $2$ in the first equation has unit $1/\text{order}$, so the second approach is the right one, and $Q^*$ has units $\text{item}/\text{order}$. The unit comes from the holding cost $hQ/...

View answer
Declare numerical-sequence set in AMPL .dat file
Accepted answer
4 votes

The .. operator cannot be used in the data section (i.e. it won't be expanded, see the AMPL FAQ). What you can do is to declare the limits in the model, e.g. param n; set things := 1..n; and define ...

View answer
Are metaheuristics ever practical for continuous optimization?
2 votes

The answer is: of course. First, nonconvex, global optimization, is a huge and challenging area, and arguably one of the most interesting. If you limit the scope to finding a nearby local minimum in ...

View answer