4th Integer Programming

• Any optimization software, including Excel’s Solver, typically has a much harder time solving an IP problem than an LP problem

-> Therefore LP Relaxation: Integer constraint gets removed, this gives us the upper bound of the integer optimal solution

-> Maximization: rounding down

-> Minimization rounding up

• 100 binary chaning cells 2^100 feasible solutions, many from them not satusfying the constraint

  -> complete enumeration naive method of testing all solutions and selecting the best is usually impractical

• Implicit enumeration, inly examines a fraction of all 2^100 potential solutions, guarantess that all solutions that are not examined have no chance of being optimal

• Idea: systematic search through the set of all feasible integer solutions, creating branches, subsets or solutions as it goes

2.7s is chosen because it’s fractional value 0.73 is larger than 0.59

= the best feasible integer solution found so far

During Maximization:

• The incumbent gives a lower bound on the true optimal value.

• Because the true optimum cannot be worse than the best solution found so far.

Upper bound = comes from LP relaxation

• Solve the LP relaxation (ignore integer restrictions).

• The LP optimum is an upper bound for a maximization problem.

➡ Because allowing fractional values can only make the solution better or equal than requiring integers.

Tolerance: Allowed % Gap between upper bound and incubent