Course Details:
An advanced-level series of three classes that include Basic Modeling, Advanced Modeling, and Solving Algorithms for Discrete Optimization. Utilizing constraint programming language MiniZinc, optimal (or near-optimal) solutions were found for NP problems normally too computationally expensive and slow to solve, from banquet seating to packing to traveling saleman problems.
Basic Modeling for Discrete Optimization:
- Learned the basics of MiniZinc, a high-level modeling language for discrete optimization problems, and contraint programming
- Programmed MiniZinc code that finds solutions to the graph coloring, knapsack, production planning, and rostering problems
- Selected most optimized data structures and variables, including booleans, integers, arrays, sets, and enumerated and optional types
- Explored the differences between and optimal scenarios for sets with fixed and bounded cardinality
- Modeled partitions and functions
- Optimized programs by considering discrete optimization problems from different, sometimes more useful, viewpoints
Advanced Modeling for Discrete Optimization:
- Debugged faulty code and learned symptoms of different bugs
- Modularized complex constraints into predicates for easy reusability
- Balanced multiple objectives in solution-finding
- Solved banquet seating problem, many scheduling problem varieties (including disjunctive, cumulative, and sequence-dependent), and the packing problem, from simple squares to complex rectilinear shapes
Solving Algorithms for Discrete Optimization:
- Learned about the underlying solvers that MiniZinc relies on, and how some are better optimized for different problems
- Dived into the guts of constraint programming solvers, learning how domains, bounds, and propagators speed up program execution
- Explored search strategies such as branch, bound, restart, randomized, impact-based, branch and bound, and branch and cut
- Utilized mixed-interger programming
- Efficiently explored complex solution search space with local search and techniques such as restarts, simulated annealing, tabu lists and discrete Lagrange Multipliers
