linear-programming

Linear Programming

Overview

Linear-programming answers are modeling and certificate problems before they are solver problems. First identify decisions, linear constraints, objective direction, feasibility status, and the proof certificate that would convince a skeptical reader the optimum is correct.

Core principle: an LP formulation is useful only when every variable has a real-valued meaning, every constraint preserves the original feasible set, the objective direction matches the bound semantics, and optimality can be certified by duality or complementary slackness.

Shared Parent Conventions

• Follow the parent clrs skill for mathematical formatting: every expression, inequality, matrix relation, objective value, and asymptotic bound belongs in a display LaTeX block.
• Keep tables verbal. Put standard forms, duals, graph constraints, and certificate equations in display blocks adjacent to the table instead of inside table cells.
• Use shortest-paths for ordinary shortest-path algorithms, maximum-flow for augmenting-path and cut mechanics, and this skill when the task asks for LP formulation, duality, feasibility, or solver-based modeling.
• Do not announce that you are using this skill. Deliver the polished formulation, proof, or review directly.

When to Use

Use this skill for:

• turning a resource-allocation, graph, flow, matching, shortest-path, or scheduling-style problem into a linear program;
• converting between arbitrary LP descriptions and the chapter's maximization standard form;
• deciding whether a model is feasible, infeasible, bounded, unbounded, or missing constraints;
• explaining simplex geometry, vertex optimality, ellipsoid methods, interior-point methods, or solver choice;
• writing primal-dual pairs, weak-duality upper bounds, equality certificates, strong-duality arguments, or complementary-slackness checks;
• distinguishing continuous LP relaxations from integer linear programs and avoiding false polynomial-time claims.