Skip to content
Set Programming with JuMP
Branch: master
Clone or download
blegat Merge pull request #3 from blegat/bl/citation
[ci skip] Add CITATION.bib
Latest commit 5ed223c Jun 20, 2019
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
examples
src Update May 22, 2019
test
.gitignore
.travis.yml
CITATION.bib [ci skip] Add CITATION.bib Jun 20, 2019
Project.toml Add lb on Moment May 22, 2019
README.md
REQUIRE

README.md

SetProg

Build Status Social
Build Status Gitter
Codecov branch

JuMP extension for Set Programming : optimization with set variables and inclusion/containment constraints. This package allows the formulation of a mathematical programming involving both classical variables and constraints supported by JuMP and set variables and constraints.

Three options exist to solve Set Programming:

In fact, the option to use can be automatically chosen depending on the variables created and the objective function set:

Variable/Objective Volume of set Affine of point
Polyhedron Polyhedral Dual Dynamic
Ellipsoid/PolySet Sum-of-Squares Sum-of-Squares

Variables

The variables can either be

  • an Ellipsoid or more generally the 1-sublevel set of a polynomial of degree 2d;
  • a polyhedron (not yet implemented);
  • a quadratic cone or more generally the 0-sublevel set of a polynomial of degree 2d (not yet implemented).
@variable m S Ellipsoid()
@variable m S PolySet(d) # 1-sublevel set of a polynomial of degree 2d
@variable m S PolySet(d, convex=true) # Convex 1-sublevel set of a polynomial of degree 2d
@variable m S PolySet(d, symmetric=true) # 1-sublevel set of a polynomial of degree 2d symmetric around the origin
@variable m S PolySet(d, symmetric=true, point=SetProg.CenterPoint([1, 0])) # 1-sublevel set of a polynomial of degree 2d symmetric around the [1, 0]

not yet implemented:

@variable m S Polyhedron()
@variable m S QuadCone()  # Quadratic cone
@variable m S PolyCone(d) # 0-sublevel set of a polynomial of degree 2d

Expressions

The following operations are allowed:

Operation Description
A*S Linear mapping

But more operations are planned to be added:

Operation Description
S + x Translation of S by x
S1 + S2 Minkowski sum
S1 ∩ S2 Intersection of S1 and S2
S1 ∪ S2 Union of S1 and S2
polar(S) Polar of S

Constraints

The following constraints are implemented

Operation Description
x ∈ S x is contained in S
S1 ⊆ S2 S1 is included in S2
S1 ⊇ S2 S1 is included in S2

But more are planned to be added:

Operation Description
S1 == S2 S1 is equal to S2

Examples

Consider a polytope

using Polyhedra
P = HalfSpace([1, 1], 1) ∩ HalfSpace([-1, 0], 0) ∩ HalfSpace([0, -1], 0)

Pick an SDP solver (see here for a list)

using CSDP # Optimizer
factory = with_optimizer(CSDP.Optimizer)

To compute the maximal ellipsoid contained in the polytope P defined above (i.e. Löwner-John ellipsoid):

using JuMP
model = Model(factory)
@variable(model, S, Ellipsoid())
@constraint(model, S ⊆ P)
@objective(model, Max, nth_root(volume(S)))
optimize!(model)

To compute the maximal invariant set contained in a polytope (not yet implemented):

using JuMP
model = Model(factory)
@variable(model, S, Polyhedron())
@constraint(model, S ⊆ P)
@constraint(model, A*S ⊆ S) # Invariance constraint
@objective(model, Max, volume(S))
optimize!(model)

To compute the maximal invariant ellipsoid contained in the polytope P defined above:

using JuMP
model = Model(factory)
@variable(model, S, Ellipsoid())
@constraint(model, S ⊆ P)
@constraint(model, A*S ⊆ S) # Invariance constraint
@objective(model, Max, nth_root(volume(S)))
optimize!(model)

To compute the maximal algebraic-invariant ellipsoid (i.e. AS ⊆ ES) contained in the polytope P defined above:

using JuMP
model = Model(factory)
@variable(model, S, Ellipsoid())
@constraint(model, S ⊆ P)
@constraint(model, A*S ⊆ E*S) # Invariance constraint
@objective(model, Max, L1_heuristic(volume(S), zeros(Polyhedra.fulldim(P))))
optimize!(model)
You can’t perform that action at this time.