Maximizing Over a Knapsack Polytope

Finally, let us solve the problem ``cuww1'' [2,5]. Its description is given in the file ``EXAMPLES/cuww1'':

1 6
89643482 -12223 -12224 -36674 -61119 -85569
linearity 1 1
nonnegative 5 1 2 3 4 5

The cost function can be found in the file ``EXAMPLES/cuww1.cost'':

1 5
213 -1928 -11111 -2345 9123

Now let us maximize this cost function over the given knapsack polytope. Note that by default, the digging algorithm as described in [5] is used.

    ./maximize EXAMPLES/cuww1

The last couple of lines that LattE prints to the screen look as follows:

Finished computing a rational function. 
Time: 0.158203 sec.

There is one optimal solution. 		

No digging.
An optimal solution for [213 -1928 -11111 -2345 9123] is: [7334 0 0 0 0].
The projected down opt value is: 191928257104
The optimal value is: 1562142.
The gap is: 7995261.806
Computation done.
Time: 0.203124 sec.

The solution $(7334,0,0,0,0)$ is quickly found. Now let us try to find the optimal value again by a different algorithm, the binary search algorithm.

    ./maximize bbs EXAMPLES/cuww1

The last couple of lines that LattE prints to the screen look as follows:

Total of Iterations: 26
The total number of unimodular cones: 125562
The optimal value: 1562142

The number of optimal solutions: 1
Time: 0.042968

Note that we get the same optimal value, but no optimal solution is provided.