A difficult combinatorial optimization problem

Question

Let $\mathcal{J}$ be a closed, bounded, compact, convex set in $\mathbb{R}^L$.

(Notations: vector $\mathbf{x}$ is denoted in bold letters and its $i^{th}$ co-ordinate is denoted as $x_i$. $\mid\mathcal{S}\mid$ denotes the cardinality of set $\mathcal{S}$.)

Consider the following problem \begin{align} \max_{\substack{\mathcal{S}\subset\{1,\dots,L\}\\ \mathbf{x}\in\mathcal{J}}}\,\mid\mathcal{S}\mid \\ x_i\,\leq\, -1,~i\in\mathcal{S } \end{align} Is there a way to rewrite this problem in terms of variables rather than the cardinality? For instance, one way I am familiar is \begin{align} \max_{\substack{v_1,\dots,v_L\\\mathbf{x}\in\mathcal{J} }}&\sum_{i=1}^{L}v_i\\ &v_i(x_i+1)\leq 0,i\in\{1,\dots,L\}\\ &v_i\in\{0,1\},\,\forall i \end{align} Actually I am trying to derive the the dual of this problem. Any suggestion in that regard would be really helpful.

Answer 1

First of all, one can shift the set $\mathcal{J}$ so that the condition $x_i \leq 1$ can be replaced by $x_i \geq 0$.

Let $M_i$ be the maximal absolute value of $x_i$ in $\mathcal{J}$, then we can introduce binary variables $v_i$ and write the problem as:

$\max \sum_{i\in S} v_i$

$M(v_i - 1) \leq x_i$ $\forall i \in S$.

The LP-relaxation of this description is probably poor because of the large constant $M_i$.