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.