YoVDO

HiGHS - Theory, Software and Impact

Offered By: Fields Institute via YouTube

Tags

Linear Programming Courses Simplex Method Courses Parallel Computing Courses

Course Description

Overview

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.

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

Related Courses

Linear and Discrete Optimization
École Polytechnique Fédérale de Lausanne via Coursera
FA19: Deterministic Optimization
Georgia Institute of Technology via edX
Automated Reasoning: satisfiability
EIT Digital via Coursera
Operations Research: an Active Learning Approach
Hong Kong Polytechnic University via edX
Operations Research (2): Optimization Algorithms
National Taiwan University via Coursera