Definition
Linear Programming
Linear programming is the optimisation problem with fixed input
, , : Choose a feasible
satisfying the linear inequalities; scores each unit of . Unlike ILP, variables may be real-valued. LP is solvable in polynomial time. Columns correspond to variables; rows correspond to constraints.
Decision Version
Given a target
, the decision version asks