Considérons un vecteur de variables et un ensemble de contraintes linéaires spécifiées par .X⃗ X→\vec{x}A x⃗ ≤ bUNEX→≤bA\vec{x}\leq b En outre, considérons deux polytopes
Considérons l' espace à nnn dimensions {0,1}n{0,1}n\{0,1\}^n , et soit ccc une contrainte linéaire de la forme a1x1+a2x2+a3x3+ ... +an−1xn−1+anxn≥ka1x1+a2x2+a3x3+ ... +an−1xn−1+anxn≥ka_1x_1 + a_2x_2 + a_3x_3 +\ ...\ + a_{n-1}x_{n-1} + a_nx_n \geq k , où ai∈Rai∈Ra_i \in \mathbb{R} , et k ∈ R...
Dans l'article Randomized Primal-Dual analysis of RANKING for Online Bipartite Matching , tout en prouvant que l'algorithme RANKING est -concurrentiel, les auteurs montrent que le dual est réalisable en attente (voir Lemme 3 page 5). Ma question est:( 1 - 1e)(1-1e)\left(1 - \frac{1}{e}\right)...
Je suis intéressé par l'implémentation de SM pour la tâche LP, mais j'ai entendu parler d'éventuels pièges: le livre de Cormen dit qu'il est possible d'avoir des données d'entrée qui feront que l'implémentation naïve se comportera en temps exponentiel. J'ai également entendu que l'implémentation...
J'ai écrit une implémentation de l'algorithme de Kuhn-Munkres pour le problème de correspondance parfaite bipartite de poids minimum basé sur des notes de cours que j'ai trouvées ici et là sur le web. Cela fonctionne vraiment bien, même sur des milliers de sommets. Et je suis d'accord que la...
L'algorithme hongrois est un algorithme d'optimisation combinatoire qui résout le problème d'appariement bipartite de poids maximum en temps polynomial et a anticipé le développement ultérieur de l'importante méthode primal-dual . L'algorithme a été développé et publié par Harold Kuhn en 1955, qui...
Est-il difficile de trouver la solution la plus simple à un système d'équations linéaires? Plus formellement, considérons le problème de décision suivant: Instance: Un système d'équations linéaires avec des coefficients entiers et un nombre ccc . Question: Existe-t-il une solution au système avec...
J'ai essayé la relaxation LP suivante de l'ensemble indépendant maximum max∑iximax∑ixi\max \sum_i x_i s.t. xi+xj≤1 ∀(i,j)∈Es.t. xi+xj≤1 ∀(i,j)∈E\text{s.t.}\ x_i+x_j\le 1\ \forall (i,j)\in E xi≥0xi≥0x_i\ge 0 J'obtiens 1/21/21/2 pour chaque variable pour chaque graphique non bipartite cubique que...
Tout en essayant de résoudre un problème, j'ai fini par en exprimer une partie comme le programme linéaire entier suivant. Ici sont tous des entiers positifs donnés dans le cadre de l'entrée. Un sous-ensemble spécifié des variables x i j est mis à zéro, et le reste peut prendre des valeurs...
L'algorithme simplex est souvent traité soit dans l'arithmétique réelle, soit dans le monde discret avec des calculs exacts. Cependant, il semble être implémenté le plus souvent avec une arithmétique à virgule flottante. Cela conduit à se demander si l'algorithme simplex doit être considéré comme...
Le célèbre article de 1983 de H. Lenstra Integer Programming With A Fixed Number Of Variables indique que les programmes entiers avec un nombre fixe de variables peuvent être résolus dans le polynôme temporel dans la longueur des données. J'interprète cela comme suit. La programmation entière en...
La programmation linéaire est, bien sûr, de nos jours très bien comprise. Nous avons beaucoup de travail qui caractérise la structure des solutions réalisables et la structure des solutions optimales. Nous avons la forte dualité, les algorithmes poly-temps, etc. Mais que sait- on des solutions...
J'ai le LP suivant: / * Fonction objectif * / min: 1 w + 2 x + 0,5 y + z; / * Limites variables * / w + x <= T1; w + y = U1; x + z = U2; T1 = 50; U1 = 70; U2 = 25; Dans ce cas, U1 + U2> T1 et la solution optimale est y = 70 et z = 25. Je veux appliquer la condition d'attribution de valeurs...
J'ai une question de faisabilité qui peut être formulée comme suit. On me donne un point dans un espace vectoriel dimensionnel, et je veux trouver le point le plus proche de qui satisfait un ensemble de " contraintes" de la formed q p ℓ 0pppdddqqqpppℓ0ℓ0\ell_0 Étant donné un ensemble , au plus l'un...
Le relâchement complémentaire (CS) est couramment enseigné lorsque l'on parle de dualité. Il établit une belle relation entre la primale et la double contrainte / variables d'un point de vue mathématique. Les deux principales raisons d'appliquer CS (comme enseigné dans les cours d'études...
Disons que nous avons un polyèdre sous forme standard: Ax=bx≥0Ax=bx≥0\begin{equation*} \begin{array}{rl} \mathbf{A}\mathbf{x} = \mathbf{b} \\\\ \mathbf{x} \ge 0 \end{array} \end{equation*} Existe-t-il des méthodes connues pour trouver un hyperplan qui divise le polyèdre de manière à ce que le...
Je connais les programmes linéaires dans la mesure où ils peuvent résoudre des problèmes avec des fonctions objectives linéaires et des contraintes linéaires. Mais qu'est-ce que la programmation semi-définie peut résoudre que la programmation linéaire ne peut pas? Je sais déjà que les programmes...
J'ai commencé à m'intéresser à l'optimisation mathématique assez récemment et je l'adore. Il semble que beaucoup de problèmes d'optimisation peuvent être facilement exprimés et résolus sous forme de programmes linéaires (par exemple, flux de réseau, couverture de bord / sommet, vendeur itinérant,...
Par le titre, outre l'utilisation d'un solveur LP à usage général, existe-t-il une approche pour résoudre les systèmes d'inégalités sur les variables où les inégalités ont la forme ? Qu'en est-il du cas particulier des inégalités qui forment un ordre total sur les sommes des membres de l'ensemble...
Il y a un programme linéaire pour lequel je veux non seulement une solution mais une solution aussi centrale que possible sur la face du polytope qui assume la valeur minimale. A priori, nous nous attendons à ce que la face minimisante soit de grande dimension pour diverses raisons, notamment que...