Problème de type LP - LP-type problem

Dans l'étude des algorithmes , un problème de type LP (également appelé programme linéaire généralisé ) est un problème d'optimisation qui partage certaines propriétés avec les programmes linéaires de faible dimension et qui peut être résolu par des algorithmes similaires. Les problèmes de type LP incluent de nombreux problèmes d'optimisation importants qui ne sont pas eux-mêmes des programmes linéaires, comme le problème de trouver le plus petit cercle contenant un ensemble donné de points planaires. Ils peuvent être résolus par une combinaison d' algorithmes aléatoires en un temps linéaire dans le nombre d'éléments définissant le problème, et sous-exponentiel dans la dimension du problème.

Définition

Les problèmes de type LP ont été définis par Sharir & Welzl (1992) comme des problèmes dans lesquels on donne en entrée un ensemble fini S d'éléments, et une fonction f qui mappe des sous-ensembles de S aux valeurs d'un ensemble totalement ordonné. La fonction doit satisfaire deux propriétés clés :

  • Monotonicité: pour deux ensembles A ⊆ B ⊆ S , f ( A ) ≤ f ( B ) ≤ f ( S ).
  • Localité: pour deux ensembles A ⊆ B ⊆ S et tous les éléments x dans S , si f ( A ) = f ( B ) = f ( A ∪ { x }) , alors f ( A ) = f ( B ∪ { x }) .

Une base d'un problème de type LP est un ensemble B ⊆ S avec la propriété que chaque sous-ensemble propre de B a une valeur de f plus petite que B lui-même, et la dimension (ou dimension combinatoire ) d'un problème de type LP est définie comme être la cardinalité maximale d'une base.

On suppose qu'un algorithme d'optimisation ne peut évaluer la fonction f que sur des ensembles qui sont eux-mêmes des bases ou qui sont formés en ajoutant un seul élément à une base. Alternativement, l'algorithme peut être restreint à deux opérations primitives : un test de violation qui détermine, pour une base B et un élément x si f ( B ) = f ( B { x }) , et un calcul de base qui (avec le même entrées) trouve une base de B ∪ { x }. La tâche que l'algorithme doit effectuer est d'évaluer f ( S ) en utilisant uniquement ces évaluations ou primitives restreintes.

Exemples et applications

Boules Lp

Un programme linéaire peut être défini par un système de d variables réelles non négatives , soumises à n contraintes d'inégalité linéaire, ainsi qu'une fonction objectif linéaire non négative à minimiser. Ceci peut être placé dans le cadre des problèmes de type LP en laissant S être l'ensemble des contraintes, et en définissant f ( A ) (pour un sous-ensemble A des contraintes) comme la valeur minimale de la fonction objectif du plus petit programme linéaire défini par A . Avec des hypothèses de position générales appropriées (afin d'éviter que plusieurs points de solution aient la même valeur de fonction objectif optimale), cela satisfait les exigences de monotonie et de localité d'un problème de type LP, et a une dimension combinatoire égale au nombre d de variables. De même, un programme entier (constitué d'un ensemble de contraintes linéaires et d'une fonction objectif linéaire, comme dans un programme linéaire, mais avec la restriction supplémentaire que les variables ne doivent prendre que des valeurs entières) satisfait à la fois les propriétés de monotonie et de localité d'un LP -problème de type, avec les mêmes hypothèses générales de position que pour les programmes linéaires. Les théorèmes de Bell (1977) et Scarf (1977) montrent que, pour un programme entier à d variables, la dimension combinatoire est d'au plus  2 d .

De nombreux problèmes d'optimisation naturelle en géométrie computationnelle sont de type LP :

