Programmation en nombres entiers - Integer programming

Un problème de programmation en nombres entiers est un programme d' optimisation mathématique ou de faisabilité dans lequel certaines ou toutes les variables sont limitées à des nombres entiers . Dans de nombreux contextes, le terme fait référence à la programmation linéaire en nombres entiers (ILP), dans laquelle la fonction objectif et les contraintes (autres que les contraintes d'entiers) sont linéaires .

La programmation en nombres entiers est NP-complète . En particulier, le cas particulier de la programmation linéaire en nombres entiers 0-1, dans laquelle les inconnues sont binaires, et seules les restrictions doivent être satisfaites, est l'un des 21 problèmes NP-complets de Karp .

Si certaines variables de décision ne sont pas discrètes, le problème est appelé problème de programmation en nombres entiers mixtes .

Forme canonique et standard pour les ILP

En programmation linéaire en nombres entiers, la forme canonique est distincte de la forme standard . Un programme linéaire entier sous forme canonique s'exprime ainsi (notons que c'est le vecteur qui est à décider) : ${\displaystyle \mathbf {x} }$

${\displaystyle {\begin{aligned}&{\text{maximize}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} \leq \mathbf {b} ,\\&&&\mathbf {x} \geq \mathbf {0} ,\\&{\text{and}}&&\mathbf {x} \in \mathbb {Z} ^{n},\end{aligné}}}$

et un ILP sous forme standard est exprimé comme

${\displaystyle {\begin{aligned}&{\text{maximize}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} +\mathbf {s} =\mathbf {b} ,\\&&&\mathbf {s} \geq \mathbf {0} ,\\&&&\mathbf {x} \geq \mathbf {0} ,\\ &{\text{and}}&&\mathbf {x} \in \mathbb {Z} ^{n},\end{aligned}}}$

où sont des vecteurs et est une matrice, où toutes les entrées sont des nombres entiers. Comme avec les programmes linéaires, les ILP non sous forme standard peuvent être convertis en forme standard en éliminant les inégalités, en introduisant des variables d'écart ( ) et en remplaçant les variables qui ne sont pas contraintes de signe par la différence de deux variables contraintes de signe ${\displaystyle \mathbf {c} ,\mathbf {b} }$${\style d'affichage A}$${\displaystyle \mathbf {s} }$

Exemple

Le graphique de droite montre le problème suivant.

${\displaystyle {\begin{aligned}\max &{\text{ }}y\\-x+y&\leq 1\\3x+2y&\leq 12\\2x+3y&\leq 12\\x,y&\ geq 0\\x,y&\in \mathbb {Z} \end{aligned}}}$

Les points entiers réalisables sont indiqués en rouge et les lignes pointillées rouges indiquent leur enveloppe convexe, qui est le plus petit polyèdre convexe qui contient tous ces points. Les lignes bleues ainsi que les axes de coordonnées définissent le polyèdre de la relaxation LP, qui est donné par les inégalités sans la contrainte d'intégralité. Le but de l'optimisation est de déplacer la ligne pointillée noire aussi loin vers le haut tout en touchant toujours le polyèdre. Les solutions optimales du problème entier sont les points et qui ont tous deux une valeur objective de 2. L'optimum unique de la relaxation est de valeur objective de 2,8. Si la solution de la relaxation est arrondie aux entiers les plus proches, ce n'est pas faisable pour l'ILP. ${\style d'affichage (1,2)}$${\style d'affichage (2,2)}$${\style d'affichage (1.8,2.8)}$

Preuve de dureté NP

Ce qui suit est une réduction de la couverture minimale des sommets à la programmation en nombres entiers qui servira de preuve de la NP-dureté.

