Performing a goal programming analysis using CPLEX

Answer

The basic principle behind Goal Programming is to convert multiple (and possibly conflicting) objectives into a single goal to find an efficient (but not necessarily an optimum) solution.

Goal Programming is usually carried out using one of the two methods:

• A Weighted Method:
  
  A weighted objective function consisting of a single objective is constructed from a weighted sum of functions representing the multiple objectives of the problem. These weights are user defined and determine the priority of each objective. For example, if the ith model has a preference weight p_i for the corresponding goal G_i, then the weighted objective function for n such objectives would be:
  Minimize: sum(i in 1..n) p_i*G_i

• A Preemptive Method:
  
  A preemptive method is useful where the model consists of several LP's with different priorities as assigned by the user. Each LP is optimized one at a time such that the optimum value of a higher priority objective is not degraded by a lower priority objective. This can be achieved by either adding the previous objective as a constraint to the successive model or looking at the reduced cost for each solved model. Note that the former approach works for both continuous and discrete models, while the latter only works for linear programs. In cases where a limited amount of degradation in the higher priority objective is acceptable, use the former approach.
• Adding an objective as a constraint:
  
  For example, if objective G_1 has higher priority than G_2, then solve for G_1 first. Suppose the optimal objective associated with G_1 is Z1*. After solving, specify the constraint:
  
  G_1 = Z1*
  
  as a constraint in the successive LP. Change the objective from G_1 to G_2, then reoptimize the LP. Each successive model would thereby consist of an extra constraint and avoid degradation of the previous solution. In cases where a certain percentage of degradation is acceptable, the constraint on G_1 becomes an inequality. For example, assuming positive objective values, if a 5 percent degradation of G_1 was acceptable when minimizing G_2, the constraint on G_1 would be:
  
  G_1 <= 1.05 Z1*
  
• Fixing nonbasic variables with nonzero reduced costs to zero:
  
  This is achieved by identifying nonbasic variables that have nonzero reduced costs at the optimal basis of the LP. Nonbasic variables with zero reduced costs can enter the basis without affecting the objective value for the optimally solved LP model. However, nonbasic variables with nonzero reduced costs, if left unchecked, could become positive while solving successive lower priority optimization problems. This could degrade the quality of a higher priority solution. All CPLEX APIS provide routines to get reduced costs, from which one can identify the nonbasic variables with nonzero reduced costs and fix them at their current values.