Image
Problème du plus petit cercle
  • Le problème du plus petit cercle est le problème de trouver le rayon minimum d'un cercle contenant un ensemble donné de n points dans le plan. Il satisfait la monotonie (ajouter plus de points ne peut que rendre le cercle plus grand) et la localité (si le plus petit cercle pour l'ensemble A contient B et x , alors le même cercle contient également B ∪ { x }). Étant donné que le plus petit cercle est toujours déterminé par trois points, le problème du plus petit cercle a une dimension combinatoire trois, même s'il est défini à l'aide de la géométrie euclidienne bidimensionnelle. Plus généralement, la plus petite boule englobante de points en d dimensions forme un problème de type LP de dimension combinatoire d + 1 . Le problème du plus petit cercle peut être généralisé à la plus petite balle enfermant un ensemble de balles, à la plus petite balle qui touche ou entoure chacune d'un ensemble de balles, au problème pondéré à 1 centre ou à des problèmes similaires de balle englobante plus petite en non- Espaces euclidiens tels que l'espace avec des distances définies par la divergence de Bregman . Le problème connexe de trouver le plus petit ellipsoïde englobant est également un problème de type LP, mais avec une dimension combinatoire plus grande, d ( d + 3)/2 .
  • Soit K 0 , K 1 , ... une suite de n ensembles convexes dans l' espace euclidien de dimension d , et supposons que l'on souhaite trouver le plus long préfixe de cette suite qui a un point d'intersection commun. Cela peut être exprimé comme un problème de type LP dans lequel f ( A ) = − i où K i est le premier membre de A qui n'appartient pas à un préfixe d'intersection de A , et où f ( A ) = − n s'il y a n'est pas un tel membre. La dimension combinatoire de ce système est d + 1 .
  • Supposons qu'on nous donne une collection de boîtes rectangulaires alignées sur les axes dans un espace tridimensionnel, et que nous souhaitions trouver une ligne dirigée dans l'octant positif de l'espace qui traverse toutes les boîtes. Cela peut être exprimé comme un problème de type LP avec une dimension combinatoire 4.
  • Le problème de trouver la distance la plus proche entre deux polytopes convexes , spécifié par leurs ensembles de sommets, peut être représenté comme un problème de type LP. Dans cette formulation, l'ensemble S est l'ensemble de tous les sommets des deux polytopes, et la valeur de la fonction f ( A ) est la négation de la plus petite distance entre les enveloppes convexes des deux sous-ensembles A de sommets des deux polytopes. La dimension combinatoire du problème est d + 1 si les deux polytopes sont disjoints, ou d + 2 s'ils ont une intersection non vide.
  • Soit S = { f 0 , f 1 , ... } un ensemble de fonctions quasi convexes . Alors le maximum ponctuel max i f i est lui-même quasi convexe, et le problème de trouver la valeur minimale de max i f i est un problème de type LP. Il a une dimension combinatoire au plus 2 d + 1 , où d est la dimension du domaine des fonctions, mais pour des fonctions suffisamment lisses la dimension combinatoire est plus petite, au plus d + 1 . De nombreux autres problèmes de type LP peuvent également être exprimés en utilisant des fonctions quasi convexes de cette manière ; par exemple, le plus petit problème du cercle englobant est le problème de la minimisation de max i f i où chacune des fonctions f i mesure la distance euclidienne à partir de l'un des points donnés.

Les problèmes de type LP ont également été utilisés pour déterminer les résultats optimaux de certains jeux de la théorie algorithmique des jeux , améliorer le placement des sommets dans les maillages de la méthode des éléments finis , résoudre les problèmes de localisation des installations , analyser la complexité temporelle de certains algorithmes de recherche en temps exponentiel et reconstruire le positions tridimensionnelles des objets à partir de leurs images bidimensionnelles.

Algorithmes

Seidel

Seidel (1991) a donné un algorithme pour la programmation linéaire de faible dimension qui peut être adapté au cadre de problèmes de type LP. L'algorithme de Seidel prend en entrée l'ensemble S et un ensemble séparé X (initialement vide) d'éléments connus pour appartenir à la base optimale. Il considère ensuite les éléments restants un par un dans un ordre aléatoire, en effectuant des tests de violation pour chacun et, en fonction du résultat, en effectuant un appel récursif au même algorithme avec un plus grand ensemble d'éléments de base connus. Il peut être exprimé avec le pseudo-code suivant : 

function seidel(S, f, X) is
    R := empty set
    B := X
    for x in a random permutation of S:
        if f(B) ≠ f(B ∪ {x}):
            B := seidel(R, f, basis(X ∪ {x}))
        R := R ∪ {x}
    return B

Dans un problème de dimension combinatoire d , le test de violation dans la i ième itération de l'algorithme échoue uniquement lorsque x est l' un des d - | X | éléments de base restants, ce qui se produit avec une probabilité au plus ( d − | X |)/ i . Sur la base de ce calcul, on peut montrer que globalement le nombre attendu de tests de violation effectués par l'algorithme est O( d ! n) , linéaire en n mais pire qu'exponentiel en d .