Soit un graphe non orienté. Définissez un programme linéaire comme suit : ${\style d'affichage G=(V,E)}$

${\displaystyle {\begin{aligned}\min \sum _{v\in V}y_{v}\\y_{v}+y_{u}&\geq 1&&\forall uv\in E\\y_{v }&\geq 0&&\forall v\in V\\y_{v}&\in \mathbb {Z} &&\forall v\in V\end{aligned}}}$

Étant donné que les contraintes se limitent à 0 ou à 1, toute solution réalisable du programme en nombres entiers est un sous-ensemble de sommets. La première contrainte implique qu'au moins un point d'extrémité de chaque arête soit inclus dans ce sous-ensemble. Par conséquent, la solution décrit une couverture de sommet. De plus, étant donné une certaine couverture de sommet C, peut être défini sur 1 pour tout et sur 0 pour tout, ce qui nous donne ainsi une solution réalisable pour le programme entier. Ainsi, nous pouvons conclure que si nous minimisons la somme de nous avons également trouvé la couverture de sommet minimale. ${\style d'affichage y_{v}}$${\style d'affichage y_{v}}$${\displaystyle v\en C}$${\displaystyle v\pas \in C}$${\style d'affichage y_{v}}$

Variantes

La programmation linéaire en nombres entiers mixtes ( MILP ) implique des problèmes dans lesquels seules certaines des variables, , sont contraintes d'être des nombres entiers, tandis que d'autres variables sont autorisées à être des non-entiers. ${\style d'affichage x_{i}}$

La programmation linéaire zéro-un (ou programmation en nombres entiers binaires ) implique des problèmes dans lesquels les variables sont limitées à 0 ou 1. Toute variable entière bornée peut être exprimée comme une combinaison de variables binaires. Par exemple, étant donné une variable entière, , la variable peut être exprimée à l'aide de variables binaires : ${\style d'affichage 0\leq x\leq U}$${\displaystyle \lfloor \log _{2}U\rfloor +1}$

${\displaystyle x=x_{1}+2x_{2}+4x_{3}+\cdots +2^{\lfloor \log _{2}U\rfloor }x_{\lfloor \log _{2}U\ étage +1}.}$

Applications

Il y a deux raisons principales d'utiliser des variables entières lors de la modélisation de problèmes en tant que programme linéaire :

1. Les variables entières représentent des quantités qui ne peuvent être que des entiers. Par exemple, il n'est pas possible de construire 3,7 voitures.
2. Les variables entières représentent des décisions (par exemple, s'il faut inclure une arête dans un graphique ) et ne devraient donc prendre que la valeur 0 ou 1.

Ces considérations se produisent fréquemment dans la pratique et la programmation linéaire en nombres entiers peut donc être utilisée dans de nombreux domaines d'application, dont certains sont brièvement décrits ci-dessous.

La planification de la production

La programmation en nombres entiers mixtes a de nombreuses applications dans les productions industrielles, y compris la modélisation d'ateliers. Un exemple important se produit dans la planification de la production agricole consiste à déterminer le rendement de la production pour plusieurs cultures qui peuvent partager des ressources (par exemple, terre, main-d'œuvre, capital, semences, engrais, etc.). Un objectif possible est de maximiser la production totale, sans dépasser les ressources disponibles. Dans certains cas, cela peut être exprimé en termes de programme linéaire, mais les variables doivent être contraintes à être des nombres entiers.

Planification

Ces problèmes impliquent la planification des services et des véhicules dans les réseaux de transport. Par exemple, un problème peut impliquer d'affecter des bus ou des métros à des itinéraires individuels afin qu'un horaire puisse être respecté, et également de les équiper de chauffeurs. Ici, les variables de décision binaires indiquent si un bus ou un métro est affecté à un itinéraire et si un conducteur est affecté à un train ou à un métro particulier. La technique de programmation zéro-un a été appliquée avec succès pour résoudre un problème de sélection de projets dans lequel les projets sont mutuellement exclusifs et/ou technologiquement interdépendants. Il est utilisé dans un cas particulier de programmation en nombres entiers, dans lequel toutes les variables de décision sont des nombres entiers. Il peut prendre les valeurs zéro ou un.

Cloisonnement territorial

Le problème de cloisonnement territorial ou d'arrondissement consiste à cloisonner une région géographique en quartiers afin de planifier certaines opérations en tenant compte de différents critères ou contraintes. Certaines exigences pour ce problème sont : la contiguïté, la compacité, l'équilibre ou l'équité, le respect des limites naturelles et l'homogénéité socio-économique. Certaines applications pour ce type de problème comprennent : les circonscriptions politiques, les circonscriptions scolaires, les circonscriptions des services de santé et les circonscriptions de gestion des déchets.

Réseaux de télécommunications

Le but de ces problèmes est de concevoir un réseau de lignes à installer de sorte qu'un ensemble prédéfini d'exigences de communication soit satisfait et que le coût total du réseau soit minimal. Cela nécessite d'optimiser à la fois la topologie du réseau et le paramétrage des capacités des différentes lignes. Dans de nombreux cas, les capacités sont contraintes d'être des quantités entières. Il existe généralement, selon la technologie utilisée, des restrictions supplémentaires qui peuvent être modélisées sous forme d'inégalités linéaires avec des variables entières ou binaires.

Réseaux cellulaires

La tâche de planification des fréquences dans les réseaux mobiles GSM consiste à répartir les fréquences disponibles sur les antennes afin que les utilisateurs puissent être servis et que les interférences soient minimisées entre les antennes. Ce problème peut être formulé comme un programme linéaire entier dans lequel des variables binaires indiquent si une fréquence est attribuée à une antenne.

Autres applications

• Correspondance des flux de trésorerie
• Optimisation du système énergétique
• Guidage par drone

Algorithmes

La manière naïve de résoudre un ILP consiste simplement à supprimer la contrainte selon laquelle x est un entier, à résoudre le LP correspondant (appelé relaxation LP de l'ILP), puis à arrondir les entrées de la solution à la relaxation LP. Mais, non seulement cette solution peut ne pas être optimale, elle peut même ne pas être réalisable ; c'est-à-dire qu'il peut violer une certaine contrainte.

Utilisation de l'unimodularité totale

Alors qu'en général, la solution à la relaxation LP ne sera pas garantie d'être intégrale, si l'ILP a la forme telle que où et ont toutes les entrées entières et est totalement unimodulaire , alors chaque solution réalisable de base est intégrale. Par conséquent, la solution renvoyée par l' algorithme du simplexe est garantie d'être intégrale. Pour montrer que toute solution réalisable de base est intégrale, soit une solution réalisable de base arbitraire . Puisque c'est faisable, nous le savons . Soient les éléments correspondant aux colonnes de base pour la solution de base . Par définition d'une base, il existe une sous - matrice carrée de avec des colonnes linéairement indépendantes telles que . ${\displaystyle \max \mathbf {c} ^{\mathrm {T} }\mathbf {x} }$${\displaystyle A\mathbf {x} =\mathbf {b} }$${\style d'affichage A}$${\displaystyle \mathbf {b} }$${\style d'affichage A}$${\displaystyle \mathbf {x} }$${\displaystyle \mathbf {x} }$${\displaystyle A\mathbf {x} =\mathbf {b} }$${\displaystyle \mathbf {x} _{0}=[x_{n_{1}},x_{n_{2}},\cdots ,x_{n_{j}}]}$${\displaystyle \mathbf {x} }$${\style d'affichage B}$${\style d'affichage A}$${\displaystyle B\mathbf {x} _{0}=\mathbf {b} }$

Puisque les colonnes de sont linéairement indépendantes et carrées, est non singulier, et donc par hypothèse, est unimodulaire et donc . De plus, étant donné qu'il n'est pas singulier, il est inversible et donc . Par définition, . Dénote ici l' adjugate de et est intégral car est intégral. Par conséquent, ${\style d'affichage B}$${\style d'affichage B}$${\style d'affichage B}$${\style d'affichage B}$${\displaystyle \det(B)=\pm 1}$${\style d'affichage B}$${\displaystyle \mathbf {x} _{0}=B^{-1}\mathbf {b} }$${\displaystyle B^{-1}={\frac {B^{adj}}{\det(B)}}=\pm B^{adj}}$${\displaystyle B^{adj}}$${\style d'affichage B}$${\style d'affichage B}$

${\displaystyle {\begin{aligned}&\Rightarrow B^{-1}=\pm B^{adj}{\text{ est intégral.}}\\&\Rightarrow x_{0}=B^{-1 }b{\text{ est intégral.}}\\&\Rightarrow {\text{Chaque solution réalisable de base est intégrale.}}\end{aligned}}}$

Ainsi, si la matrice d'un ILP est totalement unimodulaire, plutôt que d'utiliser un algorithme ILP, la méthode du simplexe peut être utilisée pour résoudre la relaxation LP et la solution sera entière. ${\style d'affichage A}$

Algorithmes exacts

Lorsque la matrice n'est pas totalement unimodulaire, il existe une variété d'algorithmes qui peuvent être utilisés pour résoudre exactement les programmes linéaires entiers. Une classe d'algorithmes est constituée de méthodes de plan de coupe qui fonctionnent en résolvant la relaxation LP, puis en ajoutant des contraintes linéaires qui conduisent la solution à être un nombre entier sans exclure de points entiers réalisables. ${\style d'affichage A}$

Une autre classe d'algorithmes est constituée de variantes de la méthode branch and bound . Par exemple, la méthode de branchement et de coupe qui combine à la fois les méthodes de branchement et de limite et de plan de coupe. Les algorithmes de branchement et de limite présentent un certain nombre d'avantages par rapport aux algorithmes qui n'utilisent que des plans de coupe. Un avantage est que les algorithmes peuvent être terminés plus tôt et tant qu'au moins une solution intégrale a été trouvée, une solution réalisable, bien que pas nécessairement optimale, peut être retournée. De plus, les solutions des relaxations LP peuvent être utilisées pour fournir une estimation dans le pire des cas de l'éloignement de l'optimalité de la solution renvoyée. Enfin, les méthodes branch and bound peuvent être utilisées pour renvoyer plusieurs solutions optimales.

Algorithmes exacts pour un petit nombre de variables

Supposons est un m de n matrice de nombre entier et est un m -en-1 vecteur entier. Nous nous concentrons sur le problème de faisabilité, qui est de décider s'il existe un vecteur n -par-1 satisfaisant . ${\style d'affichage A}$${\displaystyle \mathbf {b} }$${\displaystyle \mathbf {x} }$${\displaystyle A\mathbf {x} \leq \mathbf {b} }$

Soit V la valeur absolue maximale des coefficients dans et . Si n (le nombre de variables) est une constante fixe, alors le problème de faisabilité peut être résolu en temps polynomial en m et log V . Ceci est trivial pour le cas n =1. Le cas n = 2 a été résolu en 1981 par Herbert Scarf . Le cas général a été résolu en 1983 par Hendrik Lenstra , combinant les idées de Laszlo Lovasz et Peter van Emde Boas . ${\style d'affichage A}$${\displaystyle \mathbf {b} }$

Dans le cas particulier de 0-1 ILP, l'algorithme de Lenstra est équivalent à une énumération complète : le nombre de toutes les solutions possibles est fixe (2 ⁿ ), et la vérification de la faisabilité de chaque solution peut se faire en temps poly( m , log V ) . Dans le cas général, où chaque variable peut être un entier arbitraire, une énumération complète est impossible. Ici, l'algorithme de Lenstra utilise des idées de la géométrie des nombres . Il transforme le problème original en un problème équivalent avec la propriété suivante : soit l'existence d'une solution est évidente, soit la valeur de (la n- ième variable) appartient à un intervalle dont la longueur est bornée par une fonction de n . Dans ce dernier cas, le problème est réduit à un nombre borné de problèmes de dimension inférieure. ${\displaystyle \mathbf {x} }$${\style d'affichage x_{n}}$

L'algorithme de Lenstra implique que l'ILP est résoluble en temps polynomial également dans le cas dual, dans lequel n varie mais m (le nombre de contraintes) est constant.

L'algorithme de Lenstra a ensuite été amélioré par Kannan et Frank et Tardos. L'exécution améliorée est , où est le nombre de bits d'entrée, qui est dans . ${\displaystyle n^{2.5n}\cdot \ell }$${\style d'affichage \ell }$${\displaystyle {\text{poly}}(m,\log {V})}$

Méthodes heuristiques

Étant donné que la programmation linéaire en nombres entiers est NP-difficile , de nombreuses instances de problèmes sont insolubles et des méthodes heuristiques doivent donc être utilisées à la place. Par exemple, la recherche tabou peut être utilisée pour rechercher des solutions aux ILP. Pour utiliser la recherche taboue pour résoudre les ILP, les déplacements peuvent être définis comme l'incrémentation ou la décrémentation d'une variable contrainte par un entier d'une solution réalisable tout en gardant constantes toutes les autres variables contraintes par un entier. Les variables non restreintes sont ensuite résolues pour. La mémoire à court terme peut consister en des solutions déjà essayées tandis que la mémoire à moyen terme peut consister en des valeurs pour les variables entières contraintes qui ont abouti à des valeurs objectives élevées (en supposant que l'ILP est un problème de maximisation). Enfin, la mémoire à long terme peut guider la recherche vers des valeurs entières qui n'ont pas été essayées auparavant.

D'autres méthodes heuristiques qui peuvent être appliquées aux ILP incluent

• Escalade
• Recuit simulé
• Optimisation de la recherche réactive
• Optimisation des colonies de fourmis
• Réseaux de neurones Hopfield

Il existe également une variété d'autres heuristiques spécifiques au problème, telles que l' heuristique k-opt pour le problème du voyageur de commerce. Un inconvénient des méthodes heuristiques est que si elles ne parviennent pas à trouver une solution, il est impossible de déterminer si c'est parce qu'il n'y a pas de solution réalisable ou si l'algorithme n'a tout simplement pas pu en trouver une. De plus, il est généralement impossible de quantifier à quel point une solution optimale renvoyée par ces méthodes est proche.

Programmation d'entiers clairsemés

Il arrive souvent que la matrice qui définit le programme en nombres entiers soit creuse . En particulier, cela se produit lorsque la matrice a une structure par blocs, ce qui est le cas dans de nombreuses applications. La parcimonie de la matrice peut être mesurée comme suit. Le graphique de a des sommets correspondant aux colonnes de , et deux colonnes forment une arête si a une ligne où les deux colonnes ont des entrées non nulles. De manière équivalente, les sommets correspondent à des variables, et deux variables forment une arête si elles partagent une inégalité. La mesure de parcimonie de est le minimum entre la profondeur de l' arbre du graphe de et la profondeur de l' arbre du graphe de la transposition de . Soit la mesure numérique de définie comme la valeur absolue maximale de toute entrée de . Soit le nombre de variables du programme d'entiers. Ensuite, il a été montré en 2018 que la programmation en nombres entiers peut être résolue en temps traitable fortement polynomial et à paramètres fixes paramétré par et . C'est-à-dire que pour certaines fonctions calculables et certaines constantes , la programmation en nombres entiers peut être résolue en temps . En particulier, le temps est indépendant du membre de droite et de la fonction objectif . De plus, contrairement au résultat classique de Lenstra, où le nombre de variables est un paramètre, ici le nombre de variables est une partie variable de l'entrée. ${\style d'affichage A}$${\style d'affichage A}$${\style d'affichage A}$${\style d'affichage A}$ ${\style d'affichage d}$${\style d'affichage A}$${\style d'affichage A}$${\style d'affichage A}$${\style d'affichage a}$${\style d'affichage A}$${\style d'affichage A}$${\style d'affichage n}$${\style d'affichage a}$${\style d'affichage d}$${\style d'affichage f}$${\style d'affichage k}$${\style d'affichage f(a,d)n^{k}}$${\style d'affichage b}$${\style d'affichage c}$${\style d'affichage n}$${\style d'affichage n}$

