Let our optima�combine!

Dr. Eyal Gruss

Dr. Eyal Gruss

�ML R&D @freelance��Code // media // text artist��Teaching computational creativity @HIT

�eyalgruss.com eyalgruss@gmail.com

Combinatorial optimization

​

assignment, arrangement, with:

Discrete variables

Constraints

Objective functions

Many combinations

Problems like selection, matching,

(approx.)

(global)

(optional)

(too)

Problem types and examples

• Constraint satisfaction
• Boolean proposition satisfiability�_Puzzles:
• Crossword / Sudoku
• Crypto-arithmetics
• Eight queens�_Real-world:
• Software dependencies
• Type inference
• Wedding seating

Problem types and examples

• Constraint satisfaction
• Boolean proposition satisfiability�_Puzzles:
• Crossword / Sudoku
• Crypto-arithmetics
• Eight queens�_Real-world:
• Software dependencies
• Type inference
• Wedding seating

• Packing / Covering
• Asset allocation�
• Scheduling
• Employee shifts
• Job shop
• School timetable�
• Routing / Network flow ^{(but use a dedicated solver)}
• Traveling salesperson

OR-Tools

Google's Operations Research open-source software

CP-SAT solver

Constraint Programming - Satisfiability

Order encoding

CP-SAT reformulates problem as a logic problem:

Integer variables => Boolean variables

i in [1, 2, 3] is_i_eq_1,

is_i_eq_2, is_i_leq_2

is_i_eq_3, is_i_leq_3

​

This is done automatically and lazily

Why CP-SAT?

• Heuristic optimization
• Doesn't assure finding all / best solutions, and doesn't inform you if it has�
• Exhaustive search with handcrafted optimizations
• Requires per-domain optimization crafting which is hard and error-prone
• More complex and error-prone code
• Slow

Why CP-SAT?

• CP-SAT exhausts the search space with branch and bound / cut optimization
• Assurances on best / all solutions
• Generic optimization requiring less handcrafting
• Simpler code
• 10-100x faster�
• But, you need to learn a new declarative programing paradigm, and accept it's strict and more verbose formulation (and modeling still requires expertise)

Usage patterns

1. Find a solution / whether a solution exists (feasibility)
2. Find all solutions (if not too many)
3. Find a solution optimizing an objective (and the optimal objective value)
4. Find all solutions optimizing an objective
1. In OR-Tools we do: C, then constrain the optimal value, then B (Multi-objective works similarly)
2. If there aren't too many solutions without (or with partial) objectives, it may be easier to find them all, then filter in post-process to find the optimal solutions for the remaining objectives

Can any form

(diamond, pyramid)

contain all 26 27 letters?

Word Ways challenge from 1979

_{Philip Cohen and Ross Eckler}

3D perfect pangram

Perfect pangram = text where each letter of the alphabet appears exactly once

​

Hebrew has 22 letters + 5 final forms = 27

​

Idea: Put letters in a 3x3x3 cube to form 27 words, 9 in each of x, y, z dimensions

​

It's impossible to have all (non-)final forms at their place, so we allow interchange

Combinatorial explosion

Letter permutations:

27! / 2⁵ = 3.4 * 10²⁶

​

Word combinations:

9 of 2000 = 2000 * 1999 * ... * 1991 = 5 * 10²⁹

​

Exhaustive search is intractable (>> age of universe)

Symmetries are bad (redundant solutions)

Even after we fix the axis system we still have this rotational symmetry left

Symmetry breaking (eliminating redundant solutions)

Take one specific letter that is most likely not to be in the middle of words��We can break part of the symmetry by constraining allowed placements to 10 unique index combinations

x,y,z

0,0,0

1,0,0

2,0,0

1,1,0

1,1,1

2,1,1

2,2,0

2,2,2

2,2,1

2,1,0

x

y

z

Problem representation

27 integer variables for the cells with unicode values of the letters:

flat[i] = cells[(x, y, z)] = model.new_int_var(ord('א'), ord('ת'), f'cells_{x}_{y}_{z}')

^{(two references to the same variable)}

