Skip to main content
22 votes
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. ...
Kevin Dalmeijer's user avatar
17 votes
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 ...
prubin's user avatar
  • 39.3k
13 votes

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 ...
prubin's user avatar
  • 39.3k
11 votes
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,...
Ruslan Sadykov's user avatar
11 votes
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 ...
Rolf van Lieshout's user avatar
11 votes
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 ...
Albert Schrotenboer's user avatar
11 votes
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)$ ...
RobPratt's user avatar
  • 32.3k
10 votes
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 ...
Marco Lübbecke's user avatar
10 votes

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 (...
prubin's user avatar
  • 39.3k
10 votes

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 ...
RobPratt's user avatar
  • 32.3k
10 votes
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 ...
prubin's user avatar
  • 39.3k
10 votes

"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 ...
Oguz Toragay's user avatar
  • 8,652
10 votes
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 ...
Richard's user avatar
  • 3,459
10 votes

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, ...
PeterD's user avatar
  • 1,636
9 votes

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 ...
Kevin Dalmeijer's user avatar
9 votes
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} &...
prubin's user avatar
  • 39.3k
9 votes

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 ...
RobPratt's user avatar
  • 32.3k
9 votes

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 ...
Kuifje's user avatar
  • 13.5k
8 votes
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 ...
alerera's user avatar
  • 1,542
8 votes

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 ...
Geoffrey De Smet's user avatar
8 votes

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 ...
A.Omidi's user avatar
  • 8,950
8 votes

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 ...
Mehdi's user avatar
  • 683
8 votes

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 ...
Rolf van Lieshout's user avatar
8 votes
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 ...
RobPratt's user avatar
  • 32.3k
8 votes

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 ...
Hexaly's user avatar
  • 2,976
8 votes

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. ...
Joris Kinable's user avatar
7 votes

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. ...
PSLP's user avatar
  • 2,401
7 votes
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 ...
LarrySnyder610's user avatar
7 votes

What is good introductory literature on (meta)heuristics?

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 ...
Sune's user avatar
  • 6,552
7 votes
Accepted

Heuristic solution to the graph partitioning problem

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= \...
RobPratt's user avatar
  • 32.3k

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