I am looking for suggestions on improving the formulation of the following problem: $\max_{\vec{x} \in \mathbb{R}^{2^n}} \sum_{i=1}^{2^n}\lvert x_i \rvert$ such that $\vec{x}$ is in the feasible region $\mathcal{F} = \{ \vec{x} = (x_1, \ldots, x_{2^n}) \;:\; \lvert x_i \rvert \leq 1 \;\cap\; A \vec{x} \geq 0 \;\cap\; AB\vec{x} \geq 0 \;\cap\; \sum_i (A\vec{x})_i = 1\}$, where $A$ and $B$ are fixed, symmetric matrices in $\mathbb{R}^{2^n \times 2^n}$ and the vector inequalities are meant element-wise.

To linearize the objective function, I introduce $2^n$ auxiliary binary variables $b_i$, and write

$$ \max_{\vec{x}, b_i} \; \sum_{i=1}^{2^n} a_i \\ \text{subject to:} \quad\quad\quad\\ \vec{x} \in \mathcal{F} \\ b_i \in \{0, 1\}, \;\;\forall i \in \{1, \ldots, 2^n\} \\ x_i + M b_i \geq a_i \\ -x_i + M (1 - b_i) \geq a_i \\ $$

where $M = 2$, for instance. A minimal working example in Julia + JuMP is:

using LinearAlgebra
using JuMP, HiGHS

function mwe(n)
    ncoeffs = 2 ^ n
    A, B = [reduce(kron, repeat([Symmetric(rand(2, 2))], n)) for _ in 1:2]

    model = Model(HiGHS.Optimizer)
    @variable(model, x[1:ncoeffs], lower_bound=-1, upper_bound=1)

    # Feasibility region:
    y = A * x
    @constraint(model, y .>= 0)
    @constraint(model, sum(y) == 1)
    @constraint(model, (A * B * x) .>= 0)
    # Auxiliary variables to model the absolute values:
    @variable(model, a[1:ncoeffs], lower_bound=0, upper_bound=1)
    @variable(model, b[1:ncoeffs], Bin)

    M = 2
    for i in 1:ncoeffs
        @constraint(model,  x[i] + M * b[i] >= a[i])
        @constraint(model, -x[i] + M * (1 - b[i]) >= a[i])

    @objective(model, Max, sum(a))

Depending on the chosen $A$ and $B$, this runs just fine up to $n=5$, but may have difficulty of stop converging soon after that. (I am randomly sampling the matrices for simplicity but in my actual problem I am interest in some cases where convergence seems to be extremely slow). The number of variables alone does not seem immediately a problem, with $2^n$ binary and $2^{n+1}$ continuous variables, and different solvers do not perform much better.

Is there any smarter formulation for this model?

I am also interested in advice on:

  • What is the source of slowness in this kind of models?
  • What is the relation between the matrices $A$ and $B$ that makes it easier or harder to solve?
  • Are there any alternatives to MIP that would lead to good, even if suboptimal, solutions to this problem?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.