Heuristic Methods for Hard Problems

1 Introduction
The word heuristic’s etymology has origin from the ancient Greek Eureka!.
We indicate as heuristic algorithms simple and efficient methods used for
computing good solutions to difficult combinatorial problems. They are very
useful for hard problems where exact solutions may be computationally pro-
hibited. In practical applications, such as industrial case studies, heuristics
are often exploited.
Typically, there is a trade-off between efficacy and efficiency: to find
better solutions (i.e., be effective), an algorithm should spend a relevant
amount of computational time (i.e., lose efficiency), and vice versa.
In contrast to exact algorithms (e.g., branch and bound), heuristic algo-
rithms do not guarantee that the solutions they provide are optimal. More-
over, in contrast to approximation algorithms, there is no guarantee about
how far the heuristic solution is from the optimal solution. Note that, it is
hard in general to prove the optimality of a feasible solution for IPs.
Heuristic algorithms are generally divided into two types: construc-
tion heuristics, which build a feasible solution from scratch, and improve-
ment heuristics, which start from an initial solution and iteratively refine
it. These algorithms can possibly be effectively combined by starting with a
construction heuristic to find an initial feasible solution and then moving to
an improvement heuristic to get a better result.
As we will see, in the following several greedy heuristics are discussed.
A greedy algorithm is any algorithm that follows the heuristic strategy of
making the locally optimal choice at each stage. Note that this framework,
in general, may lead to sub-optimal solutions, like for hard problems.

1
2 Construction Heuristics
2.1 Binary Knapsack: Greedy Heuristic
In this section, we will explore the greedy heuristic for solving the binary
knapsack problem.
Recall the binary knapsack problem, which is defined as follows:
( n n
)
X X
max p j xj : aj xj ≤ b, xj ∈ {0, 1}
j=1 j=1

where pj represents the profit associated with item j, aj is the weight of item
j, and b is the capacity of the knapsack.
The greedy heuristic for the binary knapsack problem proceeds as follows:
pj
1. Order the items by their profit-to-weight ratio aj
in descending order.

2. Initialize an empty set K to represent the knapsack contents, and set

the remaining capacity b̄ = b.

3. Repeat the following steps until the knapsack is full or there are no
items left in the list:

(a) Pick the next item j from the ordered list.

(b) If the item’s weight aj is less than or equal to the remaining ca-
pacity b̄, add it to K and reduce b̄ by aj .
(c) Otherwise, skip the item.

4. Output the set of selected items K.

Note that the procedure is very similar to the one used to solve the binary
knapsack’s linear relaxation.
To illustrate the greedy heuristic, consider the following example. Let
n = 8,
pj = (15, 100, 90, 60, 40, 15, 10, 1),
aj = (2, 20, 20, 30, 40, 30, 60, 10),
pj
and b = 102. Items are already ordered by descending aj
.

2
 Following the greedy heuristic:

The total profit of this solution is z G = 280, which serves as a lower

bound on the optimal solution (recall we are maximizing).
To estimate how close this solution is to optimal, we can solve the linear
programming (LP) relaxation of the knapsack problem, which provides an
upper bound z U on the optimal solution.
For our example, the LP relaxation gives z U = 295. Thus, the absolute
U G
optimality gap is z U − z G = 15. The relative optimality gap is z z−z
G
15
= 280 =
5.35%, meaning our solution is at most 5.35% away from the optimal.
Although depending on the problem hardness, as common indications
solutions with roughly 5% of relative optimality gap are considered good,
whereas near-optimal solutions are within 2%.

2.1.1 Exercise
Consider the following binary knapsack instance:

n = 6; pj = (50, 50, 64, 46, 50, 5);

aj = (56, 59, 80, 64, 75, 17); b = 190.

Using the greedy heuristic, find the solution and calculate the absolute and
relative optimality gaps. Use the lower bound from the greedy solution to
calculate the optimality gap.

2.2 Greedy Heuristics for STSP

In this section, we discuss two greedy heuristics for solving the Symmetric
Traveling Salesman Problem (STSP). Recall that STSP involves finding the

3
minimum cost route that visits each city (node) exactly once and returns to
the starting point.

2.2.1 Nearest Neighbor Heuristic

