Developing Data-driven Methods for Mixed-integer
Nonlinear Programs
Xuan Lin and Dennis W. Hong

Abstract—Robot motion planning and control problems tend toinclude discrete decision-making such as contact scheduling andcontinuous nonlinear (non-convex) programs such as kinematics
and dynamics constraints. Simultaneously planning discrete andcontinuous non-convex variables are known as mixed-integer
nonlinear programs (MINLPs). MINLPs of practical sizes are
typically challenging. In this work, we compare the performanceof several methods including the Alternating Direction Methodof Multipliers (ADMM), data-driven mathematical programswith complementary constraints, and data-driven mixed-integer
programs with envelopes, to solve a 2D bookshelf organization
problem formulated as a mixed-integer bilinear program. The
final goal is to develop a data-driven pipeline for solving MINLPs.

I. I NTRODUCTION
The problems we are interested in solving are mixed-integerbilinear programs parametrized by Θ that is drawn from a
distribution D(Θ). For each Θ, we seek a solution to theoptimization problem:
minimize fobj (x, z; Θ)x, zs. t. fi (x, z; Θ) ≤ 0, i = 1, ..., mf(1)

bj (x, z; Θ) ≤ 0, j = 1, ..., mb
Where x denotes continuous variables and z binary variables
with zi ∈ {0, 1} for i = 1, ..., dim(z). Constraints fi are
mixed-integer convex, meaning if the binary variables z are
relaxed into continuous variables z ∈ [0, 1], fi becomes
convex. Constraints bj are mixed-integer bilinear, meaning that
relaxing the binary variables gives bilinear constraints.
There are two directions to convert this problem to either
mixed-integer convex programs (MICPs) or mathematical programs with complementary constraints (MPCCs). The MICP
approach converts the bilinear constraint b into mixed-integer
linear constraints using McCormick envelopes. The MPCC
approach converts integer variables into continuous variables
with additional complementary constraints. While MICPs canguarantee a global optimal solution, McCormick envelope
constraints make them very slow. On the other hand, MPCCs
only seek local optimal solutions, but almost impossible tosolve without a good initial guess. For both approaches, presolved data becomes very helpful. Data can uncover importantregions to reduce the size of MICPs. In the best case, it canbe reduced to a convex optimization problem. A learner canbe trained offline to map the problem parameter Θ to a goodcandidate solution. The solution will be modified online forsolving new problem instances. Data can also provide goodinitial guesses that dramatically increase the chance of successto solve MPCCs.

However, it is difficult to collect enough data for warmstart MICP or MPCC solvers, especially when the problem
becomes larger. We also demonstrate using ADMM to solvethe mixed-integer bilinear programs. This approach does notdepend on data, and have decent chance of convergence thus
can be used to collect the initial dataset.
II. B OOKSHELF P ROBLEM
Fig. 1 shows the complete formulation of 2D bookshelforganization problem. The main goal of this problem is touse robot manipulator to insert one book into the shelf suchthat minimal movement of existing books is required. The
complete formulation of this problem is given in 1. This problem contains integer variables representing different contact
states of the books, and continuous variables related to rotation
matrices and collision avoidance. In particular, this formulation
formulates collision avoidance using separating planes intobilinear inequality constraints. This approach is applicable
to multi-agent planning problems. This problem may havea solving time limitation and optimal cost requirement, as
a less optimal motion may take significantly longer for themanipulator to finish. We demonstrate the aforementioned
approaches on this problem and compare their performances.
III. A PPROACHES
A. ADMM Formulation
We implemented the non-data-driven algorithm ADMM in[1]. The basic idea is to separate the MINLP into a MIP formulation and an NLP formulation with the exact copies of variables but different constraints, and iterate between them until
the consensus is reached. The MIP formulation contains constraints A, B, D, G, H1, I1, J1, K2, K3, L2, L3, while missing bilinear constraints C, E, F, K1, L1. The NLP formulation contains constraints A, B, C, D, E, F, H, I, J, K, L, while
missing the mode constraint G which says zi s are integers.
The ADMM iterates the following 3 steps: first it solves theMIP formulation, then solves the NLP formulation. Finally it
updates the dual variables. The process continues till convergence. The readers are referred to [1] for details. The results
are shown in II column 1, 2.
B. MPCC Formulation
An equivalent formulation of the bookshelf organization
problem in Fig. 1 is to turn all the integer variables zi into
continuous variables with complementary constraints, suchthat the complete formulation can be solved through NLP