27 * 22 boolean variables indicating if the cell contains the letter (for counting):

is_char[c][i] = model.new_bool_var(f'is_char_{c}_{i}')

​

Integer and booleans variables linked with if-and-only-if constraints (channeling):

model.add(flat[i] == ord(c)).only_enforce_if(is_char[c][i])��model.add(flat[i] != ord(c)).only_enforce_if(~is_char[c][i])

Constraints

Each letter appears exactly once, except those with final forms that appear twice:

model.add(sum(is_char[c]) == allowed_count[c])��All 27 formed words must exist in our vocabulary, and have their popularity scores:

scores[n] = model.new_int_var(min(score_values), max(score_values), f'scores_{n}')��model.add_allowed_assignments([cells[(0, i, j)], cells[(1, i, j)], cells[(2, i, j)],�� scores[n]], list_of_allowed_words_and_their_scores) ...��Additionally, let's have one of the middle words be a sweetheart's name - for the sake of love, symmetry breaking and faster computation:

model.add(cells[(0, 1, 1)] == ord('י')) ...

Objective and solving

Maximize the popularity score of the least popular word used:

worst = model.new_int_var(min(score_values), max(score_values), 'worst')

model.add_min_equality(worst, scores)

model.maximize(worst)

solver.solve(model)

​

To find all optimal solutions, we clear the objective and add it as a constraint:

model.clear_objective()

model.add(worst == round(solver.objective_value))

solver.parameters.enumerate_all_solutions = True

solver.solve(model, solution_collector_callback)

Colab tutorial

Make your own: tfi.la/or

Write-up: tfi.la/c/pan3d

OR-Tools CP-SAT References

https://github.com/or-tools/awesome_or-tools

https://d-krupke.github.io/cpsat-primer/

https://xiang.es/posts/cp-sat/

http://www.hakank.org/or-tools/

https://github.com/google/or-tools/tree/stable/ortools/sat/samples/

https://github.com/google/or-tools/tree/stable/examples/

https://groups.google.com/g/or-tools-discuss

https://discord.gg/ENkQrdf

Other free CP-SAT solvers with Python interface

• I tried but OR-Tools was faster:
• Microsoft Z3
• pySMT
• python-constraint (pure python = slow)�
• Didn't try :
• PySCIPOpt (SCIP)
• PySAT
• Conda pycosat (PicoSAT)

Modeling languages and wrappers in Python

• MiniZinc (not Python but has bindings; also has a free online playground)
• COIN-OR Pyomo
• CPMpy (works with NumPy)
• OR-Tools new MathOpt (Python or free API)
• OR-Tools MPSolver and the newer MPModelRequest (LP/MIP)
• COIN-OR PuLP (LP/MIP)

Free dedicated solvers for Scheduling / Routing / Net-Flow

• Concorde (#1 for large pure TSP; not python)
• OR-Tools RoutingModel
• OR-Tools max-flow, min-cost-flow
• Google Direction API and the newer Routes API (real-world TSP)
• OR-Tools new Workforce Scheduling API and Shipping Network Design API
• OptaPy (OptaPlanner)
• PyVRP

Interesting research frontiers

Automatic constraint acquisition from positive / negative examples

https://github.com/CPMpy/PyConA

​

Explainability and finding minimal unsatisfiable / correction subsets

https://github.com/CPMpy/XCP-explain

​

LLM stuff? Early attempts trying to extract constraints or reason about them

Thanks!

eyalgruss@gmail.com

Petri-net layout optimization (multi-objective)

Arrange 20 nodes in a grid with dimensions 4x5

There are 20! = 2.4 * 10¹⁸ possible permutations

Business problem: Arrows (edges) drawn as ASCII art, so they need to be short...

Constrain connected nodes to relative positions: 0x1, 1x0, 1x1, 1x2, 2x1, 1x3, 3x1

Objective 1: Maximize number of 0x1, 1x0 edges

Objective 2: For the above optimum, minimize number of 1x3, 3x1 edges

Objective 3: For the above optimum, maximize number 1x1 edges