Examples

Graph problems

Examples that encode graph cuts, colouring, covers, independent sets, and tours.

Max-Cut – Find a 2-colour partition of a weighted graph that maximises the cut weight.
Graph Coloring – Assign colours to graph nodes so adjacent nodes do not share a colour.
Maximum Independent Set – Select the largest subset of graph nodes with no selected edge between them.
Vertex Cover – Select the smallest vertex subset that covers every graph edge.
Travelling Salesman Problem – Find the shortest Hamiltonian tour through a random symmetric distance matrix.

Examples that select subsets, cover demands, pack bins, and balance integer weights.

Knapsack – Select items that maximise value while respecting a capacity constraint.
Bin Packing – Pack items into the minimum number of fixed-capacity bins.
Set Cover – Select the minimum set collection whose union covers the universe.
Weighted Set Cover – Select sets with capacities to cover element demands at minimum cost.
Number Partition – Split positive integers into two subsets with nearly equal sums.
Portfolio Optimization – Select a fixed-size portfolio while penalising higher-order risk interactions.

Examples that reduce clauses and higher-order pseudo-Boolean objectives to quadratic models.

Max-3-SAT – Find the assignment that satisfies the maximum number of 3-literal clauses.
Cubic Optimization – Minimise a cubic pseudo-Boolean objective through HOBO degree reduction.
Quartic Optimization – Minimise a degree-4 pseudo-Boolean objective through two-stage REDUCE chaining.