NP-Hard Problems

This page collects examples and patterns for classic NP-hard optimization problems.

Several basic examples are already covered in the existing galleries:

• Example 02: Knapsack for 0/1 knapsack

• Example 03: Minimum Set Cover for minimum set cover

• Example 04: Minimum Vertex Cover for minimum vertex cover

• Example 12: WiFi Channel Assignment for graph-coloring channel assignment

• CVRP for routing with MTZ load constraints

Example 01: Job Shop Scheduling

A job shop scheduling model with machine conflicts, per-job operation order, and a makespan objective.

New primitives

• hermax.model.Model.interval()

• hermax.model.IntervalVar.ends_before()

• hermax.model.IntervalVar.no_overlap()

• hermax.model.Model.upper_bound()

Model

Each job is a sequence of operations. Each operation must run on one machine for a given duration, operations of the same job must respect their order, and operations that share a machine cannot overlap.

\[\begin{split}\begin{aligned} \text{Operations:}\quad & O_{j,1},\dots,O_{j,k_j} \\ \text{Job precedence:}\quad & O_{j,t} \text{ ends before } O_{j,t+1} \\ \text{Machine capacity:}\quad & O_{j,t} \text{ and } O_{j',t'} \text{ do not overlap if they use the same machine} \\ \text{Makespan upper bound:}\quad & \mathrm{end}(O_{j,k_j}) \le M \qquad \forall j \\ \text{Objective:}\quad & \min M \end{aligned}\end{split}\]

This is one of the classic NP-hard scheduling problems [5], and it is a good fit for interval variables because the model is fundamentally about start times, end times, and resource conflicts.

Note

This example uses hermax.model.Model.upper_bound() instead of an exact max(...) aggregate. Under minimization, that is often the cleanest way to model makespan: the optimizer will push the upper bound down to the true schedule end automatically. An exact aggregate is still useful when the maximum value itself needs to be reused elsewhere in the model.

Code

examples/model/26_job_shop_scheduling.py

from hermax.model import Model


jobs = {
    "J1": [("M1", 3), ("M2", 2), ("M3", 2)],
    "J2": [("M2", 2), ("M3", 1), ("M1", 4)],
    "J3": [("M3", 4), ("M1", 3), ("M2", 1)],
}

horizon = sum(duration for ops in jobs.values() for _, duration in ops)

m = Model()
ops = {}
machine_ops = {"M1": [], "M2": [], "M3": []}

for job, route in jobs.items():
    for step, (machine, duration) in enumerate(route):
        task = m.interval(f"{job}_{step}", start=0, duration=duration, end=horizon)
        ops[(job, step)] = task
        machine_ops[machine].append(task)

for job, route in jobs.items():
    for step in range(len(route) - 1):
        m &= ops[(job, step)].ends_before(ops[(job, step + 1)])

for machine, tasks in machine_ops.items():
    for i in range(len(tasks)):
        for j in range(i + 1, len(tasks)):
            m &= tasks[i].no_overlap(tasks[j])

makespan = m.upper_bound(
    [ops[(job, len(route) - 1)].end for job, route in jobs.items()],
    name="makespan",
)

m.obj[1] += makespan

r = m.solve()

print("status:", r.status)
print("makespan:", r[makespan])
for job, route in jobs.items():
    print(job + ":")
    for step, (machine, duration) in enumerate(route):
        task = ops[(job, step)]
        slot = r[task]
        print(
            f"  op{step + 1}: {machine} dur={duration} "
            f"start={slot['start']} end={slot['end']}"
        )

Output

The printed schedule shows the operation order inside each job and the final makespan.

$ python examples/model/26_job_shop_scheduling.py
status: optimum
makespan: 11
J1:
  op1: M1 dur=3 start=0 end=3
  op2: M2 dur=2 start=3 end=5
  op3: M3 dur=2 start=7 end=9
J2:
  op1: M2 dur=2 start=0 end=2
  op2: M3 dur=1 start=2 end=3
  op3: M1 dur=4 start=3 end=7
J3:
  op1: M3 dur=4 start=3 end=7
  op2: M1 dur=3 start=7 end=10
  op3: M2 dur=1 start=10 end=11

Example 02: Bin Packing

A bin packing model with item-to-bin assignment variables, bin capacity constraints, and symmetry break.

New primitives

• hermax.model.Model.bool_matrix()

• hermax.model.Model.bool_vector()

• hermax.model.BoolVector.exactly_one()

• hermax.model.Literal.implies()

Model

Each item must go in exactly one bin. Every bin has the same capacity. The objective is to minimize the number of bins used.

