0
$\begingroup$

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])
    end

    @objective(model, Max, sum(a))
    optimize!(model)
    model
end

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?
$\endgroup$

0

Your Answer

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