第 91 回 TechTrend Talk Series vol.5
Straightforward modeling tools for prescriptive decision-making

Jean-François BaffierInternet Initiative Japan
Research Lab
September 26th , 2023

1 Outline|1

1Introduction

2

Satisfaction Problems

3

Optimization Problems

4Free-time & Conclusion

Introduction

Satisfaction Problems

Optimization Problems

Free-time & Conclusion

1 Decision-Making and Optimality (history-ish)““|2””[…] the principles of mathematics were the principles of all things.
Aristotle, Metaphysics, 350 BCE
Light travels between points through the path of shortest length.
Heron of Alexandria, (10-75) CE

Honeycomb Conjecture Theorem
A regular hexagonal grid or honeycomb has the least
total perimeter of any subdivision of the plane into
regions of equal area.
It was proven by T.C. Hales in 1999.
Nature optimizes! But slowly, over numerous iterations,through a trial and error process.

Introduction

Satisfaction Problems

Optimization Problems

Figure: Worker Bees On
Honeycomb – Jean Beaufort
Free-time & Conclusion

1 Overview of a Decision-Making process

Introduction

Satisfaction Problems|3

Optimization Problems

Free-time & Conclusion

1 Alisu and BobIntroduction|4

Satisfaction Problems

Optimization Problems

Free-time & Conclusion

1 Prescriptive vs. Descriptive approaches|5

Prescriptive Approach (e.g. Optimization)
I Focus: Determining the best course of action.
I Primary Tool: Mathematical models.
I Objective: Optimize a specific criterion.
I Example: Efficient resource allocation, route optimization.
Predictive Approach (e.g. Machine Learning)
I Focus: Making informed predictions based on data.
I Primary Tool: Machine learning models.
I Objective: Predict future outcomes or classify data.
I Example: Predicting customer behavior, image recognition.
Introduction

Satisfaction Problems

Optimization Problems

Free-time & Conclusion

1 Complementary Nature|6Coexistence
I Prescriptive and Predictive approaches are not mutually exclusive.
I Often complement each other for holistic decision-making.
Synergy
I Optimization can use insights from predictive models.
I Machine Learning (predictive models) can use optimization to improve
performance. (This is a very hot topic in AI)

I Some problems benefit from both approaches (hybrid models).
I Example: Using predictive analytics for demand forecasting and optimization for
inventory management.
IntroductionSatisfaction Problems

Optimization Problems

Free-time & Conclusion

1 When to Use Prescriptive and Predictive Approaches
1|7Consider Problem Characteristics>

Complexity:>

Data-Driven:- Use Prescriptive (Optimization) for complex decision-making problems where finding the best solution is critical.

2- Employ Predictive (Machine Learning) when historical data is abundant and patterns need to be extracted.
Data Availability and Quality>

Data Availability:>

Data Quality:- If extensive data is accessible, consider Predictive approaches to leverage it.

- Ensure data quality; inaccurate data can lead to flawed predictions.
3 Decision Urgency>

Immediate Decisions:>

Future Planning:- Use Prescriptive approaches for real-time or critical decisions with little room for error.

- Predictive approaches are valuable for long-term planning and trend analysis.
4 Objective Types>

Objective Clarity:>

Objective Uncertainty:- When objectives are well-defined and measurable, Prescriptive methods are suitable.
- For objectives that are uncertain or evolving, Predictive approaches may be more adaptable.

Introduction

Satisfaction Problems

Optimization Problems

Free-time & Conclusion

2 Outline|81

Introduction

2Satisfaction Problems

3

Optimization Problems

4Free-time & Conclusion

Introduction

Satisfaction Problems

Optimization Problems

Free-time & Conclusion

2 Simple and fun: Sudoku|9A simple variant of prescriptive problems are Satisfaction Problems. They are a class ofproblems where the goal is to find a solution that satisfies a set of constraints. Let us
consider the following example: Sudoku.

Sudoku rules
I Each row, column and 3x3 subgrid
must contain the numbers 1 to 9.
I Each number can only appear once ineach row, column and subgrid.
Some numbers are already given as clues.

Figure: a Sudoku layout generated
by the GNU program Su Doku Solver– Lawrence Leonard Gilbert

