# Reformulations for a linear program with absolute values in the objective function

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?