Let our optima combine!
summary
Shows how to model real combinatorial problems in Python using OR-Tools CP-SAT, with concrete code: 27 integer cell variables, 27×22 Booleans and channeling booleans constraints, allowed-assignment tables, and symmetry breaking by fixing letters. Claims orders-of-magnitude speedups over hand‑coded heuristics, demonstrates maximizing an objective (maximize the minimum score), finds optimum in minutes and then enumerates all optimal solutions via model.clear_objective and enumeration, and shares a runnable Colab with the exact word lists and solver settings.
AI-written summary · about
chapters (16)
- 0:00Introduction
- 0:43What is combinatorial optimization
- 3:15OR-Tools CP-SAT solver
- 5:03Why choose CP-SAT
- 8:20Combinatorial optimization examples
- 8:413D Hebrew pangram challenge
- 13:17Modeling pangram in CP-SAT
- 17:14Objective and solving model
- 20:30Hebrew word list prep
- 21:13Variables and constraints in code
- 23:45Feasibility and optimization
- 24:48Finding all optimal solutions
- 26:33Visualizing and sharing results
- 26:53Alternative solvers and tools
- 27:57Advanced research directions
- 28:40Q&A
related talks
29mLet our optima combine!
01h 04mBuilding AI Solutions with Google OR-Tools
10mSATisfying answers to difficult questions!
20mFunction synthesis for maximizing model counting
21mCombinatorial Optimization of Train Timetable Fulfilment After Incidents
17mSynthesizing MILP Constraints for Efficient and Robust Optimization
01h 30mHow To Write a Rubik’s Cube Solver
33mA Hands-On Introduction To Multi-Objective Optimization