Catalogue of combinatorial problems¶
All the problems defined in the course, by family. Each problem has its own page: its definition, its assumptions and what the course does on it, technique by technique.
Catalogue (PDF) The problems at a glance
-
Knapsack problems
Select a subset or a multiset of items of maximum total profit subject to capacity constraints.
0/1 knapsack (KP) · Subset sum (SSP) · Bounded knapsack (BKP) · Unbounded knapsack (UKP) · Multidimensional knapsack (MDKP) · Multiple knapsack (MKP) · Multiple-choice knapsack (MCKP) · Knapsack with setups (KPS)
-
Packing problems
Pack items into the minimum number of bins of equal capacity.
-
Coloring problems
Color the vertices of a graph with the minimum number of colors.
-
Clique problems
Find a set of pairwise adjacent vertices of maximum cardinality or weight.
Maximum clique (MCP) · Maximum stable set (MSSP) · Vertex-weighted maximum clique (VWMCP) · Edge-weighted maximum clique (EWMCP)
-
Routing problems
Find a shortest tour that visits every city exactly once.
Travelling salesman (TSP) · Metric TSP · Asymmetric TSP (ATSP) · Hamiltonian cycle (HCP)
-
Scheduling problems
Assign jobs to parallel machines so as to minimize the makespan.
Identical parallel machines (P||Cmax) · Fixed number of identical machines (Pm||Cmax) · Parallel machines with different speeds (Q||Cmax) · Unrelated parallel machines (R||Cmax)
-
Lot sizing problems
Plan the production over a horizon of periods at minimum cost.
Capacitated lot sizing (CLS) · Uncapacitated lot sizing (ULS) · Capacitated lot sizing with constant capacity (CLS-C) · Lot sizing with several products and setup times (MLS) · Lot sizing with initial stock (LS-SI) · Lot sizing with overtime (LS-OT) · Lot sizing with unsatisfied demand (LS-UD)
-
Miscellaneous problems
Problems with an exact total length or amount, solved by dynamic programming.