# milp — branch-and-bound MILP solver

A small C99 MILP solver demonstrating the branch-and-bound + LP-relaxation
pattern. Originally an annex to *Predictive Algorithms*; now the codebase
backing Chapter 3 of *Practical Solvers*.

About 575 lines for the solver, four worked examples, no dependencies beyond
`libm` and `stdlib`.

## Build

    ./build.zsh

Produces binaries under `build/`:

- `build/sanity` — five LP smoke tests, runs automatically
- `build/ex1_knapsack` — 0/1 knapsack (LP=23.5, MIP=23, gap=0.5)
- `build/ex2_assignment` — assignment, LP already integer (TUM)
- `build/ex3_setcover` — NP-hard set cover, fractional LP bound
- `build/ex4_wta` — budgeted weapon-target assignment

The build script runs the sanity tests and each example after compiling it.

## Layout

    src/milp.h              public API (~80 lines)
    src/milp.c              two-phase simplex + B&B (~495 lines)
    examples/ex*.c          four worked examples
    sanity.c                smoke tests
    build.zsh               build script

## Reading

For the canonical write-up, read **Chapter 3 of *Practical Solvers***
(`../books/practical-solvers/practical-solvers.pdf`).

The original standalone annex is preserved at
`../books/background/milp-annex.{pdf,tex}` for historical reference.

Each example program is self-contained and meant to be read in order:
knapsack, assignment, set cover, WTA. Each one introduces one more thing
the LP relaxation can or cannot do.
