Explore the theory, software, and impact of HiGHS (High Performance Software for Linear Optimization) in this 55-minute lecture by Julian Hall from the University of Edinburgh. Delve into optimization techniques, including primal and dual simplex algorithms, hyper-sparsity, and parallel solution methods for structured and general linear programming problems. Learn about the HiGHS team, solver capabilities, and practical applications in linear programming. Examine optimality conditions, computational aspects of the simplex method, and the effectiveness of various approaches. Discover the performance of HiGHS in simplex, interior point, and mixed-integer programming scenarios, gaining insights into state-of-the-art optimization software and its real-world impact.
Overview
Syllabus
Intro
HIGHS: The team
HIGHS: Solvers
Practical LP problems
Solving primal LP problems: Optimality conditions
Solving dual LP problems: Optimality conditions
Dual simplex algorithm: Choose a row
Dual simplex algorithm: Choose a column
Dual simplex algorithm: Data required
Solving LP problems: Primal or dual simplex?
Simplex method: Computation
Hyper-sparsity: Solve Bx=r for sparser
Hyper-sparsity: Inverse of a sparse matrix
Hyper-sparsity: Solving Lx = b
Hyper-sparsity: Other components
Hyper-sparsity: Effectiveness
Parallel solution of structured LP problems
Parallel solution of stochastic MIP problems
PIPS-S: Exploiting problem structure
PIPS-S: Overview
PIPS-S: Results
Parallel solution of general LP problems via multiple iterations
pani: Effectiveness
HiGHS: Performance
HiGHS: Simplex performance
HiGHS: Interior point performance
HIGHS: MIP performance
Taught by
Fields Institute
