Questions tagged [heuristics]

For questions related to algorithms that are expected to produce good solutions, with no guarantee of optimality, in relatively short computation time.

Filter by
Sorted by
Tagged with
19
votes
5answers
740 views

Solving pricing problem heuristically in column generation algorithm for VRP

In the set covering/column generation approach for the VRP (Balinski and Quandt (1964), or e.g. this tutorial), the basic idea is: Generate some routes. Solve the set covering problem using those ...
9
votes
3answers
606 views

Graph problems as integer programs

Suppose I give a solver (CPLEX, Gurobi, SCIP or anything else) an IP which is a reformulation of a stable set problem (or vertex cover problem or coloring problem) of some graph, is there a way I can ...
9
votes
1answer
116 views

Heuristics for mixed integer linear and nonlinear programs

What are some primal heuristics that mixed-integer linear and nonlinear program solvers use to quickly obtain a reasonably good feasible solution?
2
votes
1answer
95 views

On what kind of problems a local search may perform better than MIP / CP techniques? [closed]

In combinatorial optimization, on what type of problem a local search may lead to better & quicker solutions than usual mixed-integer programming and constraint programming techniques ? By type ...
9
votes
1answer
51 views

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

For some insertion-type heuristics for the traveling salesman problem, we have a fixed worst-case error bound of the form: $$\frac{z^H}{z^*} \le \eta,$$ where $z^H$ is the objective value of the ...
11
votes
2answers
103 views

Neigbourhoods in Large Neighbourhood Search (LNS) algorithms

I have been trying to implement a variant of LNS on a graph for TSP. One of the ways that I can define a neighborhood for TSP is to find $k$-shortest path between two nodes. But the choice of these ...