search

d-krupke / cpsat-primer

The CP-SAT Primer: Using and Understanding Google OR-Tools' CP-SAT Solver
https://d-krupke.github.io/cpsat-primer/
Creative Commons Attribution 4.0 International
387 stars 35 forks source link

Add a simple introduction to branch and bound based on Knapsack #10

Closed d-krupke closed 1 year ago

d-krupke commented 1 year ago

Knapsack has a trivial relaxation and thus can be used to explain Branch and Bound without knowledge of Linear Programming. I guess that this would be the best start to explain the fundamentals of nearly all exact solvers. We do this in our bachelor lecture "Algorithms and Datastructure 2"

d-krupke commented 1 year ago

This part is paused for now to focus on the other parts.