The Nearest Neighbor Heuristic is a simple and intuitive approach for
constructing a feasible solution to the STSP. This heuristic constructs a tour
incrementally by choosing the nearest unvisited city at each step.
1. Initialize a partial tour T as an empty set.

2. Choose an arbitrary starting node i to begin the tour. Add this node
to T ; this node is called the seed.

3. Repeat the following steps until all nodes have been included in the
tour:

(a) Find the closest unselected neighbor n(i) of the current node i.
(b) Add n(i) to the partial tour T .
(c) Set i ← n(i), and repeat the process.

4. Once all nodes have been visited, output the completed tour T .
Different starting node i may lead to different solutions. Therefore, a
multi-start variant of the algorithm may repeat the entire heuristic by set-
ting alternative seeds (starting nodes). The best solution among the ones
computed is then kept.

2.2.2 Greedy Feasible Heuristic

The Greedy Feasible Heuristic takes a slightly more sophisticated ap-
proach than the nearest neighbor heuristic. Rather than building a tour by
selecting nodes, this heuristic constructs the tour by choosing edges based
on distance, while avoiding the creation of subtours.

1. Initialize a partial tour T as an empty set.

2. Begin by selecting the shortest edge (i, j) in the graph, and add it to
the partial tour T .

3. Repeat the following steps until the tour is complete:

4
 (a) Find the next unselected shortest edge (k, l).
(b) If adding (k, l) to T does not create a subtour and does not cause
any node in T to have a degree greater than 2, then add (k, l) to
T.
(c) Else, discard the edge (k, l) and continue to the next shortest
unselected edge.

4. Once all nodes are connected, output T .

Consider the following example of a distance matrix for a complete graph

with 10 nodes.

Distance Matrix
2 3 4 5 6 7 8 9 10
1 92 99 50 41 79 46 29 50 70
2 78 49 94 21 64 63 42 37
3 60 84 61 54 86 76 51
4 45 35 20 26 17 20
5 80 36 55 59 64
6 46 50 29 16
7 45 37 30
8 21 45
9 25
10
Using this distance data, apply both the nearest neighbor heuristic and
the greedy feasible heuristic to construct feasible tours and compare the
results.
By applying the nearest neighbor heuristic with seed 1, we obtain the
tour

5
 When using seed 6, the computed tour is

Given that STSP is a minimization problem, the latter solution is better.

This same solution is obtained by applying the greedy feasible heuristic.
To compute the optimality gap, we can compute the 1-tree relaxation of
STSP.

Finally, the relative optimality gap is

2.2.3 Exercise
For practice, use the distance data from the “Odysseus Example” in the slides
”The Travelling Salesman Problem a brief survey.pdf ” by Martin Grötschel
available in the course page on moodle. Follow these steps:

• Construct feasible tours using both the nearest neighbor heuristic and
the greedy feasible heuristic.

• Calculate the absolute and relative optimality gaps for each tour, using
the 1-tree relaxation.

6
2.3 Greedy Heuristic for Simple Plant Facility Loca-
tion Problem
In the Simple Plant Location Problem (SPLP), we aim to determine the
optimal locations to open facilities in order to serve a set of clients while
minimizing the overall costs.
Formally, a set of m potential facility sites are given as well as n client
locations, each of which requires service from exactly one facility. Let fi be
the fixed cost of opening a facility at site i, where i ∈ {1, . . . , m}, and cij be
the cost to serve client j from facility site i. The objective is to minimize
the total cost, which includes both the facility opening costs and the service
costs. The mathematical formulation of this problem is as follows:

m
X m X
X n
minimize fi y i + cij xij
i=1 i=1 j=1
Xm
subject to xij = 1, ∀j = 1, . . . , n
i=1
xij ≤ yi , ∀i = 1, . . . , m and j = 1, . . . , n
xij , yi ∈ {0, 1}, ∀i = 1, . . . , m and j = 1, . . . , n
where yi = 1 if facility i is opened, and 0 otherwise; xij = 1 if client j is
assigned to facility i, and 0 otherwise.
A greedy heuristic approach to tackle the SPLP follows:
1. Let Q be the set of facilities to be opened by the algorithm. Initially,
Q = ∅ (no facilities are open).
2. For each facility k that is not yet open (since initially, none is open),
calculate the function value as follows:
X n
X
v(Q ∪ {k}) = fi + fk + min cℓj
ℓ∈Q∪{k}
i∈Q j=1

