# Tag Info

Accepted

### Solving pricing problem heuristically in column generation algorithm for VRP

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

### Why does the design of heuristics require considerable domain knowledge?

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

### Which approaches exist to solve a TSP?

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

### Obtaining optimality gaps when using hybrid exact-heuristic approaches to vehicle routing problems

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

### Search approach to solve optimization problem with only a minimum where time series get scaled

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

### Neigbourhoods in Large Neighbourhood Search (LNS) algorithms

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

### How to partition a graph with optimal number of groups?

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)$ ...
Accepted

### Heuristics for mixed integer linear and nonlinear programs

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

### Graph problems as integer programs

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

### Is there a heuristic approach to the MILP problem?

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

### Black-box optimization with linear programming?

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

### "Out of the box" Mixed Integer Programming Heuristics

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

### Verifying optimality of heuristic solutions

Generally, the only way to prove that a given solution is optimal is to obtain a valid lower bound (assuming minimization) that matches the incumbent solution (with $\epsilon$ tolerance, to be ...

### Book to learn metaheuristics

The most famous book on metaheuristics is probably the Handbook of Metaheuristics: Michel Gendreau and Jean-Yves Potvin. 2010. Handbook of Metaheuristics (2nd. ed.). Springer Publishing Company, ...

### Search approach to solve optimization problem with only a minimum where time series get scaled

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

### Is there a heuristic approach to the MILP problem?

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

### Graph problems as integer programs

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

### How to solve this convex problem heuristically?

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

### Is there a fixed worst-case error bound for farthest-insertion?

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

### Neigbourhoods in Large Neighbourhood Search (LNS) algorithms

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

### Black-box optimization with linear programming?

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

### Solving pricing problem heuristically in column generation algorithm for VRP

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

### Obtaining optimality gaps when using hybrid exact-heuristic approaches to vehicle routing problems

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

### How to exploit known solution in MILP

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

### Do better construction heuristics increase the performance of improvement heuristics?

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

### Which approaches exist to solve a TSP?

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

### Integrating genetic algorithm (or other heuristic methods) with CPLEX

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

### Graph problems as integer programs

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