Introduction

Satisfaction Problems

Optimization Problems

Free-time & Conclusion

2 Simple and fun: Sudoku|9A simple variant of prescriptive problems are Satisfaction Problems. They are a class ofproblems where the goal is to find a solution that satisfies a set of constraints. Let us
consider the following example: Sudoku.

Figure: a Sudoku layout generated
by the GNU program Su Doku Solver– Lawrence Leonard Gilbert

Introduction

Satisfaction Problems

Optimization Problems

Free-time & Conclusion

2 A bit of magic: Magic Square| 10Now, let us consider a classical mathematical problem called Magic Square (Japan hasa strong history of solving Magic Square throughout history).

Magic Square rules
I Each number can only appear once.
I The sum of each row, column anddiagonal must be equal.
Size 3 × 3 is the minimal non-trivial
instance.

Introduction

Satisfaction Problems

Figure: a 3 × 3 Magic Squareinstance with magic number 15 –Sam Ley (Phidauex)

Optimization ProblemsFree-time & Conclusion

2 A bit of magic: Magic Square| 10Now, let us consider a classical mathematical problem called Magic Square (Japan hasa strong history of solving Magic Square throughout history).

Figure: a 3 × 3 Magic Squareinstance with magic number 15 –Sam Ley (Phidauex)

Introduction

Satisfaction Problems

Optimization Problems

Free-time & Conclusion

3 Outline| 11

1Introduction

2

Satisfaction Problems

3

Optimization Problems

4Free-time & Conclusion

Introduction

Satisfaction Problems

Optimization Problems

Free-time & Conclusion

3 A problem to rule them all: Golomb Ruler| 12

A more advanced variant of prescriptive problems are Optimization Problems. They area class of problems where the goal is to find a solution that optimizes a specificcriterion. Let us consider the following example: Golomb Ruler.
Golomg Ruler description
I Given n marks, each pair of marks has
a different distance.
I The objective is to minimize the size ofthe ruler, i.e. the distance between thefirst and last marks.
A perfect Golomb Ruler is a Golomb Ruler
with the smallest possible size.

Introduction

Satisfaction Problems

Figure: a perfect Golomb ruler with
4 marks – Khrishna Vedala

Optimization Problems

Free-time & Conclusion

3 A problem to rule them all: Golomb Ruler| 12

A more advanced variant of prescriptive problems are Optimization Problems. They area class of problems where the goal is to find a solution that optimizes a specificcriterion. Let us consider the following example: Golomb Ruler.

Figure: a perfect Golomb ruler with
4 marks – Khrishna Vedala

Introduction

Satisfaction Problems

Optimization Problems

Free-time & Conclusion

3 A personal favorite: Network flow problems

Introduction

Satisfaction Problems

Optimization Problems| 13Free-time & Conclusion

3 A personal favorite: Network flow problems| 13

Maximum Flow problem
2s22

2/24t4

s

4/4

2/2
2/2t
2/4

I Amount of flow (data/matter/anything) from a source s to a sink t
I Introduces in 1952 to study the soviet railway system
I Applications to various fields of research, among others:>>>

Scheduling problems: course scheduling, task scheduling, transports …
Matching problems: colors, pair of individuals, …
Image Segmentation

I Can be solved efficiently (tractable ∼ polynomial algorithm)

Introduction

Satisfaction Problems

Optimization Problems

Free-time & Conclusion

3 Network Interdiction problems| 14Classical max-flow
2s22

Introduction

2/2

4
t4

Satisfaction Problems

s

4/4

2/2
2/2

Optimization Problemst
2/4

Free-time & Conclusion

3 Network Interdiction problems| 14Classical max-flow2s22

Introduction

2/2(4)

t4

Satisfaction Problems

s

4/4

2/2
2/2

Optimization Problemst
2/4

Free-time & Conclusion

3 Network Interdiction problems| 14Classical max-flow22s

2/2(4)
st

2/2
2/2

42

4/4t2/4

Network Interdiction
2/2
s

2/2
0/2

Introduction

0/4
t
4/4

Satisfaction Problems

Optimization Problems

Free-time & Conclusion

3 Network Interdiction problems| 14Classical max-flow
22s

2/2(4)

Introduction

