10.37.8 A Mixed Integer Linear Optimization Example

The predicates bb_inf/[3,5] implement a simple Branch and Bound search algorithm for Mixed Integer Linear (MIP) Optimization examples. Serious MIP is not trivial. The implementation library('clpqr/bb.pl') is to be understood as a starting point for more ambitious users who need control over branching, or who want to add cutting planes, for example.

Anyway, here is a small problem from miplib, a collection of MIP models, housed at Rice University:

     NAME:         flugpl
     ROWS:         18
     COLUMNS:      18
     INTEGER:      11
     NONZERO:      46
     BEST SOLN:    1201500 (opt)
     LP SOLN:      1167185.73
     SOURCE:       Harvey M. Wagner
                   John W. Gregory (Cray Research)
                   E. Andrew Boyd (Rice University)
     APPLICATION:  airline model
     COMMENTS:     no integer variables are binary

            
% library('clpqr/examples/mip')
     
     example(flugpl, Obj, Vs, Ints, []) :-
       Vs = [ Anm1,Anm2,Anm3,Anm4,Anm5,Anm6,
              Stm1,Stm2,Stm3,Stm4,Stm5,Stm6,
              UE1,UE2,UE3,UE4,UE5,UE6],
       Ints = [Stm6, Stm5, Stm4, Stm3, Stm2,
               Anm6, Anm5, Anm4, Anm3, Anm2, Anm1],
     
       Obj =    2700*Stm1 + 1500*Anm1 + 30*UE1
              + 2700*Stm2 + 1500*Anm2 + 30*UE2
              + 2700*Stm3 + 1500*Anm3 + 30*UE3
              + 2700*Stm4 + 1500*Anm4 + 30*UE4
              + 2700*Stm5 + 1500*Anm5 + 30*UE5
              + 2700*Stm6 + 1500*Anm6 + 30*UE6,
     
       allpos(Vs),
       {  Stm1 = 60, 0.9*Stm1 +1*Anm1 -1*Stm2 = 0,
          0.9*Stm2 +1*Anm2 -1*Stm3 = 0, 0.9*Stm3 +1*Anm3 -1*Stm4 = 0,
          0.9*Stm4 +1*Anm4 -1*Stm5 = 0, 0.9*Stm5 +1*Anm5 -1*Stm6 = 0,
          150*Stm1 -100*Anm1 +1*UE1 >= 8000,
          150*Stm2 -100*Anm2 +1*UE2 >= 9000,
          150*Stm3 -100*Anm3 +1*UE3 >= 8000,
          150*Stm4 -100*Anm4 +1*UE4 >= 10000,
          150*Stm5 -100*Anm5 +1*UE5 >= 9000,
          150*Stm6 -100*Anm6 +1*UE6 >= 12000,
          -20*Stm1 +1*UE1 =< 0, -20*Stm2 +1*UE2 =< 0, -20*Stm3 +1*UE3 =< 0,
          -20*Stm4 +1*UE4 =< 0, -20*Stm5 +1*UE5 =< 0, -20*Stm6 +1*UE6 =< 0,
          Anm1 =< 18, 57 =< Stm2, Stm2 =< 75, Anm2 =< 18,
          57 =< Stm3, Stm3 =< 75, Anm3 =< 18, 57 =< Stm4,
          Stm4 =< 75, Anm4 =< 18, 57 =< Stm5, Stm5 =< 75,
          Anm5 =< 18, 57 =< Stm6, Stm6 =< 75, Anm6 =< 18
        }.
     
       allpos([]).
       allpos([X|Xs]) :- {X >= 0}, allpos(Xs).

We can first check whether the relaxed problem has indeed the quoted infimum:

     clp(r) ?- example(flugpl, Obj, _, _, _), inf(Obj, Inf).
     
     Inf = 1167185.7255923203

Computing the infimum under the additional constraints that Stm6, Stm5, Stm4, Stm3, Stm2, Anm6, Anm5, Anm4, Anm3, Anm2, Anm1 assume integer values at the infimum is computationally harder, but the query does not change much:

     clp(r) ?- example(flugpl, Obj, _, Ints, _),
               bb_inf(Ints, Obj, Inf, Vertex, 0.001).
     
     Inf = 1201500.0000000005,
     Vertex = [75.0,70.0,70.0,60.0,60.0,0.0,12.0,7.0,16.0,6.0,6.0]