This tutorial was written by Michael Schmitt, a student of the course "Discrete Optimization".
====== Branch & Bound ======
In this Tutorial, I like to describe, how one can implement the Branch & Bound Algorithm for polytopes using polymake.
===== Preamble =====
This preamble must be integrated in every script file, so that we can use the polytope functionalities of polymake.
> use application "polytope";
At first we create some global variables that keep track over the best integer solution, that has been discovered so far.
> declare $z = -10000;
> declare $x_best;
===== Subfunction =====
I introduce a subroutine, that returns the non-integer part of some rational number.
> sub f {
> my $x=shift;
> my $denom = denominator($x);
> my $nom = convert_to($denom * $x);
> my $remainder = $nom % $denom;
> if($remainder < 0){
> $remainder += $denom;
> }
> return new Rational($remainder, $denom);
> }
===== Main routine =====
It follows the main routine, that will call itself recursively. The parameters that are passed to this function are:
* The objective function as an Vector
* A list of inequalities that define the currently examined polytope
> sub branchnbound {
>
>
> # The following line gets the parameters.
>
> my $objective = shift;
> my @ineqs = @_;
>
> my $mat = new Matrix(@ineqs);
> #print "Current Inequalities: \n", $mat, "\n";
>
> my $p = new Polytope;
> $p->INEQUALITIES = $mat;
>
>
> ### Feasibility check
> # Let's check, whether the polytope is empty or not.
> # If it is empty, we can stop examining this branch of the B&B Tree.
>
> if(!$p->FEASIBLE){
> print "EMPTY!\n";
> return;
> }
>
>
> ### Solving the relaxation
> # We look for the optimal solution of the linear relaxation.
>
> $p->LP = new LinearProgram(LINEAR_OBJECTIVE=>$objective);
>
> my $x = $p->LP->MAXIMAL_VERTEX;
> my $ctx = $p->LP->MAXIMAL_VALUE;
>
> print "Relaxed solution: ", $x, " -> ", $ctx,"\n";
>
>
> ### Pruning
> # And if that is already worse then the best integer solution so far,
> # we can prune this branch.
>
> if($ctx <= $z){
> print "is pruned, because <= $z\n";
> return 0;
> }
>
>
> ### Check for integer solution
> # In the following loop, we find the first coordinate of the solution vector,
> # that is not integer.
>
> my $i = 0;
> for(my $k=1; $k<$x->dim(); $k++){
> if(f($x->[$k]) != 0){
> $i = $k;
> }
> }
>
>
> #If we didn't find any, we have found an integer solution and possibly a new best solution.
> #In the case of an integer solution, we can stop here.
>
> if($i == 0){
> print "Solution is Integer.\n";
> # Update the best solution
> if($ctx > $z){
> $x_best = $x;
> $z = $ctx;
> print "Solution is better then the last optimum.\n";
> }
> return;
> }
>
>
> ### Branching
> # Now lets create some new inequalities.
> # At first round the not integer coordinate of x up and down.
>
> #Round up and down:
> my $x_i_down = $x->[$i] - f($x->[$i]);
> my $x_i_up = $x_i_down + 1;
>
>
> # To generate P_1, add the inequality x_i <= x_i_down.
>
> my @ineq_to_add_1 = ($x_i_down);
> for (my $k = 1; $k<$x->dim(); $k++){
> if($k == $i){
> push @ineq_to_add_1, -1;
> }else{
> push @ineq_to_add_1, 0;
> }
> }
>
>
> # To generate P_2, add the inequality x_i >= x_i_up.
>
> my @ineq_to_add_2 = (-$x_i_up);
> for (my $k = 1; $k<$x->dim(); $k++){
> if($k == $i){
> push @ineq_to_add_2, 1;
> }else{
> push @ineq_to_add_2, 0;
> }
> }
>
>
> # Now add the new inequalities to the old ones ...
>
> my @new_ineqs_1 = @ineqs;
> push @new_ineqs_1, \@ineq_to_add_1;
>
> my @new_ineqs_2 = @ineqs;
> push @new_ineqs_2, \@ineq_to_add_2;
>
>
> # And do the recursive calls.
> # Here I added some printouts, that give an inorder traversal of
> # the B&B tree and the edges that are used for that.
>
> print "Set x$i <= $x_i_down\n";
> branchnbound($objective, @new_ineqs_1);
> print "Forget x$i <= $x_i_down\n";
>
> print "Set x$i >= $x_i_up\n";
> branchnbound($objective, @new_ineqs_2);
> print "Forget x$i >= $x_i_up\n";
>
> }
Finally, the first call of the Routine:
> @ineqs = ([14,-7,2],[3,0,-1],[3,-2,2],[0,1,0],[0,0,1]);
> $objective = [0,4,-1];
> branchnbound($objective, @ineqs);
>
> print "The solution is: $x_best with the optimal value $z\n";
Relaxed solution: 1 20/7 3 -> 59/7
Set x1 <= 2
Relaxed solution: 1 2 1/2 -> 15/2
Set x2 <= 0
Relaxed solution: 1 3/2 0 -> 6
Set x1 <= 1
Relaxed solution: 1 1 0 -> 4
Solution is Integer.
Solution is better then the last optimum.
Forget x1 <= 1
Set x1 >= 2
EMPTY!
Forget x1 >= 2
Forget x2 <= 0
Set x2 >= 1
Relaxed solution: 1 2 1 -> 7
Solution is Integer.
Solution is better then the last optimum.
Forget x2 >= 1
Forget x1 <= 2
Set x1 >= 3
EMPTY!
Forget x1 >= 3
The solution is: 1 2 1 with the optimal value 7