Goal Programming

Overview

Note that the Goal Programming functionality of the Optimizer will be dropped in a future release. This functionality will be replaced by an example program, available with this release (see goal_example.c in the examples/optimizer/c folder of the installation), that provides the same functionality as the original library function XPRSgoal(GOAL) but is implemented using the Optimizer library interface.

Goal programming is an extension of linear programming in which targets are specified for a set of constraints. In goal programming there are two basic models: the pre–emptive (lexicographic) model and the Archimedean model. In the pre–emptive model, goals are ordered according to priorities. The goals at a certain priority level are considered to be infinitely more important than the goals at the next level. With the Archimedean model, weights or penalties for not achieving targets must be specified and one attempts to minimize the weighted sum of goal under–achievement.

In the Optimizer, goals can be constructed either from constraints or from objective functions (N rows). If constraints are used to construct the goals, then the goals are to minimize the violation of the constraints. The goals are met when the constraints are satisfied. In the pre–emptive case we try to meet as many goals as possible, taking them in priority order. In the Archimedean case, we minimize a weighted sum of penalties for not meeting each of the goals. If the goals are constructed from N rows, then, in the pre–emptive case, a target for each N row is calculated from the optimal value for the N row. This may be done by specifying either a percentage or absolute deviation that may be allowed from the optimal value for the N rows. In the Archimedean case, the problem becomes a multi–objective linear programming problem in which a weighted sum of the objective functions is to be minimized.

In this section four examples will be provided of the four different types of goal programming available. Goal programming itself is performed using the XPRSgoal (GOAL) command, whose syntax is described in full in the reference section of this manual.

Pre-emptive Goal Programming Using Constraints

For this case, goals are ranked from most important to least important. Initially we try to satisfy the most important goal. Then amongst all the solutions that satisfy the first goal, we try to come as close as possible to satisfying the second goal. We continue in this fashion until the only way we can come closer to satisfying a goal is to increase the deviation from a higher priority goal.

An example of this is as follows:

Initially we try to meet the first goal (G1), which can be done with x=5.0 and y=1.6, but this solution does not satisfy goal 2 (G2) or goal 3 (G3). If we try to meet goal 2 while still meeting goal 1, the solution x=6.0 and y=0.0 will satisfy. However, this does not satisfy goal 3, so we repeat the process. On this occasion no solution exists which satisfies all three.

Archimedean Goal Programming Using Constraints

We must now minimize a weighted sum of violations of the constraints. Suppose that we have the following problem, this time with penalties attached:

Then the solution will be the solution of the following problem:

In this case a penalty of 8 units is incurred for each unit that 7x + 3y is less than 40 and so on. the final solution will minimize the weighted sum of the penalties. Penalties are also referred to as weights. This solution will be x=6, y=0, d₁=d₂=d₃=0 and d₄=5, which means that the first and second most important constraints can be met, while for the third constraint the right hand side must be reduced by 5 units in order to be met.

Note that if the problem is infeasible after all the goal constraints have been relaxed, then no solution will be found.

Pre-emptive Goal Programming Using Objective Functions

Suppose that we have a set of objective functions and knowing which are the most important. As in the pre–emptive case with constraints, goals are ranked from most to least important. Initially we find the optimal value of the first goal. Once we have found this value we turn this objective function into a constraint such that its value does not differ from its optimal value by more than a certain amount. This can be a fixed amount (or absolute deviation) or a percentage of (or relative deviation from) the optimal value found before. Now we optimize the next goal (the second most important objective function) and so on.

For example, suppose we have the following problem:

For each goal the sense of the optimization (max or min) and the percentage (P) or absolute (D) deviation must be specified. For OBJ1 and OBJ3 a percentage deviation of 10% and 20%, respectively, have been specified, whilst for OBJ2 an absolute deviation of 4 units has been specified.

We start by maximizing the first objective function, finding that the optimal value is –4.615385. As a 10% deviation has been specified, we change this objective function into the following constraint:

Now that we know that for any solution the value for the former objective function must be within 10% of the best possible value, we minimize the next most important objective function (OBJ2) and find the optimal value to be 51.133603. Goal 2 (OBJ2) may then be changed into a constraint such that:

and in this way we ensure that for any solution, the value of this objective function will not be greater than the best possible minimum value plus 4 units.

Finally we have to maximize OBJ3. An optimal value of 141.943995 will be obtained. Since a 20% allowable deviation has been specified, this objective function may be changed into the following constraint:

The solution of this problem is x=0.238062 and y=6.923186.

Archimedean Goal Programming Using Objective Functions

In this, the final case, we optimize a weighted sum of objective functions. In other words we solve a multi–objective problem. For consider the following:

In this case we have three different objective functions that will be combined into a single objective function by weighting them by the values given in the weights column. The solution of this model is one that minimizes:

The resulting values that each of the objective functions will have are as follows:

The solution is x=0.0 and y=7.692308.