Created
September 26, 2023 08:09
-
-
Save Azzaare/659487c2c8a7ae4d60450a5ea5783636 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
### A Pluto.jl notebook ### | |
# v0.19.27 | |
using Markdown | |
using InteractiveUtils | |
# ╔═╡ cb6ecace-da88-4e1f-9821-d01dfb5c8faa | |
begin | |
using Pkg | |
Pkg.add(url="https://github.com/JuliaConstraints/ConstraintCommons.jl.git", rev="bench") | |
Pkg.add(url="https://github.com/JuliaConstraints/ConstraintDomains.jl.git", rev="tostring") | |
Pkg.add(url="https://github.com/JuliaConstraints/Constraints.jl.git", rev="bench") | |
Pkg.add(url="https://github.com/JuliaConstraints/CBLS.jl.git", rev="constraintsup") | |
end; | |
# ╔═╡ 9c9fe073-8f4d-49a3-b42c-926c73c3d8b5 | |
using JuMP, CBLS | |
# ╔═╡ 5b539a26-4d38-11ee-1daf-c39f69bbdcb4 | |
md""" | |
# 第91回 TechTrend Talk Series vol.5 | |
## Straightforward **modeling tools** for prescriptive **decision-making** | |
- 日時: 2023/9/26 (火) 18:00~ | |
- 場所: IIJ本社 13階 Cantata | |
- 話者: Jean-Francois Baffier | |
- 概要: Decision-making processes are generally either prescriptive (Optimization) or predictive (Machine Learning). Both approaches, sometimes combined, apply efficiently to different sets of problems. This talk will highlight the typical cases to use one or the other. We will present our optimization framework to model-as-you-speak and solve problems through general and industrial problems such as (scheduling, Sudoku, etc.). | |
--- | |
""" | |
# ╔═╡ 3c7898fd-3f36-49b7-b996-b3f50ace25c6 | |
md""" | |
### Quadratic Assignement Problem (QAP) | |
qap(n, weigths, distances) | |
Modelize an instance of the Quadractic Assignment Problem with | |
- `n`: number of both facilities and locations | |
- `weights`: `Matrix` of the weights of each pair of facilities | |
- `distances`: `Matrix` of distances between locations | |
###### From Wikipedia | |
There are a set of `n` facilities and a set of `n` locations. For each pair of locations, a distance is specified and for each pair of facilities a `weight` or flow is specified (e.g., the amount of supplies transported between the two facilities). The problem is to assign all facilities to different locations with the goal of minimizing the sum of the `distances` multiplied by the corresponding flows. | |
"""; | |
# ╔═╡ d887643e-f46a-4607-a2e5-50a80d0b28dc | |
md""" | |
```julia | |
using JuMP, CBLS | |
function golomb(n, L) | |
m = JuMP.Model(CBLS.Optimizer) | |
@variable(m, 0 ≤ X[1:n] ≤ L, Int) | |
@constraint(m, X in AllDifferent()) # different marks | |
# No two pairs have the same length | |
for i in 1:(n - 1), j in (i + 1):n, k in i:(n - 1), l in (k + 1):n | |
(i, j) < (k, l) || continue | |
@constraint(m, [X[i], X[j], X[k], X[l]] in DistDifferent()) | |
end | |
# Add objective | |
@objective(m, Min, ScalarFunction(maximum)) | |
return m, X | |
end | |
``` | |
"""; | |
# ╔═╡ 06ee64d5-5623-4ff5-91cb-84b04f76bf30 | |
md""" | |
## Golomb Ruler | |
""" | |
# ╔═╡ 098783be-dc6c-4f3e-ac0a-f611e0e4721d | |
function golomb(n, L=n^2) | |
m = JuMP.Model(CBLS.Optimizer) | |
@variable(m, 0 ≤ X[1:n] ≤ L, Int) | |
@constraint(m, X in AllDifferent()) # different marks | |
@constraint(m, X in Ordered()) # for output convenience, keep them ordered | |
# No two pairs have the same length | |
for i in 1:(n - 1), j in (i + 1):n, k in i:(n - 1), l in (k + 1):n | |
(i, j) < (k, l) || continue | |
@constraint(m, [X[i], X[j], X[k], X[l]] in DistDifferent()) | |
end | |
return m, X | |
end | |
# ╔═╡ cea5a60c-57eb-43f0-bbc5-bddf5435ac26 | |
begin | |
m, X = golomb(4,6) | |
optimize!(m) | |
value.(X) | |
end | |
# ╔═╡ 6ea0272e-4c5d-4dfe-bcb4-3a0668d9b4e1 | |
md""" | |
## Sudoku | |
""" | |
# ╔═╡ 1ff31204-8c8b-4f76-b285-c63b09a76bd2 | |
function sudoku(n, start=nothing) | |
N = n^2 | |
m = JuMP.Model(CBLS.Optimizer) | |
@variable(m, 1 ≤ X[1:N, 1:N] ≤ N, Int) | |
if !isnothing(start) | |
for i in 1:N, j in 1:N | |
v_ij = start[i,j] | |
if 1 ≤ v_ij ≤ N | |
@constraint(m, X[i,j] == v_ij) | |
end | |
end | |
end | |
for i in 1:N | |
@constraint(m, X[i,:] in AllDifferent()) # rows | |
@constraint(m, X[:,i] in AllDifferent()) # columns | |
end | |
for i in 0:(n-1), j in 0:(n-1) | |
@constraint(m, vec(X[(i*n+1):(n*(i+1)), (j*n+1):(n*(j+1))]) in AllDifferent()) # blocks | |
end | |
return m, X | |
end | |
# ╔═╡ 2355b051-aea4-4c3f-867d-89c2229add3d | |
begin | |
m2, X2 = sudoku(2) | |
optimize!(m2) | |
map(Int, value.(X2)) | |
end | |
# ╔═╡ 64be03f7-6f1a-4926-9478-c5562b4ca005 | |
# ╔═╡ b62b7a89-0328-4204-be46-0a94b932d4ea | |
function magic_square(n) | |
N = n^2 | |
model = JuMP.Model(CBLS.Optimizer) | |
magic_constant = n * (N + 1) / 2 | |
@variable(model, 1 ≤ X[1:n, 1:n] ≤ N, Int) | |
@constraint(model, vec(X) in AllDifferent()) | |
for i in 1:n | |
@constraint(model, X[i,:] in SumEqualParam(magic_constant)) | |
@constraint(model, X[:,i] in SumEqualParam(magic_constant)) | |
end | |
@constraint(model, [X[i,i] for i in 1:n] in SumEqualParam(magic_constant)) | |
@constraint(model, [X[i,n + 1 - i] for i in 1:n] in SumEqualParam(magic_constant)) | |
return model, X | |
end | |
# ╔═╡ c87a912a-67b9-4414-b600-095484af27f5 | |
begin | |
m3, X3 = magic_square(3) | |
optimize!(m3) | |
map(Int, value.(X3)) | |
end | |
# ╔═╡ 6f29b920-5057-443e-8010-49d8a93c09eb | |
md""" | |
## Usual Constraints | |
""" | |
# ╔═╡ Cell order: | |
# ╟─5b539a26-4d38-11ee-1daf-c39f69bbdcb4 | |
# ╟─3c7898fd-3f36-49b7-b996-b3f50ace25c6 | |
# ╟─d887643e-f46a-4607-a2e5-50a80d0b28dc | |
# ╟─cb6ecace-da88-4e1f-9821-d01dfb5c8faa | |
# ╠═9c9fe073-8f4d-49a3-b42c-926c73c3d8b5 | |
# ╟─06ee64d5-5623-4ff5-91cb-84b04f76bf30 | |
# ╠═098783be-dc6c-4f3e-ac0a-f611e0e4721d | |
# ╠═cea5a60c-57eb-43f0-bbc5-bddf5435ac26 | |
# ╟─6ea0272e-4c5d-4dfe-bcb4-3a0668d9b4e1 | |
# ╠═1ff31204-8c8b-4f76-b285-c63b09a76bd2 | |
# ╠═2355b051-aea4-4c3f-867d-89c2229add3d | |
# ╠═64be03f7-6f1a-4926-9478-c5562b4ca005 | |
# ╠═b62b7a89-0328-4204-be46-0a94b932d4ea | |
# ╠═c87a912a-67b9-4414-b600-095484af27f5 | |
# ╟─6f29b920-5057-443e-8010-49d8a93c09eb |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment