Tag Info

21

Generating routes heuristically, or heuristic pricing, is very common in the vehicle routing literature. Even when the pricing problem can be solved exactly, heuristic pricing is often tried first. Only when no more routes can be generated by heuristics, the exact pricing algorithm is run. When heuristic pricing is used in this way, the overall method is ...

17

The following is largely opinion/conjecture on my part. Many (though not all) heuristics involve neighborhood search. For that type of heuristic to be effective, you need "neighborhood" to be defined in a way that is both computationally convenient (moving from one solution to a "neighboring" solution is straightforward and does not ...

13

I doubt there is a complete listing of every possible approach to TSPs. You can find a significant amount of information on Bill Cook's site. Bill Cook wrote what I believe many consider the definitive book about TSPs ("In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation", Princeton University Press, 2012) and is one of ...

11

You are right. If you solve the pricing heuristically, you do not have a valid lower bound. One approach to obtain a lower bound would be to solve a relaxation of the pricing problem exactly. Usually, the faster a relaxation can be solved, the worse in the resulting bound. Another (but still similar) approach is to calculate a lower bound on the pricing ...

11

Your problem actually comes down to a constrained linear regression problem where $z$ is your dependent variable, the $x_j$ for $j=1,\dots,n$ are your independent variables and $s$ is your vector with regression coefficients. Without any constraints, the unique solution optimizing the MSE is the least squares estimator: $$\hat{s}=(X'X)^{-1}X'z, \quad \text{... 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. 11 Let binary decision variable x_{i,g} indicate whether node i\in\{1,\dots,N\} appears in group g\in\{1,\dots,N\}, and let binary decision variable y_{i,j,g} indicate whether edge (i,j) appears in group g. You want to maximize$$\sum_{i<j}\sum_g w_{i,j} y_{i,j,g}subject to \begin{align} \sum_g x_{i,g} &= 1 &&\text{for all i} \... 10 This is a question, for which google "primal heuristics integer program solver" may give a better answer than I can give myself, but: One of the "definitive" references is this dissertation by Timo Berthold. 10 CPLEX has a parameter (RootAlgorithm) that lets you select the method for solving an LP (or for solving the root node relaxation of an ILP). The default setting is to let CPLEX choose, which usually (but not always) results in it using dual simplex. One of the choices is "network simplex", which you might try for a graph problem. I don't know whether CPLEX ... 10 You can solve the LP relaxation and round the resulting solution x^*, being careful to preserve the equality constraint. Then take t=\max_c |\sum_n B_{n,c} x_n - d_c|. There are lots of choices for rounding methods, but two natural choices are: Let x = \lfloor x^* \rfloor and R=M-\sum_n x_n. In descending order of x^*_n, let x_n = x_n+1 for ... 10 My experience in this may be a bit dated (it comes from a previous millennium), but back then I recall (vaguely) using a form of response surface methodology to optimize parameters in a simulation model. The idea was to run the model with a range of parameter values and harvest observations, fit a nonlinear model statistically (with the performance measure ... 9 The bounty convinced me to compete with Rolf's excellent answer, which is exactly how I would approach the problem myself. Next to CPLEX and Gurobi, it also worth noting that MATLAB and Octave provide the function fmincon, which can also be used to solve your problem directly, and SPSS provides Constrained Nonlinear Regression (which also allows for ... 9 There are a variety of heuristics and metaheuristics (not necessarily using LP) that you could employ. If we set S_c = \{n : B_{n,c}=1\}, we can rewrite the problem as\begin{align*} \min_{t} & \quad t\\ \text{s.t.} & \quad\left|\sum_{n\in S_{c}}x_{n}-d_{c}\right|\le t,\quad\forall c\in\{1,2,\cdots,C\}\\ & \quad\sum_{n=1}^{N}x_{n}=M. \end{...

9

Often such problems have side constraints, and this patent covers that more general case, using Dantzig-Wolfe decomposition with the network subproblem (MST, TSP, etc.) expressed compactly (not algebraically) and solved with a specialized solver. This functionality is implemented in SAS but currently undocumented. Please contact me if you are interested in ...

9

You can solve your model via the NEOS server which provides Gurobi, Cplex, and other solvers for free if it is the matter of not having a solver. I am not familiar with PuLP but I know it is easy to implement the solvers in NEOS if you model the problem in Pyomo. May it helps you to find PuLP syntax for it, I provide lines of code written for Pyomo using ...

9

This is a minimum cost flow problem in the bipartite graph $G=(V,A)$ with $V=N_U \cup N_B$. Add a source node and link it to each vertex $v\in N_U$. On each of these arcs, constrain the flow to be in the range $[a_{min},a_{max}]$. Note that if $a_{min} > |N_B|$ the problem is infeasible. Likewise with a sink node, that you link to each vertex $v \in N_B$, ...

8

To my knowledge, there is yet no known constant worst-case error bound $\eta$ for farthest insertion nor a proof that no constant bound exists. The results you mention here require symmetric TSP instances with costs that satisfy the triangle inequality, if I am not mistaken. Nearest and cheapest insertion benefit from the fact that it can be shown that ...

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

The general rule is to use dynamic programming (Labeling Algorithm) to solve the VRP pricing problem. It has some advantage over solving the mathematical model. DP can yield many columns in each iteration versus the one column that yielded by solving the model. As @Kevin Dalmeijer mentioned you need to be able to solve the pricing problem exactly even if you ...

8

Even if you solve the pricing heuristically, you can still obtain a valid lower bound in certain cases. However, it depends on your pricing heuristic whether this is possible. You have found the optimal solution to the linear relaxation of the master problem if there are no more columns with negative reduced costs. Suppose you have a heuristic that always ...

8

Many solvers have an option to control the "emphasis" (feasibility versus optimality) of the tree search. If you suspect that your initial solution is already optimal, set this option to emphasize optimality, which will make cut generation more aggressive and do some other similar things. Another approach is to explicitly apply reduced-cost fixing to fix ...

8

There are some proofs of the contrary: whatever the starting point, your local search can be stuck in solutions far away from the optimum. Here "local" means that each iteration must be done in polynomial time. Check the seminal paper "On the Complexity of Local Search for the Traveling Salesman Problem" by Papadimitriou and Steiglitz on ...

8

Some additional sources to help you answer your question: Cook, W. "In pursuit of the traveling salesman: mathematics at the limits of computation. 2012." Gutin, Gregory, and Abraham P. Punnen, eds. The traveling salesman problem and its variations. Vol. 12. Springer Science & Business Media, 2006.

7

I am aware of two ways of combining a (meta-)heuristic with a solver (like cplex). 1) Warm start: use a heuristic to quickly find a good solution and give it to the solver as a starting solution. This can help pruning the branch and bound tree considerably. (e.g. "Designing sustainable energy regions using genetic algorithms and location-allocation ...

7

AFAIK, it depends on the optimization problem under study. As @Kuifje said, black boxes are used when the problem is too complex. One of the ways to apply simulation-optimization is to use discrete event simulation to calculate the results of the complex problem and then, feeding that into the model which can be represented using the mixed-integer ...

7

I suspect there are a few specific problems for which the answer is "yes," and I hope others will answer to provide examples of those. But in general I believe the answer is "no." For example, if you formulate the minimum-spanning tree problem as an IP and try to solve it with a general-purpose solver, it will be much slower than just using Prim's or ...

7

This will be opinion based, but I personally like "Handbook of meta heuristics" edited by Michel Gendreau and Jean-Yves Potvin. https://link.springer.com/book/10.1007/978-1-4419-1665-5 There is also "Metaheuristics for Business Analytics" if you are teaching business school students. https://www.springer.com/gp/book/9783319681177

7

A greedy heuristic is natural to try here: Declare all groups to be admissible. Find an admissible group $g$ with the largest weight. Set $u_g=1$. Declare all groups $h$ with $N_h \cap N_g \not= \emptyset$ inadmissible. If some $i$ is still uncovered, go to step 2. For your sample data in the linked question, this greedy heuristic returns groups \{11,12,...

6

There are two possible situations. 1) You still want to solve your VRP exactly or obtain a valid lower bound. Then heuristic pricing is used only to speed up column generation (and it is always used nowadays). At the end, you always need to solve the pricing problem (or at least its relaxation) exactly. A standard approach for heuristic pricing is some ...

6

Contrary to the other answers, I claim that you don't need to solve the pricing problem exactly, not even as a last resort after trying heuristics. If you do solve it exactly, then you found the optimal solution (say $z^*_\text{LP}$) to the relaxed reduced master problem at the node. But this is not needed: you want to use $z^*_\text{LP}$ as a lower bound ...

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