Comment minimiser la cardinalité d'un ensemble et de partitions disjointes soumises à des contraintes en temps polynomial?

Le vrai problème auquel je suis confronté est le suivant.

INSTANCE : j'ai des ensembles $N:=\{1,\ldots,n\}$ et $K:=\{1,\ldots,k\}$ et matrice $a_{ij}>0$ pour tous $i\in K$ et $j\in N$ .

QUESTION : J'ai besoin de trouver un sous-ensemble $S$ de $N$ de taille aussi petite que possible et partitionner l'ensemble $K$ dans $|S|$ ensembles disjoints $K_j$ dont l'union est égale $K$ de telle sorte que pour tous $j\in S$ , J'ai

\sum_{j^{'} \in S j^{'} \neq j} a_{i j^{'}} ⩽ a_{i j} - 1,

$\sum_{j'\in S\\j'\neq j} a_{ij'} \leqslant a_{ij}-1,$ pour tout .

i \in K_{j}

$i\in K_j$

Exemple:

Soit et la matrice $n=k=3$

[\begin{matrix} 0.6 & 2.7 & 1.2 \\ 1.3 & 2.6 & 0.8 \\ 1.5 & 0.4 & 0.6 \end{matrix}] .

$\begin{bmatrix} 0.6 & 2.7 & 1.2\\ 1.3 & 2.6 & 0.8\\ 1.5 & 0.4 & 0.6 \end{bmatrix}.$

Dans cet exemple, doit être égal à et et . $S$ $S=\{1, 2\}$ $K_1=\{3\}$ $K_2=\{1,2\}$

J'ai remarqué deux faits:

S'il existe des $j\in N$ tels que $a_{ij}\geqslant 1$ pour tout $i\in K$ alors $S=\{j\}$ et $K_j=K$ ; et
S'il existe des $i\in K$ tels que $a_{ij}<1$ alors $S=\emptyset$ .

Ma question : est-il possible de résoudre ce problème d'optimisation en temps polynomial (au moins avec l'algorithme d'approximation)?

La première chose que j'ai essayé de faire est de le transformer en un problème connu, puis d'appliquer un algorithme connu pour cela. J'ai pensé à le transformer en un ensemble de couvertures ou d' emballages mais j'ai échoué et je ne pense pas non plus que ce soit intéressant.

Le problème que j'ai essayé de formuler.

Je ensembles et et la matrice pour tout et . De plus, j'ai ensembles disjoints pour chaque , (j'ai ajouté en entrée car je ne pouvais pas le formuler autrement.) $N:=\{1,\ldots,n\}$ $K:=\{1,\ldots,k\}$ $a_{ij}>0$ $i\in K$ $j\in N$ $n$ $K_j\subset K$ $j\in N$ $K_j$

Enfin, j'obtiens ceci:

\begin{aligned} \underset{S}{minimize} & | S | \\ subject to & \sum_{j^{'} \in S j^{'} \neq j} a_{i j^{'}} ⩽ a_{i j} - 1, \forall j \in S, i \in K_{j}, \\ S \subseteq N . \end{aligned}

$\begin{align*} & {\underset{S}{\text{minimize}}} & & |S|\\[3pt] & \text{subject to} & & \sum_{j'\in S\\j'\neq j} a_{ij'} \leqslant a_{ij}-1,\forall\, j\in S,i\in K_j,\\[3pt] & & & S\subseteq N.\\ \end{align*}$

Merci.

algorithms optimization drzbir
la source

Avez-vous essayé de reformuler en tant qu'ILP en utilisant des variables binaires ? Votre objectif passe à min avec une modification similaire dans la contrainte. Un solveur ILP standard peut très bien le gérer.

x_{j}

$x_j$

\sum x_{j}

$\sum x_j$

Nicholas Mancuso

Mais je pense que cela ne me donnerait pas un algorithme de temps polynomial?

drzbir

Peut-être en théorie, mais pas en pratique. Les solveurs modernes comme CPLEX sont incroyablement bons pour trouver des solutions optimales en un temps relativement court grâce à l'heuristique de branchement et liée et à d'autres heuristiques.

Nicholas Mancuso

Les tous ? Si c'est le cas, alors je pense que la formulation de votre "vrai problème" a un problème, car il est optimisé trivialement en laissant être n'importe quel ensemble singleton : faire cela fait que la somme sur le LHS de votre fonction objectif soit 0 .

a_{i j}

$a_{ij}$

\geq 1

$\ge 1$

S

$S$

{j}

$\{j\}$

j_random_hacker

Tous les sont pas tous supérieurs à .

a_{i j}

$a_{ij}$

1

$1$

drzbir

Réponses:

Même la version décisionnelle de ce problème, dans laquelle nous essayons de déterminer simplement s'il existe une solution possible, est NP-difficile par réduction à partir d' Exact Cover . (La version d'optimisation, où nous recherchons une solution réalisable qui minimise , est clairement au moins aussi difficile que cela.) $|S|$

La matrice à une seule ligne et à une seule colonne contenant la valeur 0,5 est un exemple d'entrée pour laquelle il n'existe aucune solution réalisable. En voici une autre:

[\begin{matrix} 0.2 & 4 \\ 3.1 & 3 \\ 5 & 0.6 \end{matrix}] .

$\begin{bmatrix} 0.2 & 4\\ 3.1 & 3\\ 5 & 0.6 \end{bmatrix}.$

Création d'un gadget "Choisissez au plus un"

Tout d'abord, notez que si la valeur maximale dans une ligne est , et que cette ligne contient (au moins) deux copies de , disons en et , , alors ne peut pas contenir à la fois et , car si tel était le cas, l'un des deux cas suivants doit se produire, chacun conduisant à une contradiction: $a_i$ $x > 0$ $x$ $a_{ij}$ $a_{ij'}$ $j' \ne j$ $S$ $j$ $j'$

$i \in K_j \cup K_{j'}$ : Supposons que wlog . Mais alors , contredisant l'exigence que . $i \in K_j$ $\Sigma_{m \in S, m \ne j}{a_{im}} \ge a_{ij'} = x = a_{ij}$ $\Sigma_{m \in S, m \ne j}{a_{im}} \le a_{ij} - 1$
$i \notin K_j \cup K_{j'}$ : Supposons alors . Mais alors , et puisque est maximal dans la ligne , le plus élevé que pourrait être clairement , donc nous devons violer la même inégalité qu'auparavant. $i \in K_p, p \notin \{j, j'\}$ $\Sigma_{m \in S, m \ne p}{a_{im}} \ge a_{ij} + a_{ij'} = 2x$ $x$ $i$ $a_{ip}$ $x$

Ainsi , nous pouvons choisir une valeur maximale qui est en toute sécurité supérieure à la somme de toutes les valeurs non maximales de la ligne, et des copies d'utilisation de cette valeur maximale pour faire respecter ce qui est inclus dans au plus une de ces colonnes . $S$

Nous pouvons transformer cette contrainte «choisir au plus une» en une contrainte «choisir exactement une» en utilisant toute valeur positive inférieure à 1 comme valeur «non maximale». En effet, chaque ligne appartient à une partie de la partition de ligne, et si alors la RHS de l'inégalité devient négative pour la ligne , il n'y a donc aucun moyen de la satisfaire: donc au moins un doit être forcé dans tel que . $i$ $K_j$ $a_{ij} < 1$ $i$ $j$ $S$ $a_{ij} \ge 1$

Donc, pour vous assurer que l'une des colonnes d'un ensemble est forcée dans , créez une ligne comme suit: $T \subseteq N$ $S$ $a_i$

Set pour chaque . $a_{ij} = n+1$ $j \in T$
Réglez pour chaque autre . $a_{ij} = 0.5$ $j$

Ainsi, la réduction de la couverture exacte est simple: il y a une ligne pour chaque élément, une colonne pour chaque ensemble, avec chaque fois que l'ensemble comprend l'élément et sinon. Les deux directions ("L'instance EC d'entrée est une instance YES instance construite du problème OP est une instance YES", et "L'instance construite du problème OP est une instance YES une instance EC d'entrée est une instance YES") sont clairs. $a_{ij} = n+1$ $j$ $i$ $a_{ij} = 0.5$ $\implies$ $\implies$

j_random_hacker
la source

L' exemple vous avez donné, je pense, a une solution de .

2 \times 2

$2\times2$

S = {2}

$S=\{2\}$

drzbir

J'ai et . Donc mon inégalité est pour . Parce que l'inégalité doit être valable pour tous les .

S = {2}

$S=\{2\}$

K_{2} = K = {1, 2}

$K_2=K=\{1,2\}$

0 ⩽ a_{i 2} - 1

$0\leqslant a_{i2}-1$

i \in K_{2} = {1, 2}

$i\in K_2=\{1,2\}$

i \in K_{j}

$i\in K_j$

drzbir

Tu as raison, désolé. Je vais le réparer maintenant.

j_random_hacker

J'ai écrit ce problème sous forme de programme entier et je l'ai résolu. Maintenant, je dois le résoudre avec un algorithme gourmand (mieux, un algorithme avec une garantie de performance). Comme vous l'avez suggéré, j'ai cherché un saut de couverture exact pour trouver des idées sur la façon de concevoir un bon algorithme pour cela. As tu des idées?

drzbir

C'est NP-difficile, donc presque certainement aucun algorithme poly-temps n'existe. J'essaierais de vérifier toutes les colonnes simples, toutes les paires de colonnes, tous les triplets, etc. jusqu'à ce que vous trouviez un ensemble satisfaisant. Le sous-problème que vous devez résoudre pour chaque ligne (à savoir, décider quel élément de choisir pour cette ligne) est facile.

S

$S$

j_random_hacker