Descrete Optimization

1 dimension Knapsack problem

Find a way to pack items
defined by their respective value and weight
in a sack of a given capacity so that the total value is as large as possible.

Decision variables

Constraints

Objective function

Recursive naive top-down

assume we know how to compute the best solution for for all ,
we want to solve .

if
otherwise

so we can write a recursive top-down solver:

int O(int k,int j) {
  if (j == 0)
    return 0;
  else if (wj <= k)
    return max(O(k,j-1),vj + O(k-wj,j-1)); // unnecessary exponential groth
  else
    return O(k,j-1)
}

the unnecessary exponential groth computes many times the same
to avoid this we are going to build our solution from the bottom

Dynamic Programming

  • it is a divide and conquer
  • bottom up computation technique

maximize
subject to
domain

k \ i 0  1  2  3  4 
 000000
 100000
 2016161616
 3016191919
 4016192323
 5016353535
 6016353939
 7016354244

this table is easily built from top to bottom, left to right.

for i (1..4) {
   for k (0..7) {
      if ((k >= wi) && (([i-1, (k-Wi)] + vi)> [i-1, k]))
        [i, k] = ([i-1, (k-Wi)] + vi);
      else
        [i, k] = [i-1, k];
   }
}

when done the best value can be read in the bottom right cell.

to find the items, we trace back the algorithme from this bottom right cell.
If it’s value is the same the the cell on the right, the item index i is not taken, move to the cell on the right,
otherwise the intem i is taken, move right and up .
For this particular case, the tracing back goes [ 44 , 16 , 16 , 16 , 0 ] and the items are 1 and 4.

This is a pseudo-polynomyal algorithm, very fast for small values of K, otherwise exponential.

Branch and Bound

  • branching : split the problem into subproblems
  • bounding : use optimistic estimation
    • if we are maximizing an objective function we take the upper bound of this function
    • if we are minimizing an objective function we take the lower bound of this function

Branch-Bound

Relax the capacity constraint

optimistc value is

Linear relaxation

relax the integrality requirement

  • sort the item by the ratio
  • the optimistic value becomes:
    • take the ordered items one by one untill the next one weights more than the capacity
    • fill the capacity with of fraction of the next item

Depth-First Branch-Bound

  • prunes when a node estimation is worst than the best found solution
  • memory efficient

Depth-First Branch-Bound

  • select the node with the best evaluation
  • prunes whem all the nodes are worse than a found solution
  • could be realy not memory efficient

Back to Wisdom entry