This expression represents the cost of opening facility k and assigning

all clients to the cheapest available facility in Q ∪ {k}.
3. Choose the facility k ∗ that minimizes v(Q ∪ {k}) (breaking ties arbi-
trarily if necessary) and add it to Q. This results in the initial set Q
containing one open facility.

7
 4. For each facility k not in Q, compute the function value:
X n
X
v(Q ∪ {k}) = fi + fk + min cℓj
ℓ∈Q∪{k}
i∈Q j=1

5. Select the facility k ∗ that yields the smallest v(Q ∪ {k}).

6. If v(Q ∪ {k ∗ }) < v(Q), then add k ∗ to Q. Otherwise, stop, as no

improvement can be made.

Consider an example where we have m = 5 facility sites and n = 6 clients.

The costs cij of serving each client i from facility j are as follows:
 
12 13 6 0 1
 8 4 9 1 2
 
 2 6 6 0 1
cij = 
 
 3 5 2 10 8

 8 0 5 10 8
2 0 3 4 1
The facility opening costs are given by:

f = (4, 3, 4, 4, 7)

Using the greedy heuristic described, we can determine the optimal set
of facilities to open and assign clients accordingly.

8
 Iterate to find a possible improvement of the value function:

2.4 Heuristics for the Minimum Weight Edge Cover

by Nodes
Let us recall the problem of finding a Minimum Weight Edge Cover in an
undirected graph with positive node weights. Consider an undirected graph
G = (V, E) where each node i ∈ V has an associated positive weight ci . Our
goal is to find a subset of nodes C ⊆ V with the minimum total weight such
that every edge (i, j) ∈ E has at least one of its endpoints in C. If an edge
(i, j) has at least one endpoint in C, we say that the edge is covered.

2.4.1 Greedy Heuristic

The simple greedy algorithm builds the set C iteratively.

1. Compute the degree di of each node i, where di represents the number

of edges incident to node i.

2. Calculate the ratio dcii for each node i, which reflects the weight per
degree for each node. Note that, nodes with lower weight are preferred
along with nodes having higher degrees. Inded, picking a node with
high degree will cover more edges at once.

3. Initialize C as an empty set.

4. Repeat the following steps until all edges in E are covered:

ci
(a) Select the node i with the smallest ratio di
.

9
 (b) Add node i to C.
(c) Remove node i and all edges incident to it from the graph.
ci
(d) Recompute the ratios di
for the remaining nodes.

5. Output the set C.

To illustrate the process of this greedy algorithm, consider the example

graph shown in Figure 3.

Figure 1: An example graph for finding a greedy edge cover.

10
 By solving the LP-relaxation of the formulation for the minimum weight
edge cover, a lower bound of 82 is obtained. If one solves the integer formula-
tion exactly through a solver (e.g., GUROBI), one can see that the heuristic
solution is luckily optimal.

2.4.2 A Rounding Heuristic For Minimum Weight Edge Cover

We now discuss a rounding heuristic for solving the Minimum Weight Edge
Cover problem. It uses the LP-relaxation of the problem formulation and
provides a way to approximate the optimal integer solution with a bounded
performance guarantee. Given the existence of such a guarantee, this heuris-
tic is actually an approximation algorithm.
The study of approximation algorithms is nowadays a very active and
challenging field of research. As a noteworthy example, one may recall the
Christofides algorithms for STSP dated 1976. It is an approximation algo-
rithm that guarantees that its solutions will be within a factor of 32 of the
optimal tour length, that is 50% of the relative optimality gap. Such theo-
retical result was later improved after roughly 45 years by achieving a new
factor of 32 + ϵ, with ϵ small constant.
To formulate the Minimum Weight Edge Cover problem as an integer
optimization problem, define a variable yi for each vertex i ∈ V , where yi = 1
if vertex i is included in the cover, and yi = 0 otherwise. The formulation
reads as:
X
minimize ci y i
i∈V
subject to yi + yj ≥ 1, ∀(i, j) ∈ E
yi ∈ {0, 1}, ∀i ∈ V

The rounding heuristic proceeds as follows:

1. Solve the LP relaxation of the formulation. Let the optimal solution of

this LP relaxation be y LP , with an objective value z LP .

