Programmation linéaire vs programmation linéaire entière

Question

Donné $A,b$, laisser $Ax \le b$ être une instance de programmation linéaire sur les variables $x=(x_1,\dots,x_n)$. Supposons que les contraintes$0 \le x_i$ et $x_i \le 1$ sont inclus dans $A,b$.

Supposons qu'il existe une solution faisable $x \in \mathbb{R}^n$ au problème de programmation linéaire où $x_1 = 1$. Supposons également qu'il existe une solution au programme linéaire entier correspondant, c'est-à-dire qu'il existe$x' \in \{0,1\}^n$ tel que $Ax' \le b$. Sommes-nous garantis qu'il existe une solution avec$x'_1=1$, c'est-à-dire qu'il existe $x' \in \{0,1\}^n$ tel que $Ax' \le b$ et $x'_1=1$?

Pour le dire autrement: si nous résolvons le programme linéaire associé à une instance d'ILP zéro ou un, et trouvons qu'une des variables est affectée à 1 dans une solution du programme linéaire, cela s'ensuit-il qu'il existe une solution? à l'instance ILP où nous définissons cette variable sur 1?

Je suis sceptique mais je n'ai trouvé ni preuve ni contre-exemple.

Answer 1

Le programme $x_1 + 2x_2 = 2$ a la solution entière $(0,1)$ et la solution fractionnée $(1,1/2)$ mais pas une solution entière de la forme $(1,\cdot)$.

Answer 2

Yuval Filmus propose un contre-exemple :$x_1 + 2x_2 = 2$, $0 \le x_1 \le 1$, $0 \le x_2 \le 1$.

Ici, il existe une solution réalisable à l'instance LP avec $x_1=1$, à savoir, $x_1=1$, $x_2=1/2$.

Cependant, la seule solution possible à l'instance ILP est $x_1=0$, $x_2=1$.