Minimiser la composante maximale d'une somme de vecteurs

J'aimerais apprendre quelque chose sur ce problème d'optimisation: pour des nombres entiers non négatifs donnés $a_{i,j,k}$ , trouver une fonction $f$ minimisant l'expression

max_{k} \sum_{i} a_{i, f (i), k}

$\max_k \sum_i a_{i,f(i),k}$

Un exemple utilisant une formulation différente pourrait le rendre plus clair: on vous donne un ensemble d'ensembles de vecteurs comme

{
    {(3, 0, 0, 0, 0), (1, 0, 2, 0, 0)},
    {(0, 1, 0, 0, 0), (0, 0, 0, 1, 0)},
    {(0, 0, 0, 2, 0), (0, 1, 0, 1, 0)}
}

Choisissez un vecteur dans chaque ensemble, de sorte que la composante maximale de leur somme soit minimale. Par exemple, vous pouvez choisir

(1, 0, 2, 0, 0) + (0, 1, 0, 0, 0) + (0, 1, 0, 1, 0) = (1, 1, 2, 1, 0)

avec la composante maximale égale à 2, ce qui est clairement optimal ici.

Je suis curieux de savoir s'il s'agit d'un problème bien connu et des méthodes de résolution approximative spécifiques au problème disponibles. Il doit être rapide et facile à programmer (pas de solveur ILP , etc.). Aucune solution exacte n'est nécessaire car ce n'est qu'une approximation du problème réel.

Je vois que j'aurais dû ajouter quelques détails sur les instances de problème qui m'intéressent:

$i \in \{0, 1, \ldots, 63\}$ , c'est-à-dire qu'il y a toujours 64 lignes (lorsqu'elles sont écrites comme dans l'exemple ci-dessus).
$j \in \{0, 1\}$ , c'est-à-dire qu'il n'y a que 2 vecteurs par ligne.
$k \in \{0, 1, \ldots, N-1\}$ où (la longueur du vecteur) est compris entre 10 et 1000. $N$

De plus, sur chaque ligne, la somme des éléments de tous les vecteurs est la même, c'est-à-dire

\forall i, j, j^{'} : \sum_{k} a_{i, j, k} = \sum_{k} a_{i, j^{'}, k}

$\forall i, j, j':\quad \sum_k a_{i,j,k} = \sum_k a_{i,j',k}$

et la somme des éléments du vecteur somme est inférieure à sa longueur, c'est-à-dire,

\sum_{k} \sum_{i} a_{i, f (i), k} < N

$\sum_k \sum_i a_{i,f(i),k} < N$

algorithms optimization linear-programming maaartinus
la source

Il n'est pas difficile de réduire le problème des 3 partitions à votre problème. Cela signifie que votre problème est NP-complet même si les nombres sont donnés en unaire, ce qui exclut l'une des approches courantes pour un algorithme d'approximation.

Tsuyoshi Ito