2. Initialize the cover set C as empty.

3. For each vertex i ∈ V :

(a) If yiLP ≥ 21 , add vertex i to C.

11
 4. Output the set C.

Two questions arise: i ) Is the output C a valid edge cover? ii ) What is the
performance guarantee of this heuristic compared to the optimal solution?

Proposition 1. The set C is an edge cover.

Proof. To show that C is indeed an edge cover, we proceed by contradiction.

Assume that C is not an edge cover. Then, there would exist an edge
(i, j) ∈ E for which neither endpoint i nor j is in C, meaning i ∈
/ C and j ∈/ C.
This implies that neither i nor j was selected by the heuristic, so yiLP < 21
and yjLP < 12 . However, this contradicts the LP constraint yi + yj ≥ 1 for
all (i, j) ∈ E, because if yi < 21 and yj < 12 , then yi + yj < 1, violating the
constraint.
Since this leads to a contradiction, C must be an edge cover.
Let z R denote the cost of the edge cover produced by the heuristic, and
let z ∗ represent the cost of the optimal edge cover.
We aim to show the following result:

Theorem 1. The heuristic has a performance guarantee within a factor of

2, that is z R ≤ 2z ∗ .
1
Proof. We know that yiLP ≥ 2
for all i ∈ C. Multiplying both sides by ci
(which is positive) yields:
1
ci yiLP ≥ ci
2
Summing over all i ∈ C, we get:
X X
2 ci yiLP ≥ ci
i∈C i∈C

The right-hand side is exactly z R , the cost of the cover generated by the
heuristic.
LP LP LP
P
The left-hand side is less than or equal to 2z , since 2z = 2 i∈C ci yi +
LP LP
P P
2 i∈C
/ ci y i ≥ 2 i∈C ci yi . Therefore, we have:

z R ≤ 2z LP ≤ 2z ∗

12
3 Improvement Heuristics
Improvement heuristics are a class of algorithms that start from an initial fea-
sible solution and attempt to improve upon iteratively. The primary idea is
to identify a neighborhood of the current feasible solution and find the best
possible solution within this set. If this new solution improves the current
solution, we move to it. If not, the search stops, and the current solution is
considered a locally optimal solution concerning the chosen neighborhood.
The selection of the neighborhood is crucial as it affects the efficacy and
efficiency of the heuristic: a small neighborhood leads to fast computation
but typically worse solutions, whereas a large neighborhood allows reaching
better solutions but at a non-negligible computational cost.
Several well-known heuristics fall into this category, including Local Ex-
change, Tabu Search, Simulated Annealing, and Genetic Algorithms. Besides
the former that embeds basic strategies, the other heuristics are typically re-
ferred to as metaheuristics, that is higher-level frameworks designed to
avoid local optima traps and explore a wide search space. These features
made metaheuristic very popular choices and can be easily adapted to deal
with several optimization problems.

Figure 2: Plot of the objective function value f (x),

x1 local optimum, x∗ global optimum of a minimization problem.

Just to give an intuition of how metaheuristics work, let us consider Simu-

lated Annealing. This metaheuristic is a heuristic inspired by physics princi-
ples. While exploring the neighborhood, a dynamic parameter describing the
system temperature is used to determine the probability of accepting wors-
ening solutions. At high temperatures, the exploration/diversification
phase is fostered by allowing the accept largely worse solutions and move

13
widely in the solution space. As the system cools down and the temperature
decreases, the heuristic behaves more and more like a local search algorithm,
accepting only improving solutions. This refinement step is typically called
exploitation/intensification, where the solution quality is pushed as far
as possible in a close neighborhood.
Genetic Algorithms are heuristics inspired by biology/genetics. It oper-
ates on a population of solutions (individuals or chromosomes) and evolves
them over generations to improve their quality with respect to an objective
(fitness) function. The selection (reproductive) mechanism typically takes
elite candidates from the population, the one with higher fitness, and recom-
bines them (crossover) by mixing their features to get new solutions (off-
spring). Moreover, with a small probability, new solutions can be randomly
and partially modified (mutation) to introduce diversity into the population
and prevent premature convergence to suboptimal solutions. Finally, the new
solutions are inserted in the population according to replacement strategies.
In this framework, exploration is granted by generating a wide variety of
solutions, whereas elitism in selection and replacement fosters exploitation.
We will look now at the two remaining heuristics in detail.

3.1 2-Exchange (2-Opt) Heuristic for the Symmetric

TSP (STSP)
The 2-exchange, or 2-opt heuristic, is a local search heuristic designed for
STSP. We define a tour T as a 2-neighbor of a tour T ′ if T can be obtained
from T ′ by deleting two edges and adding two other edges. The 2-exchange
heuristic procedure works as follows:

1. Take a tour T .

2. For every pair of edges, denoted by (i, j) and (k, ℓ), within the tour:

(a) Remove these two edges from the current tour T .

(b) Add two new edges, (i, ℓ) and (j, k), forming a new tour T ′ .
(c) If the length of T ′ is shorter than the length of T , set T = T ′ as
the new current solution and return to step 1.

3. Output T .

14
The heuristic iterates until no improvement is possible, that is when a local
optimal solution is found. At each iteration, the heuristic possibly evaluates
n(n−3)
2
neighbors, where n is the number of nodes of the tour. In the proposed
implementation, the first improving 2-exchange operation is accepted by the
heuristic. An alternative implementation can evaluate all the possible 2-
exchanges in each iteration, then pick the best one.
The procedure can be generalized to consider 3-exchanges or k-exchanges,
but the size of the neighborhood grows very quickly and the heuristic becomes
rapidly inefficient for relevant values of n.
As example, let us consider the graph in the following figure and a corre-
sponding starting tour of cost 29.

Figure 3: On the left, a complete graph with edge costs, on the right a
feasible initial tour T .

At the first iteration of the 2-exchange heuristic, the neighborhood is

made by 5 alternative tours:

15
 Tour (a) has a cost of 31 and it is not chosen. Tour (b) has a cost 27 < 29,
hence the corresponding exchange is accepted. However, note that tour (d)
would lead to a better cost of 24.
The procedure then continues by evaluting 2-exchanges from tour (b).
One of the 2-exchange would bring back to the previous (less convenient)
tour, hence only 4 alternative 2-exchanges are considered:

Although tour (b) has a cost of 23, our naive version of the algorithm
selects tour (a) as new tour with cost 24.
The next iteration evaluates 4 new 2-exchange operations (see Figure 6),
but no improvement is achieved. Therefore, tour (b) in Figure 5 of cost 24
is the heuristic output.

16
3.2 Local Search for Binary Knapsack
For BKP, a neighboring solution is obtained by flipping the value of the i-th
variable: if the current value of xi is 1, flipping will set it to 0; conversely,
if xi is 0, flipping will set it to 1. By flipping one variable at a time, we
generate n neighbors. If there are better neighbors, move to the best among
them and repeat the process until no further improvement is possible (or a
maximum number of iterations). Note that this idea can be applied to any
0-1 integer optimization problem.
This simple local search can be improved, especially in terms of diversi-
fication capability, by using some refinements:
1. Multi-start: The multi-start approach attempts to diversify the search
by beginning from different initial feasible solutions multiple times.
Each time, the search is conducted independently, and the best solu-
tion found is retained as the final solution.

2. Enlarging Neighborhood: If no improvement is found in the cur-

rent neighborhood, the search space can be extended by enlarging the
neighborhood. For instance, instead of flipping one variable at a time,
we could flip two variables simultaneously. This approach increases the
computational cost, but it may yield better solutions.

3. Tabu Search: The local search can be embedded in the Tabu Search
metaheuristic framework. In Tabu Search, when no improving neighbor
is available, it is possible to accept a move leading to a worse solution.
To prevent the search from revisiting points previously explored and
to mitigate the risk of cycling, certain points are declared tabu (for-
bidden) for a specific number of iterations. The set of tabu solutions is
typically stored in the tabu list L.
As example, let us consider an instance of BKP, with tabu rule lasting
two iterations and stopping criterion reached after 5 iterations.

max 18x1 + 25x2 + 11x3 + 14x4

s.t. 2x1 + 2x2 + x3 + x4 ≤ 3
x1 , x2 , x3 , x4 ∈ {0, 1}

Start with an initial solution x0 = (1, 0, 0, 0) of value 18 and set x0 ∈ L

tabu.

17
The local search generates by flipping operations the neighbors:

18