Fig. 1.
ADMM - Knitro

ADMM - IPOPTMPCC default- Knitro

MPCC default- IPOPT

Using default initial guess fromCasADi

Note
Success Rate

96.5%

94.75%

1.25 %

Avg. Solve Time

260 ms522 ms

Max. Solve Time

1.29 sec

Avg. Objective-7250

Avg. # of iterations

4.73

4.6

Gurobi+Knitro

Gurobi+IPOPT

SolverComplete formulation of the bookshelf organization problem.
MPCC Manual- IPOPT

Using manually selected 1 initial guess

MPCC KNN3- Knitro (15000data)

MPCC KNN3- IPOPT (15000 data)

KNN selects top 3 guesses from 15000 data

MPCC KNN3 (Rev)- Knitro (36000 data)

ReDUCE - 200(15000 data)

ReDUCE - 600(15000 data)

ReDUCE - 200(78000 data)

Same to left but selectthe worst 3 guesses

Max iterationof OSQP=200

Max iterationof OSQP=600

Currently KNN
learner

78.25%

78.25%

99.25%

98.5%

92.5%

94.5%

98.75%

96%

72 ms

29 ms

81 ms

30 ms

96 ms

61 ms

65 ms

80 ms

16 ms

3.59 sec

82 ms

198 ms

1.96 sec

280 ms

990 ms

327 ms

190 ms

400 ms

174 ms

-7339

-5703

-8620

-8952

-8258

-8618

-6461

-8631

-8687

-8637

11

1.05

1.06

1.25

4.85

3.85

2.57Knitro

IPOPTKnitro

IPOPT

Knitro

OSQP

OSQP

OSQP

Knitro0%

MPCC Manual- Knitro

IPOPTsolvers. We implemented the formulation from [4]. Specifically zi (1 − zi ) = 0, which is equivalent to zi ∈ {0, 1}.
To get MPCC working, proper initial guesses are required.
Using the solver’s default initial guess will result in a successrate lower than 5%. We take 2 different approaches to supply
better initial guesses. The first approach is choosing fromheuristics. For this problem, we choose the initial guess to bethe original scene as the problem minimizes the movement ofbooks. The second approach is collecting a dataset offline andusing k-nearest neighbor to pick the top 3 candidate solutions
online for initial guess, which is data-driven. The results areshown in Table II column 4 − 10.

solver takes only 1 trial to find a feasible solution. However,the solving speed seems to be limited. Finally, if the algorithm
can learn a mapping to a convex problem well, the convex
approach has potential to solve most of the test problems with
1 or 2 trials. One can leverage on the strong performanceof convex solvers to achieve fastest speed. However, thisapproach requires larger amount of data for more precise
learning.
The proposed algorithms are being tested on more challenging robotics problems such as modular self-configurable robot
systems and hybrid MPC. Some results are under review.

C. Convex Formulation[1] Alp Aydinoglu and Michael Posa. Real-time multicontact model predictive control via admm. arXiv preprint
arXiv:2109.07076, 2021.
[2] Abhishek Cauligi, Preston Culbertson, Edward Schmerling, Mac Schwager, Bartolomeo Stellato, and MarcoPavone. Coco: Online mixed-integer control via supervised learning. IEEE Robotics and Automation Letters, 7(2):1447–1454, 2021.
[3] Xuan Lin, Gabriel I Fernandez, and Dennis W Hong. Reduce: Reformulation of mixed integer programs using datafrom unsupervised clusters for learning efficient strategies.
arXiv preprint arXiv:2110.00666, 2021.
[4] Jaehyun Park and Stephen Boyd. A semidefinite programming method for integer convex quadratic minimization.
Optimization Letters, 12(3):499–518, 2018.

We implemented the approach given by [3], named ReDUCE, which converts bilinear constraints into mixed-integerenvelope constraints and uses a data-driven approach to reduce
the size of integer problems. In the best case, it can directly
learn a mapping to a convex problem in the same fashion as[2]. The results are shown in II column 11 − 13.
IV. C ONCLUSION
The results show that the non-data-driven ADMM approachhas good chance of convergence and decent solving speed. The
rate of success is significantly higher than a poorly initialized
MPCC and significantly faster than a MICP formulation without warm-start. The MPCC formulation has good performancewith data of thousands, mainly due to the strong capability ofNLP solvers to find feasible solutions. In most cases, NLP

R EFERENCES