Skip to main content
3 of 3
deleted 147 characters in body
J Fabian Meier
  • 1.3k
  • 10
  • 24

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$.

J Fabian Meier
  • 1.3k
  • 10
  • 24