Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
| linear-programming problem | Many problems can be formulated as maximizing or minimizing an objective, given limited resources and competing constraints. If we can specify the objective as a linear function of certain variables, and if we can specify the constraints on resources as equalities or inequalities on those variables, then we have a linear-programming problem
(See page 770)
|
 |
|
|
| linear equality | If b is a real number and f is a linear function, then the equation f(x1, x2, . . . , xn) = b is a linear equality.
(See page 772)
|
|
|
|
| linear inequality | If b is a real number and f is a linear function, then the inequalities f(x1, x2, . . . , xn) ≤ b and f(x1, x2, . . . , xn) ≥ b are linear inequalities
(See page 772)
|
|
|
|
| linear constraints | denote either linear equalities or linear inequalities.
(See page 772)
|
|
|
|
| linear-programming problem | the problem of either minimizing or maximizing a linear function subject to a finite set of linear constraints.
(See page 772)
|
|
|
|
| minimization linear program | the linear program we are to minimize.
(See page 773)
|
|
|
|
| maximization linear program | the linear program we are to maximize.
(See page 773)
|
|
|
|
| standard | a conanical form in which to describe properties of and algorithms for linear programs. Informally, a linear program in standard form is the maximization of a linear function subject to linear inequalities.
(See page 773)
|
|
|
|
| slack | A linear program in slack form is the maximization of a linear function subject to linear equalities. Slack measures the difference between the left-hand and right-hand sides of an equation.
(See pages 773 & 781)
|
|
|
|
| feasible solution | an setting of variables that satisfies all the constraints.
(See page 773)
|
|
|
|
| feasible region | If we graph the constraints in the (x1, x2)-Cartesian coordinate system, the set of feasible solutions forms a convex region in the two-dimensional space called the feasible region.
(See page 773)
|
|
|
|
| objective function | the function we wish to maximize.
(See page 773)
|
|
|
|
| objective value | the value of the objective function at a particular point.
(See page 774)
|
|
|
|
| simplex | If we have three variables, then each constraint is described by a half-space in three-dimensional space. The feasible region formed by the intersection of these half-spaces is called a simplex.
(See page 775)
|
|
|
|
| simplex algorithm | takes as input a linear program and returns an optimal solution.
(See page 775)
|
|
|
|
| ellipsoid algorithm | The first polynomial-time algorithm for linear programming.
(See page 776)
|
|
|
|
| interior-point methods | A second class of polynomial-time algorithms.
(See page 776)
|
|
|
|
| integer linear program | has an additional requirement that all variables take on integer values.
(See page 777)
|
|
|
|
| infeasible solution | a setting of the variables that fails to satisfy at least one constraint.
(See page 778)
|
|
|
|
| infeasible | a linear program which has no feasible solutions.
(See page 778)
|
|
|
|
| feasible | a linear program which has feasible solutions.
(See page 778)
|
|
|
|
| unbounded | a linear program which has some feasible solutions but does not have a finite optimal objective value.
(See page 778)
|
|
|
|
| equality constraints | A linear program not in standard form because it has an equal sign rather than a less-than-or-equal-to.
(See page 778)
|
|
|
|
| inequality constraints | A linear program which is not in standard form because instead of having a less-than-or-equal-to sign, it has a greater-than-or-equal-to sign.
(See page 778)
|
|
|
|
| slack variable | measures the slack, or difference, between the left-hand and right-hand sides of an equation.
(See page 781)
|
|
|
|
| basic variables | the variables on the left-hand side of an equality.
(See page 782)
|
|
|
|
| nonbasic variables | the variables on the right-hand side of an equality.
(See page 782)
|
|
|
|
| tight | property of an equality constraint for a particular setting of its nonbasic variables if they cause the constraint's basic variable to become 0.
(See page 791)
|
|
|
|
| basic solution | set all the (nonbasic) variables on the right-hand side to 0 and then compute the values of the (basic)variables on the left-hand side.
(See page 792)
|
|
|
|
| basic feasible solution | a basic solution which is also feasible.
(See page 792)
|
|
|
|
| pivot | chooses a nonbasic variable xe, called the entering variable, and a basic variable xi, called the leaving variable, and exchanges their roles.
(See page 793)
|
|
|
|
| degeneracy | phenomenon which occurs when an iteration leaves the objective value unchanged.
(See page 802)
|
|
|
|
| cycles | SIMPLEX cycles if the slack forms at two different iterations are identical, in which case, since SIMPLEX is a deterministic algorithm, it will cycle through the same series of slack forms forever.
(See page 802)
|
|
|
|
| Bland's rule | breaks a tie caused by a cycle by always choosing the variable with the smallest index.
(See page 803)
|
|
|
|
| linear programming duality | a very important property. In an optimization problem, the identification of a dual problem is almost always coupled with the discovery of a polynomial-time algorithm. Duality is also powerful in its ability to provide a proof that a solution is indeed optimal.
(See page 804)
|
|
|
|
| primal | the original linear program when referring to dual linear programs.
(See page 805)
|
|
|
|
| weak duality | states that any feasible solution to the primal linear program has a value no greater than that of any feasible solution to the dual linear program.
(See page 805)
|
|
|
|
| auxiliary linear program | finds a slack form for which the basic solution is feasible.
(See page 811)
|
|
|
|
| linear-inequality feasibility problem | Given a set of m linear inequalities on n variables x1, x2, . . . , xn, it asks if there is a setting of the variables that simultaneously satisfies each of the inequalities.
(See page 818)
|
|
|
|
| complementary slackness | describes a relationship between the values of primal variables and dual constraints and between the values of dual variables and primal constraints.
(See page 818)
|
|
|
|
| integer linear-programming problem | a linear-programming problem with the additional constraint that the variables must take on integer values.
(See page 819)
|
2002 McGraw-Hill Higher Education