Finding the right JuMP package to solve a mixed-integer convex program

Specific Domains Optimization (Mathematical)
1

I have a fairly straightforward optimisation problem that looks like this:

\max \ \log(a \cdot x) + b \cdot x \\ s.t. \ x \in \{0,1\}^n \text{ and } \sum_{i \in [n]}x_i \leq 10,

for some a, b \in \mathbb{R}^n.

I’d like to solve this program with a package from the JuMP ecosystem, but there are so many and I don’t know how to proceed. Is Pajarito.jl a good starting point? It doesn’t seem to have extensive documentation, so any pointers would be greatly appreciated.

2

Have a look at SCIP: https://github.com/scipopt/SCIP.jl

2 Likes
3

Hi!

You have several possibilities (more on solvers below):

  1. Keep that log term as it is, and use a Mixed-Integer Nonlinear Programming (MINLP) solver (more on those below)
  2. Convert the log term to conic form (see the Mosek modeling cookbook for how to do so), and use a mixed-integer conic solver.
  3. Build your model using Convex.jl (this page should help get you started)

In terms of numerical stability, available tools and, ultimately, speed, I highly recommend the conic form. Note that, if you use Convex.jl, it will automatically reformulate the log term using a conic constraint.

In terms of solvers, you can find a list of supported solvers here.
Which solver you can use depends of how you modeled the problem (general nonlinear or conic)

  • MINLP: Alpine, Bonmin, SCIP
  • MI-Conic: Mosek, Pajarito

Mosek is a commercial product, but they have free academic licenses. SCIP is also free for academic research. The other ones are open-source. Note that both Alpine and Pajarito require external solvers.

Option D

If you’re OK with a relaxation / approximate solution, you can also build a polyhedral outer-approximation of the log term, and pass the resulting problem to your favorite MILP solver.

To do so:

  • introduce an additional variable t >= 0…
  • … and a constraint t = a^{T}x, so that the objective becomes \log(t) + b^{T}x.
  • then linearize the \log(t) terms using a finite number of tangents. The more tangents you use, the better the approximation, but the larger the problem.
5 Likes
4

Thanks for your excellent suggestions, @mtanneau. I’m currently attempting your second approach, and I’m having difficulty converting the log term to conic form. Here’s my current attempt, in which I intend for y to stand for \log(a \cdot x). But if I’m not mistaken, (u, 1, z) \in K_{exp} only guarantees z \leq \log(a \cdot x), whereas I need equality. Is there a clever way to achieve this?

\max y \\ \text{s.t.}\ \ y = z + x \cdot b, \\ \qquad \ \ \ (u, 1, z) \in K_{exp}, \\ \ u = a \cdot x.

Edit: Since posting this reply, I’ve realised that an optimal solution (z,x) to the program above always satisfies z = \log(a \cdot x) (otherwise we could increase z which also increases the objective value).