CODEWITHSUNDEEP
drake
Andrea Tagliabue
Andrea Tagliabue

Reputation: 13

Which solver should I use in Drake to solve a mixed-integer program with non-linear constraints?

I am trying to solved a mixed-integer non-linear program with Drake using the Snopt solver, but I encounter the following error:

ValueError: The capabilities of drake::solvers::SnoptSolver do not meet the requirements of the MathematicalProgram ({ProgramAttributes: GenericConstraint, QuadraticCost, LinearConstraint, LinearEqualityConstraint, BinaryVariable})

What is the recommended solver/alternative approach in my case?

Upvotes: 1

Views: 455

Answers (2)

Hongkai Dai
Hongkai Dai

Reputation: 2766

As you mentioned that your constraint is

x[k+1] = A * ((1-b[k]) * x1[k] + b[k] * x2[k])

where b[k] is a binary variable, x1[k], x2[k], x[k+1] are continuous variables.

This constraint could be reformulated as a mixed-integer linear constraint. What you want is

b[k] = 1, then x[k+1] = A * x2[k]
b[k] = 0, then x[k+1] = A * x1[k]

Generally, if by fixing the binary variable to either 0 or 1, the remaining constraint is linear, then the constraints can be reformulated as mixed-integer linear constraints. There are two approaches to convert your constraint to mixed-integer linear constraint, namely the big-M approach and the convex hull approach, as explained in this tutorial.

As a quick demo on the convex hull approach, suppose that your variable are bounded

x1[k] ∈ ConvexHull(v₁, v₂, ..., vₘ)
x2[k] ∈ ConvexHull(w₁, w₂, ..., wₙ)

where v₁, v₂, ..., vₘ, w₁, w₂, ..., wₙ are all given points.

We introduce two slack variables s1, s2. We intend to impose the following constraints

b[k] = 1, then s1 = 0, s2 = A * x2[k]
b[k] = 0, then s2 = 0, s1 = A * x1[k]
x[k+1] = s1 + s2

The constraints above means that the convex hull of the point (b[k], s2, x2[k]) is the polytope with vertices

(1, A * w₁, w₁)
(1, A * w₂, w₂)
...
(1, A * wₙ, wₙ)
(0, 0, w₁)
(0, 0, w₂)
...
(0, 0, wₙ)

With these vertices, the polytope is written in the V-representation. You could convert this V-representation to an H-representation. This H-representation is denoted as

H * [b[k], s2, x2[k]] <= h

Where each row of H is a face normal of the polytope. This H-representation is a (mixed-integer) linear constraint on the variables b[k], s2, x2[k]. An alternative formulation to constrain that b[k], s2, x2[k] to lie within the polytope is to write (b[k], s2, x2[k]) as a convex combination of the polytope vertices (You will need to introduce the convex combination weights as decision variables also, with all the weights being non-negative, and the sum of the weights equal to 1). Using this convex combination approach you won't need to convert the V-representation to H-representation. Here is the mixed-integer linear constraints on b[k], s2, x2[k] using the convex combination approach.

b[k] = λ₁ + λ₂ + ... + λₙ
s2 = A*(λ₁w₁ + λ₂w₂ + ... + λₙwₙ)
x2[k] = λ₁w₁ + λ₂w₂ + ... + λₙwₙ + λₙ₊₁w₁ + λₙ₊₂w₂ + ... + λ₂ₙwₙ
1 = λ₁ + λ₂ + ... + λₙ + λₙ₊₁ + λₙ₊₂ + ... + λ₂ₙ
λᵢ ≥ 0 ∀ i = 1, ..., 2n
b[k] is binary

where the weights λᵢ, i = 1, ..., 2n are new slack variables representing the convex combination weights. You could verify that these constraints enforce that

if b[k] = 0, then s2 = 0.
if b[k] = 1, then s2 = A*x2[k]

Similarly we know that the convex hull of the point (b[k], s1, x1[k]) is a polytope with the following vertices

(1, 0, v₁)
(1, 0, v₂)
...
(1, 0, vₘ)
(0, A*v₁, v₁)
(0, A*v₂, v₂)
...
(0, A*vₘ, vₘ)

and we can write the linear constraints from the H-representation of the polytope. We combine the two sets of linear constraints derived from the polytopes, together with the linear constraint x[k+1] = s1 + s2, we get the mixed-integer linear constraints of your problem. For the detailed explanation of this convex hull approach, you could refer to the linked tutorial above.

Upvotes: 2

Tobia Marcucci
Tobia Marcucci

Reputation: 223

Mixed integer nonlinear optimizations are very hard problems and only a handful of optimization solvers exist for that, e.g.: Couenne, Baron. Drake does not support any of these solvers.

Drake supports solvers for most common mixed-integer convex programs (such as MILPs, MIQPs, MISOCs). But for using these, your optimization problem must only have convex constraints (e.g. linear equalities and inequalities).

One way to proceed using a nonlinear solver such as SNOPT to solve your optimization problem is to enforce binary constraints as follow. Say you want x to be binary, then you can add the smooth constraint x * (x - 1) = 0. (Note that the latter is verified iff x = 0 or x = 1.) This however is a very "tough" constraint, and can lead to numeric issues. Note also that doing this you do not have any guarantees in terms of finding a feasible solution if one exists (guarantees that you do have in mixed-integer convex programming), and the solver might converge to a local minimum.

Upvotes: 2

Related Questions