1.5.2 Linear and Integer Programming One notable computational problem is that of solving linear programs. A linear program consists of a set of variables x j (1 j n), a set of constraints indexed by i (1 i m), and an objective. Constraint i is defined by parameters a ij (1 j n) and b i , resulting in the following inequality constraint: n j=1 a ij x j b i . The objective is defined by parameters c j , resulting in the following objective: n j=1 c j x j . The goal is to find a vector of nonnegative values for the x j that maximizes the value of the objective while still meeting all the constraints (i.e., all the inequalities should hold). Natural variants, such as not requiring variables to take nonnegative values, allowing equality constraints, having a minimization rather than a maximization objective, and so on, are not substantively different from this basic setup. There is a rich theory of linear programming; for the purpose of this book, what is most important to know is that linear programs can be solved to optimality in polynomial time. Thus, if a computational problem can be formulated as (equivalently, reduced to) a polynomial- sized linear program, then it can be solved in polynomial time.