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

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

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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 Accepted answer 5 votes I assume you're applying the matrix version of the algorithm. When you happen to have only one$0for A and D the matrix is \begin{align*} \pmatrix{2&9&0&8&8\\2&1&6&0&... View answer 5 votes The coefficient2$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/...