0/4

2/2
0/2

2/4

Adaptive Network Flow

Network Interdiction
st

2/2

42

2/2

2/2

s

t

4/4

2/2
t

4/4

Satisfaction Problems

s

3/4

2/2
2/2

Optimization Problemst
3/4

Free-time & Conclusion

3 Specialist approach for Adaptive FlowPf (e)(1 − µ(e))
 maxf ,µe∈Ef ∈Fµ ∈ argmin max

f0µ










P| 15f 0 (s, i)(s,i)∈E

f 0 (e)P 6 0f (e)(1 − µ(e)),
P for0 all e ∈ Ef ((i, j)) −f ((j, k)) = 0,i:(i,j)∈E

k:(j,k)∈E

for all j ∈ V \ {s, t}f (e) > 0, for all e ∈ E.
















I Upper level is classical max flow problem with an objective function variation coming from theattacked links

I Lower Level is a Network Interdiction problem on a given flow

Introduction

Satisfaction Problems

Optimization Problems

Free-time & Conclusion

3 Specialist approach for Adaptive Flowmaxf

P| 15(f (e)δij − f (e)νij )e∈Ef ∈Fδ, ν, µ ∈ minµ,δ,σP(f (e)δij − f (e)νij )e∈E

δij + σj − σi > 0,
δsj + σj > 1,
δit − σi > 0,
δij > 0,
νij 6 µ((i, j)),νij 6 δij ,νP
ij > 0,µ(e) = ke∈Eµ(e) ∈ {0, 1},

Introduction

Satisfaction Problems

for all (i, j) ∈ E, i 6= s, j 6= tfor all j such that (s, j) ∈ E
for all i such that (t, i) ∈ E
for all (i, j) ∈ E
for all (i, j) ∈ E
for all (i, j) ∈ Efor all (i, j) ∈ E
for all (i, j) ∈ E

Optimization Problems







(1) (2) 

(3)
(4) 


(5) (6) (7) (8) 
(9)

Free-time & Conclusion

3 A simpler model| 16The maximum network flow problem is a dual case of the minimum cut problem. It isalso true for the interdiction version.

Figure: a mincut example

Here the model is much simpler, but the problem is still NP-hard. So we look for goodenough solutions.

Introduction

Satisfaction Problems

Optimization Problems

Free-time & Conclusion

4 Outline

| 17

1

Introduction

2

Satisfaction Problems

3

Optimization Problems

4Free-time & Conclusion

Introduction

Satisfaction Problems

Optimization Problems

Free-time & Conclusion

4 Conclusion| 18

Most specialists of a field cannot do the following:I Iterates over billions of years such as natural processes
I Write complex mathematical models that requires weeks of work for a scientist
specialized in Optimization
I Fine-tune decision-making software to be able to make decisions in real-time
Model-as-you-speak framework
We propose a model-as-you-speak framework that allows non-specialists to solve
complex decision-making problems.
We take care of the solving part, you can take care of making models of you field
specialties!

Introduction

Satisfaction Problems

Optimization Problems

Free-time & Conclusion

4 Support you from the shadows| 19

Sudoku 16×16
naive
automatedsemi-autostate-of-the-art

time (seconds)

101

100

10− 1

10− 2

Introduction

Satisfaction Problems

Optimization Problems

Free-time & Conclusion

4 Framework| 20

Our model-as-you-speak framework is available on GitHub
https://github.com/JuliaConstraints/LocalSearchSolvers.jl

I The framework is based on the JuMP (Julia forMathematical Programming) ecosystem
I Works natively with multithreaded and distributed
computing
I Can be used with any solver supported by JuMP
(and we add more solvers every day … or monthmaybe)

Introduction

Satisfaction Problems

Optimization Problems

Free-time & Conclusion

4 Try 1Introduction| 21

Satisfaction Problems

Optimization Problems

Free-time & Conclusion

4 Try 2

Introduction| 22

Satisfaction Problems

Optimization Problems

Free-time & Conclusion

4 Try 3

Introduction| 23

Satisfaction Problems

Optimization Problems

Free-time & Conclusion

4 Try 4 (really?)

Introduction| 24

Satisfaction Problems

Optimization Problems

Free-time & Conclusion