Skip to main content
Post Undeleted by J Fabian Meier
deleted 147 characters in body
Source Link
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$.

Then one should note that if there is a vector $x^1$ in $\mathcal{J}$ withLet $x^1_i > 0$ and a vector$M_i$ be the maximal absolute value of $x^2$$x_i$ in $\mathcal{J}$ with $x^2_j> 0$, then we also have a vector $x^3\in \mathcal{J}$ with $x^3_i>0$, $x^3_j>0$ given by any convex combination ofcan introduce binary variables $x^1$$v_i$ and write the problem as:

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

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

So we can solve the Problem $P_i$: $\max x_i$, $x \in \mathcal{J}, x_j \geq 0\, \forall j$ for every $i$ and use a convex combinationThe LP-relaxation of solution vectors to solvethis description is probably poor because of the original problemlarge constant $M_i$.

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

Then one should note that if there is a vector $x^1$ in $\mathcal{J}$ with $x^1_i > 0$ and a vector $x^2$ in $\mathcal{J}$ with $x^2_j> 0$, then we also have a vector $x^3\in \mathcal{J}$ with $x^3_i>0$, $x^3_j>0$ given by any convex combination of $x^1$ and $x^2$.

So we can solve the Problem $P_i$: $\max x_i$, $x \in \mathcal{J}, x_j \geq 0\, \forall j$ for every $i$ and use a convex combination of solution vectors to solve the original problem.

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

Post Deleted by J Fabian Meier
added 24 characters in body
Source Link
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$.

Then one should note that if there is a vector $x^1$ in $\mathcal{J}$ with $x^1_i > 0$ and a vector $x^2$ in $\mathcal{J}$ with $x^2_j> 0$, then we also have a vector $x^3\in \mathcal{J}$ with $x^3_i>0$, $x^3_j>0$ given by any convex combination of $x^1$ and $x^2$.

So we can solve the Problem $P_i$: $\max x_i$, $x \in \mathcal{J}$$x \in \mathcal{J}, x_j \geq 0\, \forall j$ for every $i$ and use a convex combination of solution vectors to solve the original problem.

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

Then one should note that if there is a vector $x^1$ in $\mathcal{J}$ with $x^1_i > 0$ and a vector $x^2$ in $\mathcal{J}$ with $x^2_j> 0$, then we also have a vector $x^3\in \mathcal{J}$ with $x^3_i>0$, $x^3_j>0$ given by any convex combination of $x^1$ and $x^2$.

So we can solve the Problem $P_i$: $\max x_i$, $x \in \mathcal{J}$ for every $i$ and use a convex combination of solution vectors to solve the original problem.

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

Then one should note that if there is a vector $x^1$ in $\mathcal{J}$ with $x^1_i > 0$ and a vector $x^2$ in $\mathcal{J}$ with $x^2_j> 0$, then we also have a vector $x^3\in \mathcal{J}$ with $x^3_i>0$, $x^3_j>0$ given by any convex combination of $x^1$ and $x^2$.

So we can solve the Problem $P_i$: $\max x_i$, $x \in \mathcal{J}, x_j \geq 0\, \forall j$ for every $i$ and use a convex combination of solution vectors to solve the original problem.

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

Then one should note that if there is a vector $x^1$ in $\mathcal{J}$ with $x^1_i > 0$ and a vector $x^2$ in $\mathcal{J}$ with $x^2_j> 0$, then we also have a vector $x^3\in \mathcal{J}$ with $x^3_i>0$, $x^3_j>0$ given by any convex combination of $x^1$ and $x^2$.

So we can solve the Problem $P_i$: $\max x_i$, $x \in \mathcal{J}$ for every $i$ and use a convex combination of solution vectors to solve the original problem.