Recall that any linear program can be reduced to a more constrained canonical form where all variables are non-negative, the constraints are given by inequalities, and the objective is the maximization of a cost function. More formally, our variables are xi . Our objective is max c x = maxP i cixi for some con- stants ci . The jth constraint is P i aijxi bj for some constants aij , bj . Finally, we also have the constraints xi 0. An example canonical form LP: maximize 5x1 + 3x2