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. ...
- 6,063
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 ...
- 37.9k
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 ...
- 37.9k
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,...
- 1,394
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 ...
- 2,305
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 ...
- 1,859
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)$ ...
- 30.5k
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 ...
- 5,909
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 (...
- 37.9k
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 ...
- 30.5k
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 ...
- 37.9k
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 ...
- 8,622
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 ...
- 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, ...
- 1,461
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 ...
- 6,063
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} &...
- 37.9k
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 ...
- 30.5k
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 ...
- 12.9k
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 ...
- 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 ...
- 4,675
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 ...
- 8,450
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 ...
- 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 ...
- 2,305
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 ...
- 30.5k
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 ...
- 2,936
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. ...
- 3,396
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. ...
- 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 ...
- 13.1k
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 ...
- 6,352
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= \...
- 30.5k
Only top scored, non community-wiki answers of a minimum length are eligible