3.3 The Linear Programming Model

Tackling a multi-knapsack problem with a LP solver amounts to implementing a branch & bound solver to obtain integral solutions. The idea is to compute a continuous solution and to branch over the problem variables with continuous solutions. This is done until only integral problem variables are left. This is what the procedure DistributeKnapSackLP does.

proc {DistributeKnapSackLP Vs ObjFn Constraints MaxProfit}
      DupVs = {DuplicateRIs Vs}
      DupMaxProfit V DupV
      DupMaxProfit = {RI.var.bounds
                      {RI.getLowerBound MaxProfit}
                      {RI.getUpperBound MaxProfit}}
      {LP.solve DupVs ObjFn Constraints DupMaxProfit optimal}
      V#DupV = {SelectVar Vs#DupVs}
      case {IsDet V} then 
         DupMaxProfit = MaxProfit
         DupVs        = Vs
            {RI.lessEq {Ceil DupV} V}  
            {RI.lessEq V {Floor DupV}}  
         {DistributeKnapSackLP Vs ObjFn Constraints MaxProfit}

It first duplicates the problem variables (note this is possible due to stability) and invokes the LP solver on them to compute a (possibly continuous) solution. Then it selects the first duplicated continuous problem variable DupV by SelectVar (see below). If continuous variables are left (see the else branch of the case statement), it creates two choices on the corresponding original problem variable V: \lceil DupV \rceil \le V \vee V \le
\lfloor DupV \rfloor and calls DistributeKnapSackLP recursively. In case no continuous variables are left, an integral solution is found and the original problem variables are unified with duplicated ones.

For completeness sake the auxiliary functions SelectVar and DuplicateRIs are presented here.

fun {SelectVar VsPair}
   case VsPair
   of nil#nil then unit#unit  
   [] (VH|VT)#(RVH|RVT) then 
      % check for integrality
      case RVH == {Round RVH}
      then {SelectVar VT#RVT}
      else VH#RVH end 
   else unit 

fun {DuplicateRIs Vs}
   {Map Vs
    fun {$ V}
        {RI.getLowerBound V}
        {RI.getUpperBound V}}

The procedure KnapsackLP return the script which creates the appropriate parameters for the LP solver and eventually calls DistributeKnapSackLP.

fun {KnapsackLP Problem}
   NumProducts = {Length Problem.profit}
   Resources   = Problem.resources
   proc {$ Sol}
      sol(maxprofit: MaxProfit = {RI.var.decl}
          products: Products = {MakeList NumProducts})
      = Sol
      ObjFn Constraints
      {ForAll Products proc {$ V}
                          {RI.var.bounds 0.0 RI.sup V}
      ObjFn = objfn(row: {Map Problem.profit IntToFloat}
                    opt: max)
      Constraints =  
      {Map {Arity Resources}
       fun {$ ResourceName}
          Resource = Resources.ResourceName
           constr(row: {Map Resource.npp IntToFloat}
                  type: '=<' 
                  rhs: {IntToFloat Resource.ta})
      {DistributeKnapSackLP Products ObjFn Constraints


{ExploreBest {KnapsackLP Problem}  
             proc {$ O N}  
                {RI.lessEq O.maxprofit+1.0 N.maxprofit}  

produces the following search tree.

Tobias Müller
Version 1.4.0 (20080702)