-
Notifications
You must be signed in to change notification settings - Fork 27
/
index.html
58 lines (49 loc) · 14.9 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
<!DOCTYPE html>
<html lang="en"><head><meta charset="UTF-8"/><meta name="viewport" content="width=device-width, initial-scale=1.0"/><title>Optimization · Polyhedra</title><link href="https://fonts.googleapis.com/css?family=Lato|Roboto+Mono" rel="stylesheet" type="text/css"/><link href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/5.15.0/css/fontawesome.min.css" rel="stylesheet" type="text/css"/><link href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/5.15.0/css/solid.min.css" rel="stylesheet" type="text/css"/><link href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/5.15.0/css/brands.min.css" rel="stylesheet" type="text/css"/><link href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.11.1/katex.min.css" rel="stylesheet" type="text/css"/><script>documenterBaseURL=".."</script><script src="https://cdnjs.cloudflare.com/ajax/libs/require.js/2.3.6/require.min.js" data-main="../assets/documenter.js"></script><script src="../siteinfo.js"></script><script src="../../versions.js"></script><link class="docs-theme-link" rel="stylesheet" type="text/css" href="../assets/themes/documenter-dark.css" data-theme-name="documenter-dark"/><link class="docs-theme-link" rel="stylesheet" type="text/css" href="../assets/themes/documenter-light.css" data-theme-name="documenter-light" data-theme-primary/><script src="../assets/themeswap.js"></script></head><body><div id="documenter"><nav class="docs-sidebar"><div class="docs-package-name"><span class="docs-autofit">Polyhedra</span></div><form class="docs-search" action="../search/"><input class="docs-search-query" id="documenter-search-query" name="q" type="text" placeholder="Search docs"/></form><ul class="docs-menu"><li><a class="tocitem" href="../">Index</a></li><li><a class="tocitem" href="../installation/">Installation</a></li><li><a class="tocitem" href="../representation/">Representation</a></li><li><a class="tocitem" href="../polyhedron/">Polyhedron</a></li><li><a class="tocitem" href="../plot/">Plot</a></li><li><a class="tocitem" href="../redundancy/">Containment/Redundancy</a></li><li><a class="tocitem" href="../projection/">Projection/Elimination</a></li><li class="is-active"><a class="tocitem" href>Optimization</a><ul class="internal"><li><a class="tocitem" href="#Using-a-polyhedron-for-in-an-optimization-model"><span>Using a polyhedron for in an optimization model</span></a></li><li><a class="tocitem" href="#Creating-a-polyhedron-from-the-feasible-set-of-a-JuMP-model"><span>Creating a polyhedron from the feasible set of a JuMP model</span></a></li></ul></li><li><a class="tocitem" href="../utilities/">Utilities</a></li><li><span class="tocitem">Examples</span><ul><li><a class="tocitem" href="../generated/Convex hull and intersection/">Convex hull and intersection</a></li><li><a class="tocitem" href="../generated/Extended Formulation/">Extended Formulation</a></li><li><a class="tocitem" href="../generated/Minimal Robust Positively Invariant Set/">Minimal Robust Positively Invariant Set</a></li></ul></li></ul><div class="docs-version-selector field has-addons"><div class="control"><span class="docs-label button is-static is-size-7">Version</span></div><div class="docs-selector control is-expanded"><div class="select is-fullwidth is-size-7"><select id="documenter-version-selector"></select></div></div></div></nav><div class="docs-main"><header class="docs-navbar"><nav class="breadcrumb"><ul class="is-hidden-mobile"><li class="is-active"><a href>Optimization</a></li></ul><ul class="is-hidden-tablet"><li class="is-active"><a href>Optimization</a></li></ul></nav><div class="docs-right"><a class="docs-edit-link" href="https://github.com/JuliaPolyhedra/Polyhedra.jl/blob/master/docs/src/optimization.md" title="Edit on GitHub"><span class="docs-icon fab"></span><span class="docs-label is-hidden-touch">Edit on GitHub</span></a><a class="docs-settings-button fas fa-cog" id="documenter-settings-button" href="#" title="Settings"></a><a class="docs-sidebar-button fa fa-bars is-hidden-desktop" id="documenter-sidebar-button" href="#"></a></div></header><article class="content" id="documenter-page"><h1 id="Optimization"><a class="docs-heading-anchor" href="#Optimization">Optimization</a><a id="Optimization-1"></a><a class="docs-heading-anchor-permalink" href="#Optimization" title="Permalink"></a></h1><p>A polyhedron can represents the feasible set of an optimization program. The program is infeasible when the polyhedron is empty.</p><article class="docstring"><header><a class="docstring-binding" id="Base.isempty" href="#Base.isempty"><code>Base.isempty</code></a> — <span class="docstring-category">Function</span></header><section><div><pre><code class="language-julia">isempty(p::Rep, solver=Polyhedra.linear_objective_solver(p))</code></pre><p>Check whether the polyhedron <code>p</code> is empty by using the solver <code>solver</code>.</p></div><a class="docs-sourcelink" target="_blank" href="https://github.com/JuliaPolyhedra/Polyhedra.jl/blob/b59a9f61ab902ef0d5c7d4a96d95fc035af58ac9/src/opt.jl#L177-L181">source</a></section></article><p>If the V-representation of the polyhedron has been computed, it can be used to solve the linear program.</p><article class="docstring"><header><a class="docstring-binding" id="Polyhedra.VRepOptimizer" href="#Polyhedra.VRepOptimizer"><code>Polyhedra.VRepOptimizer</code></a> — <span class="docstring-category">Type</span></header><section><div><pre><code class="language-julia">VRepOptimizer{T} <: AbstractPolyhedraOptimizer{T}</code></pre><p>Linear Programming solver using the V-representation of the feasible set to find the optimal solution.</p></div><a class="docs-sourcelink" target="_blank" href="https://github.com/JuliaPolyhedra/Polyhedra.jl/blob/b59a9f61ab902ef0d5c7d4a96d95fc035af58ac9/src/vrep_optimizer.jl#L3-L8">source</a></section></article><p>Otherwise, any programming solver implementing the <a href="https://github.com/jump-dev/MathOptInterface.jl">MathOptInterface</a> interface can be used. See <a href="http://jump.dev/JuMP.jl/dev/installation/#Getting-Solvers-1">here</a> for a list of available solvers.</p><article class="docstring"><header><a class="docstring-binding" id="Polyhedra.default_solver" href="#Polyhedra.default_solver"><code>Polyhedra.default_solver</code></a> — <span class="docstring-category">Function</span></header><section><div><pre><code class="language-julia">default_solver(p::Rep)</code></pre><p>Returns a default linear programming solver for the polyhedron <code>p</code> (e.g. CDD has an internal solver which is used by default).</p></div><a class="docs-sourcelink" target="_blank" href="https://github.com/JuliaPolyhedra/Polyhedra.jl/blob/b59a9f61ab902ef0d5c7d4a96d95fc035af58ac9/src/default.jl#L72-L76">source</a></section></article><article class="docstring"><header><a class="docstring-binding" id="Polyhedra.linear_objective_solver" href="#Polyhedra.linear_objective_solver"><code>Polyhedra.linear_objective_solver</code></a> — <span class="docstring-category">Function</span></header><section><div><pre><code class="language-julia">linear_objective_solver(p::Rep, solver=default_solver(p))</code></pre><p>Return the solver to use for optimizing a linear objective over the polyhedron <code>p</code>, i.e.</p><pre><code class="language-julia">model = Model(solver)
x = @variable(model, [1:fulldim(p)])
@constraint(model, x in p)
@objective(model, c ⋅ x)</code></pre><p>for some vector <code>c</code>.</p><p>By default, if the V-representation of <code>p</code> has been computed, it returns <code>VRepOptimizer()</code>, otherwise, it returns <code>solver</code>.</p><p>If the problem has constraints different to <code>x in p</code>, use <code>default_solver(p)</code> instead as the fact that the V-representation of <code>p</code> has been computed does not help.</p></div><a class="docs-sourcelink" target="_blank" href="https://github.com/JuliaPolyhedra/Polyhedra.jl/blob/b59a9f61ab902ef0d5c7d4a96d95fc035af58ac9/src/default.jl#L87-L104">source</a></section></article><h2 id="Using-a-polyhedron-for-in-an-optimization-model"><a class="docs-heading-anchor" href="#Using-a-polyhedron-for-in-an-optimization-model">Using a polyhedron for in an optimization model</a><a id="Using-a-polyhedron-for-in-an-optimization-model-1"></a><a class="docs-heading-anchor-permalink" href="#Using-a-polyhedron-for-in-an-optimization-model" title="Permalink"></a></h2><p>A polyhedron or representation can be used in the constraint of a JuMP model. For instance, consider the 1-simplex:</p><pre><code class="language-julia-repl">julia> using Polyhedra
julia> simplex = HalfSpace([-1, 0], 0) ∩ HalfSpace([0, -1], 0) ∩ HyperPlane([1, 1], 1)
H-representation Polyhedra.Intersection{Int64,Array{Int64,1},Int64}:
1-element iterator of HyperPlane{Int64,Array{Int64,1}}:
HyperPlane([1, 1], 1),
2-element iterator of HalfSpace{Int64,Array{Int64,1}}:
HalfSpace([-1, 0], 0)
HalfSpace([0, -1], 0)</code></pre><p>and the following JuMP model with two variables</p><pre><code class="language-julia-repl">julia> using JuMP
julia> model = Model()
A JuMP Model
Feasibility problem with:
Variables: 0
Model mode: AUTOMATIC
CachingOptimizer state: NO_OPTIMIZER
Solver name: No optimizer attached.
julia> @variable(model, λ[1:2])
2-element Array{VariableRef,1}:
λ[1]
λ[2]</code></pre><p>The variables can be constrained to belong to the simplex as follows:</p><pre><code class="language-julia-repl">julia> @constraint(model, λ in simplex)
[λ[1], λ[2]] ∈ Polyhedra.PolyhedraOptSet{Int64,Polyhedra.Intersection{Int64,Array{Int64,1},Int64}}(HyperPlane([1, 1], 1) ∩ HalfSpace([-1, 0], 0) ∩ HalfSpace([0, -1], 0))</code></pre><p>but a vector of affine or quadratic expressions can also be constrained to belong to the simplex:</p><pre><code class="language-julia-repl">julia> A = [1 1
1 -1]
2×2 Array{Int64,2}:
1 1
1 -1
julia> @constraint(model, A * λ in simplex)
[λ[1] + λ[2], λ[1] - λ[2]] ∈ Polyhedra.PolyhedraOptSet{Int64,Polyhedra.Intersection{Int64,Array{Int64,1},Int64}}(HyperPlane([1, 1], 1) ∩ HalfSpace([-1, 0], 0) ∩ HalfSpace([0, -1], 0))</code></pre><p>We can verify that the model contains both constraints:</p><pre><code class="language-julia">julia> model
A JuMP Model
Feasibility problem with:
Variables: 2
`Array{JuMP.VariableRef,1}`-in-`Polyhedra.PolyhedraOptSet{Int64,Polyhedra.Intersection{Int64,Array{Int64,1},Int64}}`: 1 constraint
`Array{JuMP.GenericAffExpr{Float64,JuMP.VariableRef},1}`-in-`Polyhedra.PolyhedraOptSet{Int64,Polyhedra.Intersection{Int64,Array{Int64,1},Int64}}`: 1 constraint
Model mode: AUTOMATIC
CachingOptimizer state: NO_OPTIMIZER
Solver name: No optimizer attached.
Names registered in the model: λ</code></pre><p>When the model is solved, the constraint is automatically transformed into appropriate constraints if the optimizer does not support consraints with the set <code>Polyhedra.PolyhedraOptSet</code>.</p><pre><code class="language-julia">julia> import GLPK
julia> set_optimizer(model, GLPK.Optimizer)
julia> optimize!(model)
julia> termination_status(model)
OPTIMAL::TerminationStatusCode = 1
julia> value.(λ)
2-element Array{Float64,1}:
0.5
0.5</code></pre><p>For instance, GLPK, does not support <code>Polyhedra.PolyhedraOptSet</code> constraints but supports <code>MOI.EqualTo{Float64}</code> and <code>MOI.LessThan{Float64}</code>. The polyhedral constraints are therefore bridged into several <code>MOI.EqualTo{Float64}</code> and <code>MOI.LessThan{Float64}</code> constraints using the following <a href="http://jump.dev/MathOptInterface.jl/stable/apimanual/#Constraint-bridges-1">constraint bridge</a>:</p><article class="docstring"><header><a class="docstring-binding" id="Polyhedra.PolyhedraToLPBridge" href="#Polyhedra.PolyhedraToLPBridge"><code>Polyhedra.PolyhedraToLPBridge</code></a> — <span class="docstring-category">Type</span></header><section><div><pre><code class="language-julia">PolyhedraToLPBridge{T}</code></pre><p>The <code>PolyhedraToLPBridge</code> converts a constraint <code>VF</code>-in-<code>PolyhedraOptSet</code> into the constraints <code>F</code>-in-<code>EqualTo</code> for the hyperplanes and <code>F</code>-to-<code>LessThan</code> for halfspaces.</p></div><a class="docs-sourcelink" target="_blank" href="https://github.com/JuliaPolyhedra/Polyhedra.jl/blob/b59a9f61ab902ef0d5c7d4a96d95fc035af58ac9/src/polyhedra_to_lp_bridge.jl#L1-L7">source</a></section></article><p>See <a href="https://github.com/JuliaPolyhedra/Polyhedra.jl/blob/master/examples/Polyhedral%20Function.ipynb">Polyhedral Function</a> for an example notebook.</p><h2 id="Creating-a-polyhedron-from-the-feasible-set-of-a-JuMP-model"><a class="docs-heading-anchor" href="#Creating-a-polyhedron-from-the-feasible-set-of-a-JuMP-model">Creating a polyhedron from the feasible set of a JuMP model</a><a id="Creating-a-polyhedron-from-the-feasible-set-of-a-JuMP-model-1"></a><a class="docs-heading-anchor-permalink" href="#Creating-a-polyhedron-from-the-feasible-set-of-a-JuMP-model" title="Permalink"></a></h2><p>A typical application of polyhedral computation is the computation of the set of extreme points and rays of the feasible set of an optimization problem. This comes from the fact that given a minimization of a concave function (or maximization of a convex function) on a convex feasible set (e.g. Linear Programming), we are either in the following three situations:</p><ul><li>The feasible set is empty, i.e. the problem is infeasible.</li><li>An extreme ray is optimal, i.e. the problem is unbounded (or it may also be bounded if the objective is constant along the ray).</li><li>An extreme point is optimal.</li></ul><p>A JuMP model is treated by <code>polyhedron</code> just like any H-representation. For example, the hypercube of dimension <code>n</code> can be created as follows</p><pre><code class="language-julia">m = Model()
@variable(m, 0 ≤ x[1:n] ≤ 1)
poly = polyhedron(m, CDDLib.Library(:exact))</code></pre></article><nav class="docs-footer"><a class="docs-footer-prevpage" href="../projection/">« Projection/Elimination</a><a class="docs-footer-nextpage" href="../utilities/">Utilities »</a><div class="flexbox-break"></div><p class="footer-message">Powered by <a href="https://github.com/JuliaDocs/Documenter.jl">Documenter.jl</a> and the <a href="https://julialang.org/">Julia Programming Language</a>.</p></nav></div><div class="modal" id="documenter-settings"><div class="modal-background"></div><div class="modal-card"><header class="modal-card-head"><p class="modal-card-title">Settings</p><button class="delete"></button></header><section class="modal-card-body"><p><label class="label">Theme</label><div class="select"><select id="documenter-themepicker"><option value="documenter-light">documenter-light</option><option value="documenter-dark">documenter-dark</option></select></div></p><hr/><p>This document was generated with <a href="https://github.com/JuliaDocs/Documenter.jl">Documenter.jl</a> on <span class="colophon-date" title="Monday 30 November 2020 10:38">Monday 30 November 2020</span>. Using Julia version 1.5.3.</p></section><footer class="modal-card-foot"></footer></div></div></div></body></html>