Skip to content

Constructive heuristics

Part 4 · Heuristic algorithms · Chapter 30 · Lecture notes, volume 4 (PDF) · Slides (1/2) · Slides (2/2) · Exercises: Constructive heuristics · App: Bin packing heuristics · App: List scheduling and LPT · App: Vertex coloring: greedy and DSATUR · App: TSP: nearest neighbour and 2-opt

Prerequisites

  • From this module, the chapter «Heuristic algorithms: definitions»: primal and dual bounds, the gap, and the four reference instances.

  • From this module, the chapters on the problems: the KP, the BPP, \(P\,||\,C_{\max}\), the TSP and the VCP.

Objectives

At the end of this chapter you will be able to:

  • apply the greedy algorithm to the KP with the three orders (profit, weight, efficiency);

  • execute FF, FFD and BFD for the BPP, and LIST and LPT for \(P\,||\,C_{\max}\);

  • build a TSP tour by nearest neighbour and by the insertion heuristics;

  • apply randomized construction, regret insertion and the pilot method;

  • compare the results with the dual bounds, and explain when a constructive heuristic fails.

30.1 Constructive heuristics

Definition 30.1: Constructive heuristic

A constructive heuristic is a heuristic algorithm that builds one feasible solution step by step: it starts from the empty partial solution and extends it with one element at a time, until the solution is complete.

  • The elements depend on the problem: the items selected for the knapsack, the assignments of items to bins and of jobs to machines, the edges of a tour.

  • The quality of the result depends on how the element to add is chosen at every step (Section 30.3).

  • Overview

    Constructive heuristics

    Open

  • The problems and the assumptions · The greedy paradigm

    The greedy paradigm

    Open

  • 30.4 The 0/1 knapsack problem: which order?

    Open

  • 30.5 The bin packing problem: first sort, then pack

    Best Fit Decreasing · What sorting gives, and what it does not

    Open

  • 30.6 Scheduling on parallel machines: longest jobs first

    Longest processing time first

    Open

  • 30.7 The travelling salesman problem: append or insert?

    Multi-start nearest neighbour · Insertion heuristics · A comparison on a larger instance

    Open

  • 30.8 Vertex coloring: greedy and DSATUR

    DSATUR · What the greedy coloring guarantees · DSATUR as a heuristic

    Open

  • 30.9 Randomized construction

    Open

  • 30.10 Look-ahead and regret

    Look-ahead: the pilot method

    Open

  • 30.11 What constructive heuristics give, and what they do not

    Open

  • Typical mistakes · In summary

    In summary

    Open

Next: The problems and the assumptions · The greedy paradigm

Exercises on this chapter: Constructive heuristics

In the interactive lab: Bin packing heuristics, List scheduling and LPT, Vertex coloring: greedy and DSATUR, TSP: nearest neighbour and 2-opt.