4.2 Bounded variables

Many variables have natural upper bounds: a capacity, a demand, a binary choice relaxed to \([0, 1]\). Writing each \(x_j \leq u_j\) as a constraint adds a row per variable. The bounded-variable simplex method keeps the constraints \(\ell _j \leq x_j \leq u_j\) implicit, by allowing a non-basic variable to sit at either of its bounds.

Consider: minimise \(c^{\mathsf T}x\) subject to \(Ax = b\), \(\ell \leq x \leq u\). A basic solution now fixes each non-basic variable at \(\ell _j\) or \(u_j\) and solves for the basic ones; it is feasible if they lie within their bounds.

Theorem 4.2.1. A basic feasible solution is optimal if every non-basic variable at its lower bound has \(\bar c_j \geq 0\) and every non-basic variable at its upper bound has \(\bar c_j \leq 0\).

Proof. For any feasible \(z\), as in Theorem 3.1.1, \(c^{\mathsf T}z - c^{\mathsf T}x = \sum _{j \in N}\bar c_j(z_j - x_j)\). If \(x_j = \ell _j\) then \(z_j - x_j \geq 0\) and \(\bar c_j \geq 0\); if \(x_j = u_j\) then \(z_j - x_j \leq 0\) and \(\bar c_j \leq 0\). Every term is non-negative. □

If a non-basic variable violates the condition, it is moved away from its bound: increased if it is at \(\ell _j\) with \(\bar c_j < 0\), decreased if at \(u_j\) with \(\bar c_j > 0\). The ratio test now has three kinds of limit on the step \(\theta \):

(i): a basic variable falls to its lower bound;
(ii): a basic variable rises to its upper bound;
(iii): the entering variable itself reaches its other bound, after a step of \(u_j - \ell _j\).

In cases (i) and (ii) the basis changes as usual, and the leaving variable becomes non-basic at the bound it reached. In case (iii) there is a bound flip: the variable moves from one bound to the other, the basis does not change, and no refactorisation is needed. Flips are cheap, and in problems with many bounded variables most iterations are flips (Software 4.4.2). Free variables, with no bounds at all, are kept basic once they enter; the dual simplex method of the section on duality uses the same idea on the dual side.

[next] [prev] [prev-tail] [front] [up]

Questions on this section

Stuck on something here? Ask below and it stays attached to this topic.