Clarkson

Clarkson (1995) définit deux algorithmes, un algorithme récursif et un algorithme itératif, pour la programmation linéaire basée sur des techniques d'échantillonnage aléatoire, et suggère une combinaison des deux qui appelle l'algorithme itératif à partir de l'algorithme récursif. L'algorithme récursif choisit à plusieurs reprises des échantillons aléatoires dont la taille est approximativement la racine carrée de la taille d'entrée, résout le problème échantillonné de manière récursive, puis utilise des tests de violation pour trouver un sous-ensemble des éléments restants qui doit inclure au moins un élément de base : 

function recursive(S, f) is
    X := empty set
    repeat
        R := a random subset of S with size d√n
        B := basis for R ∪ X, computed recursively
        V := {x | f(B) ≠ f(B ∪ {x})}
        X := X ∪ V
    until V is empty
    return B

À chaque itération, la taille attendue de V est O( √ n ) , et chaque fois que V n'est pas vide, il inclut au moins un nouvel élément de la base éventuelle de S . Par conséquent, l'algorithme effectue à la plupart d itérations, dont chacun effectue n tests de violation et fait un seul appel récursif à un sous - problème de taille O ( d √ n ) .

L'algorithme itératif de Clarkson attribue des poids à chaque élément de S , initialement tous égaux. Il choisit alors un ensemble R de 9 d 2 éléments de S au hasard, et calcule les ensembles B et V comme dans l'algorithme précédent. Si le poids total de V est au plus égal à 2/(9 d − 1) fois le poids total de S (comme cela se produit avec une probabilité constante) alors l'algorithme double les poids de chaque élément de V , et comme avant, il répète ce processus jusqu'à ce que V devient vide. À chaque itération, on peut montrer que le poids de la base optimale augmente plus rapidement que le poids total de S , d'où il s'ensuit que l'algorithme doit se terminer en O(log n ) itérations.

En utilisant l'algorithme récursif pour résoudre un problème donné, en passant à l'algorithme itératif pour ses appels récursifs, puis à nouveau à l'algorithme de Seidel pour les appels effectués par l'algorithme itératif, il est possible de résoudre un problème de type LP donné en utilisant O( dn + d ! d O(1) log n ) tests de violation.

Appliqué à un programme linéaire, cet algorithme peut être interprété comme étant une méthode du simplexe double . Avec certaines primitives de calcul supplémentaires au-delà des primitives de test de violation et de calcul de base, cette méthode peut être rendue déterministe.

Matoušek, Sharir et Welzl

Matoušek, Sharir & Welzl (1996) décrivent un algorithme qui utilise une propriété supplémentaire des programmes linéaires qui n'est pas toujours détenue par d'autres problèmes de type LP, à savoir que toutes les bases ont la même cardinalité les unes par rapport aux autres. Si un problème de type LP n'a pas cette propriété, il peut être fait pour l'avoir en ajoutant d nouveaux éléments factices et en modifiant la fonction f pour retourner le couple ordonné de son ancienne valeur f ( A ) et du nombre min( d ,| A |) , ordonné lexicographiquement .

Plutôt que d'ajouter des éléments de S un par un, ou de trouver des échantillons des éléments, Matoušek, Sharir & Welzl (1996) décrivent un algorithme qui supprime les éléments un par un. A chaque étape il maintient une base C qui peut être initialement l'ensemble des éléments fictifs. Il peut être décrit avec le pseudo-code suivant : 

function msw(S, f, C) is
    if S = C then
        return C
    choose a random element x of S \ C
    B = msw(S \ x, f, C)
    if f(B) ≠ f(B ∪ {x}) then
        B := basis(B ∪ {x})
        B := msw(S, f, B)
    return B

Dans la plupart des appels récursifs de l'algorithme, le test de violation réussit et l'instruction if est ignorée. Cependant, avec une faible probabilité, le test de violation échoue et l'algorithme effectue un calcul de base supplémentaire, puis un appel récursif supplémentaire. Comme le montrent les auteurs, le temps attendu pour l'algorithme est linéaire en n et exponentiel en racine carrée de d log n . En combinant cette méthode avec les procédures récursives et itératives de Clarkson, ces deux formes de dépendance temporelle peuvent être séparées l'une de l'autre, résultant en un algorithme qui effectue des tests de violation de O( dn ) dans l'algorithme récursif externe et un nombre qui est exponentiel dans le racine carrée de d log d dans les niveaux inférieurs de l'algorithme.

