Optimization Algorithms & Tools for AI
Basic Information
Topics
Many complex systems, ranging from social, industrial, economics, financial, educational, to military, require that we obtain high-quality solutions to combinatorial problems. Linear programming and its extensions developed in operations research once formed the primary paradigm for solving combinatorial problems. During the last three decades, a plethora of paradigms have been developed for combinatorial problems, including constraint programming (CP), propositional satisfiability testing (SAT), satisfiability modulo theories (SMT), and answer set programming (ASP). Search algorithms, which play an important role in traditional symbolic AI, find solutions to problems by exploring and navigating through complex knowledge spaces. Search algorithms are still indispensable in the current development of neuro-symbolic AI that aims for more sophisticated, flexible, and explainable AI systems.
This course covers some of the basic optimization algorithms, including the Simplex, branch-and-bound, and cutting-plane algorithms for Mixed Integer Programming (MIP), the DPLL and CDCL algorithms for Satisfiability (SAT), and various kinds of propagation algorithms for Constraint Programming (CP). This course also covers several optimization tools and many constraint satisfaction and optimization problems.
References
- Introduction to Operations Research by Frederick S. Hillier and Gerald J. Lieberman
- Handbook of Satisfiability, eds., by Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh
- Handbook of Constraint Programming, eds., by Francesca Rossi, Peter van Beek, Toby Walsh.
- Constraint Solving and Planning with Picat, by Neng-Fa Zhou, Hakan Kjellerstrand, and Jonathan Fruhman.
Homework
Exams and Grading
Course Outline and Homework Assignments
- Introduction
- Overview of optimization problems
- Types of optimization problems
- Optimization problems in AI applications
- Highlights of various solving methods
- Linear Programming (LP)
- Introduction to LP
- Formulation of LP problems
- Simplex method for solving LP problems
- Mixed Integer Programming (MIP)
- Basics of integer programming (IP)
- Formulation of IP problems
- Branch and bound algorithm
- Cutting plane methods
- Linearization of non-linear constraints
- Constraint Programming (CP)
- Satisfiability (SAT)
- Optimization Tools
- Picat, or-tools, MiniZinc
- Gurobi, CPLEX, SCIP, CBC, GLPK, HiGHS...
- Tools in Julia and Python
- Final Project Presentation and Review