\[\begin{split}\begin{aligned} \text{Variables:}\quad & x_{i,b} \in \{0,1\}\ \text{(item } i \text{ is placed in bin } b\text{)} \\ & u_b \in \{0,1\}\ \text{(bin } b \text{ is used)} \\ \text{Assignment:}\quad & \sum_b x_{i,b} = 1 \qquad \forall i \\ \text{Capacity:}\quad & \sum_i size_i x_{i,b} \le C \qquad \forall b \\ \text{Linking:}\quad & x_{i,b} \Rightarrow u_b \qquad \forall i,b \\ \text{Symmetry break:}\quad & u_{b+1} \Rightarrow u_b \qquad \forall b \\ \text{Objective:}\quad & \min \sum_b u_b \end{aligned}\end{split}\]

Bin packing is an NP-hard problem [1], and it is also a common benchmark for approximation algorithms [2].

Note

The symmetry break says that bin b+1 cannot be used unless bin b is already used. This does not change the set of achievable packings, but it removes many equivalent bin permutations and usually helps search.

Code

examples/model/27_bin_packing.py

from hermax.model import Model


sizes = [4, 8, 1, 4, 2, 1]
capacity = 10
num_items = len(sizes)
num_bins = num_items

m = Model()
place = m.bool_matrix("place", num_items, num_bins)
used = m.bool_vector("used", num_bins)

for i in range(num_items):
    m &= place.row(i).exactly_one()

for b in range(num_bins):
    m &= sum(sizes[i] * place[i][b] for i in range(num_items)) <= capacity
    for i in range(num_items):
        m &= place[i][b].implies(used[b])

for b in range(num_bins - 1):
    m &= used[b + 1].implies(used[b])

for b in range(num_bins):
    m.obj[1] += ~used[b]

r = m.solve()

print("status:", r.status)
print("bins_used:", sum(1 for b in range(num_bins) if r[used[b]]))
for b in range(num_bins):
    if r[used[b]]:
        items = [i for i in range(num_items) if r[place[i][b]]]
        load = sum(sizes[i] for i in items)
        print(f"bin {b}: items={items} load={load}/{capacity}")

Output

The result shows the number of bins used and one concrete packing.

$ python examples/model/27_bin_packing.py
status: optimum
bins_used: 2
bin 0: items=[1, 4] load=10/10
bin 1: items=[0, 2, 3, 5] load=10/10

Example 03: Maximum Clique

A graph model where the goal is to select the largest fully connected group of vertices.

New primitives

• hermax.model.BoolDict

• Hard clauses over graph decisions

• Soft unit objective terms for cardinality maximization

Model

Each vertex has one Boolean decision. If two vertices are not connected by an edge, they cannot both belong to the clique. The objective is to maximize the number of selected vertices.

\[\begin{split}\begin{aligned} \text{Variables:}\quad & x_v \in \{0,1\}\ \text{(vertex } v \text{ is in the clique)} \\ \text{Non-edge constraints:}\quad & \neg x_u \lor \neg x_v \qquad \forall \{u,v\} \notin E \\ \text{Objective:}\quad & \max \sum_{v \in V} x_v \end{aligned}\end{split}\]

The maximum clique problem is one of Karp’s original NP-complete problems [3] and is a common graph optimization benchmark [4].

Note

Maximum clique and maximum independent set are two sides of the same graph idea. An independent set in a graph is a clique in its complement.

Problem

Code

examples/model/28_maximum_clique.py

from hermax.model import Model


vertices = [0, 1, 2, 3, 4, 5]
edges = {
    (0, 1),
    (0, 2),
    (0, 3),
    (1, 2),
    (1, 3),
    (2, 3),
    (3, 4),
    (3, 5),
    (4, 5),
}

edge_set = {tuple(sorted(e)) for e in edges}

m = Model()
pick = m.bool_dict("pick", vertices)

for i in range(len(vertices)):
    for j in range(i + 1, len(vertices)):
        u = vertices[i]
        v = vertices[j]
        if (u, v) not in edge_set:
            m &= (~pick[u] | ~pick[v])

for v in vertices:
    m.obj[1] += pick[v]

r = m.solve()

clique = [v for v in vertices if r[pick[v]]]
print("status:", r.status)
print("size:", len(clique))
print("clique:", clique)

Output

The result shows one maximum clique found in the example graph.

$ python examples/model/28_maximum_clique.py
status: optimum
size: 4
clique: [0, 1, 2, 3]

Solution

References

[1]

Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.

[2]

Edward G. Coffman Jr., Michael R. Garey, and David S. Johnson. Approximation algorithms for bin packing: A survey. In Approximation Algorithms for NP-hard Problems, pages 46–93. PWS Publishing Co., 1996.

[3]

Richard M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85–103. Springer, 1972.

[4]

Immanuel M. Bomze, Marco Budinich, Panos M. Pardalos, and Marcello Pelillo. The maximum clique problem. In Handbook of Combinatorial Optimization, pages 1–74. Springer, 1999.

[5]

Jan Karel Lenstra, A. H. G. Rinnooy Kan, and Peter Brucker. Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1:343–362, 1977.