Voir également

• moindres carrés contraints

Les références

Lectures complémentaires

• George L. Nemhauser ; Laurence A. Wolsey (1988). Optimisation entière et combinatoire . Wiley. ISBN 978-0-471-82819-8.
• Alexandre Schrijver (1998). Théorie de la programmation linéaire et en nombres entiers . John Wiley et fils. ISBN 978-0-471-98232-6.
• Laurence A. Wolsey (1998). Programmation en nombres entiers . Wiley. ISBN 978-0-471-28366-9.
• Dimitris Bertsimas ; Robert Weismantel (2005). Optimisation sur des entiers . Idées dynamiques. ISBN 978-0-9759146-2-5.
• John K. Karlof (2006). Programmation en nombres entiers : théorie et pratique . Presse CRC. ISBN 978-0-8493-1914-3.
• H. Paul Williams (2009). Programmation logique et en nombres entiers . Springer. ISBN 978-0-387-92279-9.
• Michael Junger; Thomas M. Liebling ; Denis Naddef ; George Nemhauser ; William R. Poulieblank ; Gerhard Reinelt; Giovanni Rinaldi ; Laurence A. Wolsey, éd. (2009). 50 ans de programmation en nombres entiers 1958-2008 : des premières années à l'état de l'art . Springer. ISBN 978-3-540-68274-5.
• Der-San Chen ; Robert G. Batson ; Yu Dang (2010). Programmation en nombres entiers appliquée : modélisation et solution . John Wiley et fils. ISBN 978-0-470-37306-4.
• Gérard Sierksma ; Yori Zwols (2015). Optimisation linéaire et entière : théorie et pratique . Presse CRC. ISBN 978-1-498-71016-9.

Liens externes

• Un tutoriel sur la programmation en nombres entiers
• Programmation d'entiers de conférence et optimisation combinatoire, IPCO
• L'atelier d'optimisation combinatoire d'Aussois