Optimization & solvers

Solves linear programs by walking along the edges of the feasible polytope from vertex to vertex, one basis swap (pivot) at a time; the workhorse behind MIP solvers.

Solves LPs with integer variables by solving the LP relaxation, branching on a fractional variable, and pruning subtrees whose LP bound cannot beat the incumbent.

Valid inequalities added to an LP relaxation to cut off its fractional optimum without removing any integer point; the engine of branch-and-cut MIP solvers.

Cheap, provably safe reductions run before the solver (fix variables, drop rows, tighten bounds and coefficients) so LP and MIP solves start from a smaller, tighter model.

Solve a huge LP by keeping only a few columns and pricing new ones from a subproblem until none can improve; gives the Dantzig-Wolfe bound.

Follows the central path with Newton steps on the perturbed KKT system, one sparse Cholesky per iteration; Mehrotra's predictor-corrector makes it fast.

Search for a satisfying assignment, learn a new constraint from every dead end, and jump back past irrelevant choices; handles industrial formulas with millions of clauses.

Unit propagation for SAT that watches just two literals per clause, so backtracking costs nothing and long clauses are rarely touched.

A reduced ordered BDD stores a Boolean function as a shared DAG that is unique per variable order, so equivalence is one integer compare and counting is one pass.

Variables with finite domains, propagators that prune impossible values to a fixpoint, and backtracking search with trail undo between decisions.

Repeatedly remove a chunk of a solution and rebuild it with a heuristic or exact solver; learn which operator pairs pay off.

Keep earliest/latest start and slack per segment so "does this insertion or move keep every window?" costs O(1) instead of a walk down the sequence.

Model jobs as chains of operations, resource order as a choice of arc directions, and minimise the longest path; build with dispatching rules, improve by swapping critical neighbours or solve with CP.

Pack items of given sizes into the fewest fixed-capacity bins; sort descending, then first-fit, gives at most 11/9 of optimal and runs in O(n log n).