Combinatorial optimization studies how to choose the best option from a finite set of possibilities. Students use it to model routing, scheduling, assignment, network design, and resource allocation problems. This cheat sheet helps organize the main problem types, formulas, and algorithms used to solve discrete optimization problems.
It is useful when a problem involves yes or no choices, ordering, paths, networks, or limited resources.
The core idea is to define decision variables, an objective function, and constraints. Many models use binary variables, where x = 1 means an option is chosen and x = 0 means it is not chosen. Graph problems often involve vertices, edges, weights, paths, trees, flows, and matchings.
Important solution methods include greedy algorithms, dynamic programming, branch and bound, and integer programming.
Key Facts
- A combinatorial optimization model has decision variables, an objective such as minimize cost or maximize value, and constraints that limit feasible choices.
- A binary decision variable satisfies x in {0, 1}, where x = 1 usually means select an item and x = 0 means do not select it.
- A common linear objective is maximize c1x1 + c2x2 + ... + cnxn subject to constraints such as a1x1 + a2x2 + ... + anxn <= b.
- In a shortest path problem, the goal is to find a path from a start vertex to an end vertex with minimum total edge weight.
- A minimum spanning tree connects all vertices in a connected weighted graph using exactly n - 1 edges with the least possible total weight.
- In a 0-1 knapsack problem, the goal is maximize value v1x1 + v2x2 + ... + vnxn subject to weight w1x1 + w2x2 + ... + wnxn <= W and xi in {0, 1}.
- A matching in a graph is a set of edges with no shared endpoints, and a perfect matching pairs every vertex exactly once.
- A greedy algorithm makes the best local choice at each step, but it is correct only when the problem has a property that guarantees local choices lead to a global optimum.
Vocabulary
- Objective function
- The expression being maximized or minimized, such as total profit, total cost, or total distance.
- Constraint
- A rule or inequality that limits which solutions are allowed.
- Feasible solution
- A solution that satisfies every constraint in the problem.
- Graph
- A structure made of vertices and edges used to represent networks, routes, relationships, or choices.
- Integer programming
- An optimization method where some or all decision variables must be whole numbers.
- Greedy algorithm
- An algorithm that builds a solution by repeatedly choosing the best available option at the current step.
Common Mistakes to Avoid
- Using continuous variables for yes or no decisions, which is wrong because fractional choices like x = 0.4 may not make sense in real applications.
- Maximizing when the problem asks for a minimum, which reverses the goal and can produce the worst useful solution instead of the best one.
- Ignoring feasibility, which is wrong because a solution with a great objective value is invalid if it breaks even one constraint.
- Assuming every greedy strategy is optimal, which is wrong because greedy choices can fail unless the problem has the required structure.
- Confusing a shortest path with a minimum spanning tree, which is wrong because a shortest path connects two selected vertices while a spanning tree connects all vertices.
Practice Questions
- 1 A delivery route has edge distances AB = 4, AC = 7, BC = 2, BD = 5, and CD = 1. What is the shortest distance from A to D?
- 2 For a 0-1 knapsack with capacity 10, items have weights 6, 4, and 5 and values 12, 7, and 9. Which combination gives the greatest value without exceeding capacity?
- 3 A connected graph has 8 vertices. How many edges must any spanning tree of this graph have?
- 4 Explain why choosing the cheapest available edge at every step does not automatically solve every network optimization problem.
Understanding Combinatorial Optimization Reference
The hardest part is usually turning a story into a model without losing an important detail. Start by naming exactly what one decision represents. A route variable might represent using one road.
An assignment variable might represent giving one worker one shift. Then check the units. Costs should be in the same currency or time unit before they are added.
Constraints often come from physical limits, rules, or promises. A delivery vehicle has a capacity limit. A student cannot attend two classes held at the same time.
A useful habit is to write each constraint as a full sentence before converting it into math. This catches mistakes such as allowing an item to be chosen twice or forgetting that every customer must be served.
Graph models are especially useful because the picture can reveal structure that a list of equations hides. In a road network, an edge weight may be distance, travel time, fuel use, or toll cost. These choices can produce different best routes.
The shortest distance route is not always the fastest route. A spanning tree is useful when building the links is expensive, such as laying cable between towns or connecting sensors in a building. It gives connectivity without unnecessary loops.
Matching appears in school situations too, such as pairing students with projects, tutors with learners, or players with teams. The no shared endpoint rule means one person cannot receive two assignments when the model requires one each.
Different solution methods succeed for different reasons. A greedy rule is fast because it commits to a choice early, but a locally cheap edge or locally valuable item can block a better final arrangement. Students should learn the proof idea behind a greedy method, not only memorize its steps.
Dynamic programming avoids this problem by storing answers to smaller subproblems. For a packing problem, a state can record how much capacity remains and which items have been considered. This can be reliable, though the table may become too large when capacities or input sizes grow.
Integer programming can express many real rules clearly. Solvers often first study a relaxed version where choices can take fractional values, then use bounds to rule out groups of impossible or inferior choices.
A claimed optimum needs checking. Verify that every constraint is satisfied before comparing objective values. In a route, confirm that consecutive roads join properly and that the path reaches the destination.
In an assignment, count each person and each task. Then ask how stable the answer is. A small change in cost, capacity, or demand can change the best choice completely.
Real data may be uncertain or incomplete, so a mathematically best answer can still be impractical. A route may cross a road closed at certain hours.
A schedule may be unfair even when it uses the fewest staff hours. Good optimization includes checking assumptions, explaining tradeoffs, and recognizing when extra human rules belong in the model.