Merci pour les corrections et merci à @Tsuyoshi Ito pour la perspicacité. Si je comprends bien, la restriction à deux vecteurs par ligne (que j'ai oublié de mentionner) invalide la réduction et peut rendre le problème beaucoup plus facile.

maaartinus

Vous avez raison, la réduction du problème des 3 partitions auquel je pensais ne fonctionne pas s'il n'y a que deux vecteurs par ligne.

Tsuyoshi Ito

Il y a donc combinaisons à comparer?

j^{i}

$j^i$

Jason Kleban

@ uosɐſ: Pour être précis, il existe combinaisons possibles, où est le nombre de possibilités pour et est le nombre de possibilités pour .

J^{I} = 2^{64}

$J^I=2^{64}$

J = 2

$J=2$

j

$j$

I = 64

$I=64$

i

$i$

maaartinus

Réponses:

Réduction de 3SAT à la version à deux vecteurs: étant donné une formule, laissez indexer les variables, et clauses d'index. Soit le nombre de fois que la variable apparaît positivement (si ) ou négativement (si ) dans la clause . OPT est inférieur à si la formule est satisfaisable (la bijection est évidente). $i$ $j \in \{0,1\}$ $k$ $a_{i,j,k}$ $i$ $j = 0$ $j = 1$ $k$ $3$

Comment j'attaquerais ce problème: une grande recherche de quartier. Commencez avec n'importe quelle solution. Choisissez lignes au hasard. Utilisez la force brute pour trouver la meilleure solution où ne peut changer que sur ces lignes - très faisable même pour modéré étant donné que la taille du problème est de lignes. Répéter. $r$ $f$ $k$ $64$

salut les mods
la source

C'est une belle réduction. Je ne sais pas pourquoi il n'a pas de votes positifs. Quoi qu'il en soit, voici mon +1.

Tsuyoshi Ito

Je pense que vous devriez en dire un peu plus sur la réduction. En particulier, vous avez bien caché, peut - être trop bien, car il rend le bijection difficile de voir un peu.

f

$f$

Raphael

Nous ne pouvons pas discuter de la complexité d'un problème lorsque la taille du problème est fixée à une constante, car (la majeure partie de) la théorie de la complexité traite du comportement asymptotique de la complexité du problème car la taille du problème tend vers l'infini. Ici, je considère le nombre de lignes et la dimension des vecteurs comme des variables.

Le problème est alors NP-complet même si les nombres dans l'entrée sont donnés en unaire. Ce n'est pas une réponse à votre question parce que vous posez des questions sur l'approximation, mais c'est quelque chose.

Définissez le problème avec rigueur:

Instance : n paires de vecteurs a _i , b _i ∈ ℕ ^m ( i ∈ {1,…, n }) et K ∈ ℕ, tous en unaire.
Question : Pouvons-nous choisir soit a _i soit b _i pour chaque i afin que la somme de ces n vecteurs ait au plus K dans chaque coordonnée?

Voici un problème connu NP-complet appelé 3-partition :

Instance à 3 partitions : B ∈ ℕ, et 3 k entiers c ₁ ,…, c _{3 k} entre B / 4 et B / 2, exclusifs, tels que ∑ _{i = 1}^{3 k} c _i = kB , le tout en unaire.
Question : Le multiset { c ₁ ,…, c _{3 k} } peut-il être partitionné en k multisets S ₁ ,…, S _{k de} telle sorte que la somme de chaque S _j soit égale àB ?

Étant donné une instance ( B ; c ₁ ,…, c _{3 k} ) du problème à 3 partitions, construisez une instance du problème ci-dessus comme suit. Pour chaque i = 1, ..., 3 k et j = 1, ..., k , nous allons construire une paire de 4 k vecteurs de dimension, ce qui représente le choix si c _i appartient à S _j ou non:

Le vecteur représentant le choix « c _i ∈ S _j » n'a qu'une seule entrée non nulle, qui est ( k -1) c _i à la j ème coordonnée.
Le vecteur représentant le choix « c _i ∉ S _j » a également une seule entrée non nulle, qui est B à la ( k + i ) -ième coordonnée.

Il n'est pas difficile de voir que l'instance ( B ; c ₁ ,…, c _{3 k} ) du problème à 3 partitions a une solution si et seulement s'il existe un moyen de choisir un vecteur dans chacun des 3 k ² construits paires de telle sorte que toutes les coordonnées de la somme de ces vecteurs sont au plus ( k - 1) B . (En fait, lorsque cela se produit, toutes les coordonnées de la somme sont égales à ( k -1) B. ) Il s'agit donc d'une réduction du problème des 3 partitions au problème ci-dessus.

Jusqu'à présent, j'ai ignoré les deux contraintes supplémentaires énoncées à la fin de la question, mais les deux sont faciles à appliquer en modifiant légèrement cette réduction. La condition selon laquelle la somme des éléments de chaque vecteur est égale peut être appliquée en ajoutant des coordonnées fictives qui ne contiennent que 0 ou 1. La condition selon laquelle cette somme est inférieure à la dimension peut être appliquée en ajoutant des coordonnées fictives qui ne contiennent que 0.

Tsuyoshi Ito
la source

Belle réponse, juste quelques notes: 1. Je ne me soucie pas de la complexité théorique ici. 2. Le nombre de lignes est fixe et peut le rester, car la variation de suffit. Cela dit, merci beaucoup.

N

$N$

maaartinus