Linear Programming, Duality and Rounding
Relaxing integer decisions to fractions gives a problem that can be solved, and its optimum bounds the integer one. Duality supplies the certificate that a solution is optimal, and rounding turns the fractional answer back into a real one at a cost that can be bounded.
What a learner can do afterwards
- Write a combinatorial problem as a linear program and state its dual
- Use a dual solution as a certificate for a bound on the primal
- Round a fractional solution and bound what the rounding lost
1 · Read
A linear program writes a decision problem in math. Pick variables for the choices you control, write the limits you face as linear inequalities, and write the goal as a linear expression over costs, profits, or resources. Practice the full path from a word problem to a clean program, since everything after starts from writing one with confidence.
Relaxing turns hard integer choices into easy fractions. For vertex cover, replace each take-or-skip 0 or 1 with a fraction between 0 and 1, then solve the easier fractional program. Its optimum bounds the integer one from below, so the fraction tells you how far any true answer can possibly go.
Every linear program owns a dual: a second program built from the same data whose any feasible value certifies a bound on the first. A good dual solution proves your answer sits near optimal without you ever knowing the optimum itself. Read the primal and the dual off the same matrix, and let the dual carry the certificate.
Round fractions back into decisions with a rule you can price. Rounding every variable at or above one half up to 1 keeps every edge covered while at most doubling the cost. A fractional optimum of 6 rounds to at most 12, so the rounding loses at most a factor of 2.
Write it linear, relax to fractions, certify with the dual, and round at a bounded price.
More to read
MGTS 113 - Introduction to Quantitative Decision Making - Practice Questions
This is a free set of practice questions with full solutions from a college course on quantitative decision making. The part that matters most for you is the section on linear programming models. A linear program is a way to write a decision problem with math: you pick variables for the choices you control, write the limits you face as linear inequalities, and write the thing you want to maximize or minimize as a linear expression. Working through these practice questions lets you see the full path from a word problem about costs, profits, or resources to a clean linear program you can solve. The set also reviews the algebra and graphing skills that linear programming builds on, plus related ideas like break-even analysis, where you find the point that costs and revenue balance. Because solutions are included, you can try a problem yourself first and then check each step of your work. It is a good warm-up, since relaxation, duality, and rounding all start from being able to write a problem as a linear program with confidence. Relaxing vertex cover shows the next steps: replace each take or skip decision (0 or 1) with a fraction between 0 and 1, solve the easier fractional program, and its optimum bounds the integer one from below. Every linear program has a dual, a second program whose any feasible value certifies a bound on the primal, so a good dual solution proves your answer is near optimal without knowing the optimum itself. Rounding turns fractions back into decisions: round every variable at or above one half up to 1 and the rest down, which keeps every edge covered while at most doubling the cost, so the rounding loses at most a factor of 2.
2 · Watch
Take it off screen
Where it sits
Learn first
Optional connections
This opens up
Nothing builds on it yet.
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.