Goal Programming

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 Archimedian 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 Archimedian model weights or penalties for not achieving targets must be specified, and we attempt to minimize the sum of the weighted infeasibilities.

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.

The example in this section demonstrates how Mosel can be used for implementing pre-emptive Goal Programming with constraints. We try to meet as many goals as possible, taking them in priority order.

Example problem

The objective is to solve a problem with two variables x and y (x,y ≥ 0), the constraint

and the three goal constraints

where the order given corresponds to their priorities.

Implementation

To increase readability, the implementation of the Mosel model (file goalctr.mos) is organized into three blocks: the problem is stated in the main part, procedure preemptive implements the solution strategy via preemptive Goal Programming, and procedure print_sol produces a nice solution printout.

model GoalCtr
 uses "mmxprs"

 forward procedure preemptive
 forward procedure print_sol(i:integer)

 declarations
  NGOALS=3                          ! Number of goals
  x,y: mpvar                        ! Decision variables
  dev: array(1..2*NGOALS) of mpvar  ! Deviation from goals
  MinDev: linctr                    ! Objective function
  Goal: array(1..NGOALS) of linctr  ! Goal constraints
 end-declarations

 100*x + 60*y <= 600                ! Define a constraint

! Define the goal constraints
 Goal(1):=  7*x + 3*y >= 40
 Goal(2):= 10*x + 5*y = 60
 Goal(3):=  5*x + 4*y >= 35

 preemptive                         ! Pre-emptive Goal Programming

At the end of the main part, we call procedure preemptive to solve this problem by pre-emptive Goal Programming. In this procedure, the goals are at first entirely removed from the problem (`hidden'). We then add them successively to the problem and re-solve it until the problem becomes infeasible, that is, the deviation variables forming the objective function are not all 0. Depending on the constraint type (obtained with gettype) of the goals, we need one (for inequalities) or two (for equalities) deviation variables.

Let us have a closer look at the first goal (Goal_1), a ≥ constraint: the left hand side (all terms with decision variables) must be at least 40 to satisfy the constraint. To ensure this, we add a dev₂. The goal constraint becomes 7·x + 3·y + dev₂ ≥ 40 and the objective function is to minimize dev₂. If this is feasible (0-valued objective), then we remove the deviation variable from the goal, thus turning it into a hard constraint. It is not required to remove it from the objective since minimization will always force this variable to take the value 0.

We then continue with Goal₂: since this is an equation, we need variables for positive and negative deviations, dev₃ and dev_4. We add dev_4-dev₃ to the constraint, turning it into 10·x + 5·y +dev_4-dev₃ = 60 and the objective now is to minimize the absolute deviation dev_4+dev₃. And so on.

 procedure preemptive

! Remove (=hide) goal constraint from the problem
  forall(i in 1..NGOALS) sethidden(Goal(i), true)

  i:=0
  while (i<NGOALS) do
    i+=1
    sethidden(Goal(i), false)       ! Add (=unhide) the next goal

    case gettype(Goal(i)) of        ! Add deviation variable(s)
     CT_GEQ: do
              Deviation:= dev(2*i)
              MinDev += Deviation
             end-do
     CT_LEQ: do
              Deviation:= -dev(2*i-1)
              MinDev += dev(2*i-1)
             end-do
     CT_EQ : do
              Deviation:= dev(2*i) - dev(2*i-1)
              MinDev += dev(2*i) + dev(2*i-1)
             end-do
     else    writeln("Wrong constraint type")
             break
    end-case
    Goal(i)+= Deviation

    minimize(MinDev)                ! Solve the LP-problem
    writeln(" Solution(", i,"): x: ", getsol(x), ", y: ", getsol(y))

    if getobjval>0 then
     writeln("Cannot satisfy goal ",i)
     break
    end-if
    Goal(i)-= Deviation             ! Remove deviation variable(s) from goal
  end-do

  print_sol(i)                      ! Solution printout
 end-procedure

The procedure sethidden(c:linctr, b:boolean) has already been used in the previous chapter (Section Column generation) without giving any further explanation. With this procedure, constraints can be removed (`hidden') from the problem solved by the optimizer without deleting them in the problem definition. So effectively, the optimizer solves a subproblem of the problem originally stated in Mosel.

To complete the model, below is the procedure print_sol for printing the results.

 procedure print_sol(i:integer)
  declarations
   STypes={CT_GEQ, CT_LEQ, CT_EQ}
   ATypes: array(STypes) of string
  end-declarations

  ATypes::([CT_GEQ, CT_LEQ, CT_EQ])[">=", "<=", "="]

  writeln(" Goal", strfmt("Target",11), strfmt("Value",7))
  forall(g in 1..i)
   writeln(strfmt(g,4), strfmt(ATypes(gettype(Goal(g))),4),
     strfmt(-getcoeff(Goal(g)),6),
     strfmt( getact(Goal(g))-getsol(dev(2*g))+getsol(dev(2*g-1)) ,8))

  forall(g in 1..NGOALS)
   if (getsol(dev(2*g))>0) then
    writeln(" Goal(",g,") deviation from target: -", getsol(dev(2*g)))
   elif (getsol(dev(2*g-1))>0) then
    writeln(" Goal(",g,") deviation from target: +", getsol(dev(2*g-1)))
   end-if
 end-procedure

end-model

When running the program, one finds that the first two goals can be satisfied, but not the third.