Linear optimization: Upper and lower bounds 2

Theory

Linear optimization can be used for set of different problems, which have restrictions such as a given amount of resources or a certain budget.

Example

Linear Programming (LP) Linear programming is the most commonly used optimisation technique in embedded industrial applications. There are many reasons for this. Linear programs are relatively easy to formulate, use and understand. The LP optimisation techniques are also relatively efficient and well developed. A surprisingly large set of real-life problems can be represented as linear programs, or approximated sufficiently well with linear programs. Finally, a number of more advanced modelling and solution techniques are based on linear programming, such as quadratic programming, fractional programming, integer programming, mixed integer programming, constraint logic programming, etc. Different formulations of LP problems The standard formulation of an LP problem is minimization of a linear objective function subject to linear inequality constraints:

min s.t. (1) i=1,…,m xj  0 j=1,…,n

Instead of writing the model using sums and iteration constructs, it is often more convenient to use the vector and matrix notation: min z = cx

s.t. (2) Ax  b x  0

z is the linear objective function to be minimized, x = [x1, …, xn] is a column-vector of n non-negative decision variables, c = [c1, …, cn] is a row-vector of cost coefficients, A is an nm matrix of constraint coefficients, and b = [b1, …, bm] is a column vector of right hand side (RHS) coefficients (sometimes called the resource vector). Other equivalent formulations can also be used: • Maximization: max cx is equivalent to –min –cx. • Greater than inequalities: Ax  b is equivalent to -Ax  -b. • Equality constraints: Ax = b is equivalent to double inequalities Ax  b and Ax  b. • Non-positive variables: y  0 can be substituted by –x where x  0. • Unconstrained variables: unconstrained y can be substituted by difference x1-x2 where x1,x2  0. • Nonzero lower bounds: yymin can be substituted by x=y-ymin where x 0. When formulating an LP problem it is convenient to allow a more general formulation min (max) cx

s.t. (3) bmin  Ax  bmax (two sided constraints) xmin  x  xmax (lower and upper bounds)

In this form each constraint may be two-sided and decision variables may have non-zero lower bounds and upper bounds. Choosing some bmin= bmax yields equality constraints. Upper bounds can be disabled by choosing  as upper bound. Graphical solution of LP problems Small models with two decision variables can be visualized and solved graphically. Each linear inequality constraint divides the plane into two half-planes: the feasible and infeasible side. The feasible region is a convex polygon formed as the intersection of these half-planes. The objective function is a direction in the plane. The optimum solution is always in some corner of this polygon. (In rare cases, two corners may give the same optimal solution. Then also all points on their connecting edge are optimal). Example: Consider the problem min z = -2 x1 - 3 x2

s.t. 3 x1 + 2 x2  24 x1 + 2 x2  12 x2  4 x1  8 x1, x2  0

This problem can be is illustrated graphically in Figure 1. The feasible region is the convex polygon with corners (0,0), (0,4), (4,4), (6,3), and (8,0). The dotted line indicates the direction where z is constant. The minimal feasible solution z = -21 is found by shifting the line as far to the Northeast as possible while still touching the feasible region. As seen in the figure, this happens in point (6,3). Similarly, the maximal feasible solution z = 0 is found in (0,0) by shifting the line as far to Southwest as possible.

Transforming an LP problem into the canonical form Prior to solving an LP problem numerically, it is normally converted into a format, where each constraint is an equality that includes a unique slack variable. This format may either contain or not contain upper bounds for variables. Canonical form with upper bounds The following transformations are applied:

• Inequality constraints Ax  b are converted to equality constraints by adding non-negative slack variables into Ax + s = b, where s0.

• Inequality constraints Ax  b are multiplied by –1 and then converted by adding non-negative slack variables into –Ax + s = –b, where s0.

• The equality constraints Ax = b are augmented with so called artificial variables into Ax + s = b, where 0  s  0. • Two-sided constraints bmin  Ax  bmax can be efficiently handled by using a combined slack/surplus variable: Ax + s = bmax, where 0  s  bmax-bmin After these transformations, the canonical form of the LP problem with upper bounds is obtained:

min z = cx s.t. (4) Ax + s = b 0  x  xmax 0  s  smax

The x-variables are called structural variables. The s-variables are called slacks for short. The only difference between the s-variables and x-variables is that the objective function coefficients of s-variables are known to be zeroes and the constraint coefficients of the s-variables are known to form an identity matrix. If we do not want to highlight these differences, we can extend the x-vector to include the s-variables and augment the c and xmax vectors and the A-matrix correspondingly. Then the LP problem can be written as

min z = c’x’ s.t. A’x’ = b, 0  x’  x’max.

In this form the matrix A’ consists of the original A corresponding to the original x-variables and an mm identity matrix I corresponding to the s-variables. Non-zero lower bounds and negative variables can be modelled easily through substitution of variables, as described earlier. For example the canonical form with upper bounds of the sample model is min z = -2 x1 - 3 x2

s.t. 3 x1 + 2 x2 + s1 = 24 x1 + 2 x2 + s2 = 12 0  x1  8 0  x2  4 0  s1, s2  

Canonical form without upper bounds The following transformations are applied: • Upper bounds for variables are treated as inequalities. • Inequality constraints Ax  b are converted to equality constraints by adding non-negative slack variables into Ax + s = b, where s0.

• Inequality constraints Ax  b are multiplied by –1 and then converted by adding non-negative slack variables into –Ax + s = –b, where s0.

• Equality constraints Ax = b are treated as two separate inequalities Ax  b and Ax  b. • Two-sided constraints bmin  Ax  bmax are treated as two separate inequalities. After these transformations, the canonical form of the LP problem without upper bounds is obtained: min z = cx

s.t. (5) Ax + s = b x, s  0

In the canonical form without upper bounds a model is often larger (has more constraints and variables) than with upper bounds. The previous sample model can be written in canonical format without upper bounds as min z = -2 x1 - 3 x2

s.t. 3 x1 + 2 x2 + s1 = 24 x1 + 2 x2 + s2 = 12 x2 + s3 = 4 x1 + s4 = 8 x1, x2, s1, s2, s3, s4  0