Linear and Convex Optimization. Michael H. Veatch

Linear and Convex Optimization

even when these assumptions do not fully hold.

We will use matrix notation for linear programs whenever possible. Let images , images , images , and

Here images , images , and images are column vectors. If all the constraints are equalities, they can be written images . Similarly, “ images ” constraints can be written images .

Example 1.2 Consider the linear program

(1.4) equation

Converting the objective function and constraints to matrix form, we have

If we let

then this linear program can be written

It is important to distinguish between the structure of an optimization problem and the data that provides a specific numerical example. The structure of (1.4) is a minimization linear program with “ images ” constraints and nonnegative variables; the data are the values in images , images , and images .

To write a mixture of “ images ” and “ images ” constraints, it is convenient to use submatrices

and write, e.g.

1.4.2 Integer Programs

Many practical optimization problems involve making discrete quantitative choices, such as how many fire trucks of each type a fire department should purchase, or logical choices, such as whether or not each drug being developed by a pharmaceutical company should be chosen for a clinical trial. Both types of situations can be modeled by integer variables.

Consider again the linear program (1.1) with the alternative objective function (1.2). The variables represent the number of pallets of tents and food. If we restrict the variables to be integers, i.e. we can only load whole pallets, then the problem becomes an integer program and can be stated

(1.5) equation

Without the integer restriction, it is a linear program with optimal solution images and optimal value images . However, because this solution is not integer (i.e. not all of its variables have integer values), it is not feasible for the integer program. Only solutions that have integer values and satisfy the constraints are feasible, as shown in Figure 1.4. Once we have determined the feasible points, an optimal solution can be found graphically by sweeping the contour line images in the improving direction (upward). The last point touched by the line is optimal. In this case the last point is images and the optimal value is images .

Geometric representation of the feasible integer solutions for.

Figure 1.4 Feasible integer solutions for (1.5).

Although the graphical method was fairly simple for this example, it is quite different than when solving linear programs. Note that:

There is not necessarily an optimal solution at the intersection of two constraints. In our example, lies only on the constraint line . In other examples, the optimal solution may not lie on any constraint.

The optimal solution is not necessarily obtained by rounding the linear program optimal solution. In fact, there is no limit to how far the optimal solution could be from the linear programming solution.

The integer program can be infeasible when the linear program is feasible.

These difficulties suggest that integer programs are harder to solve than linear programs, which we will see is true. Even solving a two‐variable integer program graphically can be tedious. However, we do not necessarily need to generate all integer feasible solutions. For example, if we start by generating the feasible point images , then we draw the contour line through it and check for integer points in the linear program's feasible region and above the contour. Checking points to the right of images (because this contour does not touch the feasible region for images ), images is infeasible but images qualifies, so it is optimal. The idea of using a feasible integer solution to eliminate other integer points from consideration will be used in Chapter 13.

The general form of an integer program is the same as a linear program with the added constraint that the variables are integers. If only some of the variables are restricted

Скачать книгу