Variantes

Optimisation avec valeurs aberrantes

Matoušek (1995) considère une variante des problèmes d'optimisation de type LP dans laquelle on donne, avec l'ensemble S et la fonction objectif f , un nombre k ; la tâche consiste à supprimer k éléments de S afin de rendre la fonction objectif sur l'ensemble restant aussi petite que possible. Par exemple, appliqué au problème du plus petit cercle, cela donnerait le plus petit cercle qui contient tout sauf k d'un ensemble donné de points plans. Il montre que, pour tous les problèmes de type LP non dégénérés (c'est-à-dire les problèmes dans lesquels toutes les bases ont des valeurs distinctes) ce problème peut être résolu en temps O( nk d ) , en résolvant un ensemble de O( k d ) LP -problèmes de type définis par des sous-ensembles de S .

Problèmes implicites

Certains problèmes d'optimisation géométrique peuvent être exprimés comme des problèmes de type LP dans lesquels le nombre d'éléments dans la formulation de type LP est significativement supérieur au nombre de valeurs de données d'entrée pour le problème d'optimisation. À titre d'exemple, considérons une collection de n points dans le plan, chacun se déplaçant à une vitesse constante. A tout instant, le diamètre de ce système est la distance maximale entre deux de ses points. Le problème de trouver un temps auquel le diamètre est minimisé peut être formulé comme minimisant le maximum ponctuel de O( n 2 ) fonctions quasi convexes, une pour chaque paire de points, mesurant la distance euclidienne entre la paire en fonction du temps. Ainsi, il peut être résolu comme un problème de type LP de dimension combinatoire deux sur un ensemble de O( n 2 ) éléments, mais cet ensemble est significativement plus grand que le nombre de points d'entrée.

Chan (2004) décrit un algorithme pour résoudre des problèmes de type LP implicitement définis comme celui-ci dans lequel chaque élément de type LP est déterminé par un k -uplet de valeurs d'entrée, pour une constante k . Afin d'appliquer son approche, il doit exister un algorithme de décision qui peut déterminer, pour une base de type LP donnée B et un ensemble S de n valeurs d'entrée, si B est une base pour le problème de type LP déterminé par S .

L'algorithme de Chan effectue les étapes suivantes :

  • Si le nombre de valeurs d'entrée est inférieur à une valeur seuil, recherchez l'ensemble d'éléments de type LP qu'il détermine et résolvez le problème de type LP explicite résultant.
  • Sinon, partitionnez les valeurs d'entrée en un nombre approprié supérieur à k de sous-ensembles de taille égale S i .
  • Si f est la fonction objectif pour le problème de type LP implicitement défini à résoudre, alors définissez une fonction g qui mappe les collections de sous-ensembles S i à la valeur de f sur l'union de la collection. Alors l'ensemble des sous-ensembles S i et la fonction objectif g définit elle-même un problème de type LP, de même dimension que le problème implicite à résoudre.
  • Résoudre le problème de type LP (explicite) défini par g en utilisant l'algorithme de Clarkson, qui effectue un nombre linéaire de tests de violation et un nombre polylogarithmique d'évaluations de base. Les évaluations de base pour g peuvent être effectuées par des appels récursifs à l'algorithme de Chan, et les tests de violation peuvent être effectués par des appels à l'algorithme de décision.

En supposant que l'algorithme de décision prend un temps O( T ( n )) qui croît au moins polynomialement en fonction de la taille d'entrée n , Chan montre que le seuil de passage à une formulation LP explicite et le nombre de sous-ensembles dans la partition peut être choisi de telle sorte que l'algorithme d'optimisation implicite de type LP s'exécute également dans le temps O( T ( n )) .

Par exemple, pour le diamètre minimum des points mobiles, l'algorithme de décision n'a besoin que de calculer le diamètre d'un ensemble de points à un instant fixe, un problème qui peut être résolu en un temps O( n log n ) en utilisant la technique des compas rotatifs . Par conséquent, l'algorithme de Chan pour trouver le moment auquel le diamètre est minimisé prend également le temps O( n log n ) . Chan utilise cette méthode pour trouver un point de profondeur maximale de Tukey parmi une collection donnée de n points dans l' espace euclidien de dimension d , en temps O( n d − 1 + n log n ) . Une technique similaire a été utilisée par Braß, Heinrich-Litan & Morin (2003) pour trouver un point de profondeur maximale de Tukey pour la distribution uniforme sur un polygone convexe.

Histoire et problèmes connexes

La découverte d'algorithmes de temps linéaire pour la programmation linéaire et l'observation que les mêmes algorithmes pouvaient dans de nombreux cas être utilisés pour résoudre des problèmes d'optimisation géométrique qui n'étaient pas des programmes linéaires remonte au moins à Megiddo ( 1983 , 1984 ), qui a donné un temps linéaire attendu. algorithme pour les programmes linéaires à trois variables et le problème du plus petit cercle. Cependant, Megiddo a formulé la généralisation de la programmation linéaire géométriquement plutôt que combinatoire, comme un problème d' optimisation convexe plutôt que comme un problème abstrait sur les systèmes d'ensembles. De même, Dyer (1986) et Clarkson (dans la version de conférence de 1988 de Clarkson 1995 ) ont observé que leurs méthodes pouvaient être appliquées aussi bien aux programmes convexes qu'aux programmes linéaires. Dyer (1992) a montré que le problème de l'ellipsoïde englobant minimum pouvait également être formulé comme un problème d'optimisation convexe en ajoutant un petit nombre de contraintes non linéaires. L'utilisation de la randomisation pour améliorer les limites de temps pour la programmation linéaire de faible dimension et les problèmes connexes a été lancée par Clarkson et par Dyer & Frieze (1989) .

La définition des problèmes de type LP en termes de fonctions satisfaisant les axiomes de localité et de monotonie est de Sharir & Welzl (1992) , mais d'autres auteurs dans la même période ont formulé des généralisations combinatoires alternatives de programmes linéaires. Par exemple, dans un cadre développé par Gärtner (1995) , la fonction f est remplacée par un ordre total sur les sous-ensembles de S . Il est possible de rompre les liens dans un problème de type LP pour créer un ordre total, mais seulement au prix d'un accroissement de la dimension combinatoire. De plus, comme dans les problèmes de type LP, Gärtner définit certaines primitives pour effectuer des calculs sur des sous-ensembles d'éléments ; cependant, sa formalisation n'a pas d'analogue de la dimension combinatoire.

Une autre généralisation abstraite des programmes linéaires et des problèmes de complémentarité linéaire , formulée par Stickney & Watson (1978) et étudiée plus tard par plusieurs autres auteurs, concerne les orientations des arêtes d'un hypercube avec la propriété que chaque face de l'hypercube (y compris l'hypercube entier en tant que face) a un puits unique , un sommet sans arêtes sortantes. Une orientation de ce type peut être formée à partir d'un problème de type LP en faisant correspondre les sous-ensembles de S avec les sommets d'un hypercube de telle sorte que deux sous-ensembles diffèrent d'un seul élément si et seulement si les sommets correspondants sont adjacents, et en l' orientation de l'arête entre les ensembles voisins A ⊆ B vers B si f ( A ) ≠ f ( B ) et vers un autre. L'orientation résultante a la propriété supplémentaire de former un graphe acyclique orienté , à partir duquel on peut montrer qu'un algorithme aléatoire peut trouver le puits unique de l'hypercube entier (la base optimale du problème de type LP) en un certain nombre d'étapes exponentielle dans la racine carrée de  n .

Le cadre plus récemment développé des espaces de violeur généralise les problèmes de type LP, dans le sens où chaque problème de type LP peut être modélisé par un espace de violeur mais pas nécessairement l'inverse. Les espaces de violation sont définis de manière similaire aux problèmes de type LP, par une fonction f qui mappe les ensembles aux valeurs de la fonction objectif, mais les valeurs de f ne sont pas ordonnées. Malgré le manque d'ordre, chaque ensemble S a un ensemble bien défini de bases (les ensembles minimaux ayant la même valeur que l'ensemble entier) qui peuvent être trouvés par des variantes des algorithmes de Clarkson pour les problèmes de type LP. En effet, il a été démontré que les espaces de violation caractérisent exactement les systèmes qui peuvent être résolus par les algorithmes de Clarkson.

Remarques

Les références