Disjunctive programming software

Question

Can you advise me any kind of existing software that can help to solve the disjunctive programming problem?

The problem is the following.

We have unit 3D planes $\Pi_{1}, \ldots, \Pi_{N}$ (they are known). Let us write them as follows: $U_{j} x = H_{j}, j = 1, \ldots, N$.

Having the fixed numbers $n$ and $m$, we want to find 3D planes $\pi_{1}, \ldots, \pi_{n}$ and 3D points $x_{1}, \ldots, x_{m}$ such that:

1. Planes and points satisfy the incidence structure: $x_{i} \in \pi_{j}\;\;\forall(i, j) \in I$, where $I$ is fixed known set $I \subseteq \{1, \ldots, m\} \times \{1, \ldots, n\}$.
2. The polyhedron bounded by planes $\pi_{1}, \ldots, \pi_{n}$ is convex.

and minimize the function $\sum \limits_{j = 1}^{N}(H_{j} - \max \limits_{i = 1, \ldots, m} (x_{i}, U_{j}))^{2}$.

Since we have a $\max$ in the functional, the above problem can be formulated as a disjunctive programming program as follows:

$$\begin{align} &\text{minimize} \sum \limits_{j = 1}^{N}(H_{j} - L_{j})^{2}\\ &\text{subject to } \, (1-2) \text{ and } \forall j = 1, \ldots, N\; \exists i \text{ such that } (x_{i}, U_{j}) = H_{j} \enspace . \end{align}$$

I have read from Internet that such problems are called disjunctive programming. Can you give any hint which software can be used to solve it?

Answer 1

I haven't used it, but Pyomo, a seemingly well-supported modeling software includes a module for generalized disjunctive programming.

One of the many examples they provide at the above link appears as follows:

m = ConcreteModel()
m.s = RangeSet(4)
m.ds = RangeSet(2)
m.d = Disjunct(m.s)
m.djn = Disjunction(m.ds)
m.djn[1] = [m.d[1], m.d[2]]
m.djn[2] = [m.d[3], m.d[4]]
m.x = Var(bounds=(-2, 10))
m.d[1].c = Constraint(expr=m.x >= 2)
m.d[2].c = Constraint(expr=m.x >= 3)
m.d[3].c = Constraint(expr=m.x <= 8)
m.d[4].c = Constraint(expr=m.x == 2.5)
m.o = Objective(expr=m.x)

# Add the logical proposition
m.p = LogicalConstraint(
   expr=m.d[1].indicator_var.implies(m.d[4].indicator_var))
# Note: the implicit XOR enforced by m.djn[1] and m.djn[2] still apply

# Apply the Big-M reformulation: It will convert the logical
# propositions to algebraic expressions.
TransformationFactory('gdp.bigm').apply_to(m)

# Before solve, Boolean vars have no value
Reference(m.d[:].indicator_var).display()

# Solve the reformulated model
run_data = SolverFactory('glpk').solve(m)
Reference(m.d[:].indicator_var).display()

From this we learn several things.

1. The syntax is a little awkward. However, they have more succinct syntax available at the link.
2. They have transformations available to make GDPs accessible to various solvers. The example above shows a Big-M transformation. These introduce no additional variables, but tend to be a little looser than Hull transformations. They also have an experimental hybrid Big-M/Hull transformation and a solver that works on the GDP directly. See the list of transformations/reformulations here.
3. Pyomo can interface with several solvers. This is great since it allows you to play around to figure out which solvers are appropriate for your problem. In particular, there are a number of open source solvers available that work decently for small problems; however, for larger problems you may need to work with a commercial solver. Pyomo makes this possible.

If, for whatever reason, you needed to do the GDP transformation by hand the paper

I. E. Grossmann and J. P. Ruiz. Generalized disjunctive programming: A framework for formulation and alternative algorithms for MINLP optimization. In J. Lee and S. Leyffer, editors, Mixed Integer Nonlinear Programming, pages 93–115, New York, NY, 2012. Springer New York. ISBN 978-1-4614-1927-3.

has a decent explanation of the MINLP transformation and a less comprehensible explanation of a hull transformation.