[DOCKER] Combinaison de problèmes typiques d'optimisation et comment le faire

Problèmes typiques d'optimisation de combinaison et comment exécuter

Répertoriez les problèmes typiques dans Optimisation de combinaison et comment s'exécuter avec Python. ([Courons](# Courons)) Pour une explication plus détaillée, reportez-vous au livre "Combination Optimization".

Classe de problème typique # Problème typique Classe de complexité Double problème
Problème de réseau graphique 1 Problème minimal d'arborescence de surface entière P
2 Problème maximum d'ensembles stables
( Problème minimum de couverture de vertex , Problème de ruisseau maximum du graphe supplémentaire)
difficulté NP
3 Problème de coupe maximum difficulté NP < / tr>
4 Problème d'itinéraire le plus court P
5 Problème de débit maximum P Problème de coupe minimum
6 Problème de flux de coût minimum P < / tr>
Problème d'itinéraire 7 Problème d'itinéraire de transport (optimisation de la livraison) Difficulté NP
8 Problème de vendeur de patrouille difficulté NP Moins
Problème de recouvrement / fractionnement collectif 10 Problème de couverture agrégée difficulté NP 11 Problème de division de groupe difficulté NP
12 Problème d'enchères combinées Difficulté NP < / tr>
Problème de planification 13 Problème d'atelier de travail Difficulté NP
14 Problème de planification du travail Difficulté NP < / tr>
Problème de coupure / brouillage 15 Problème de sac à dos difficulté NP
16 Problème d'emballage de bac Difficulté NP < / tr>
17 Problème de brouillage en n dimensions difficulté NP
Problème de placement 18 Problème de placement des installations Difficulté NP
19 Pas de contrainte de capacité Problème de placement des installations Difficulté NP
Problème d'affectation / correspondance 20 Problème d'allocation secondaire difficulté NP
21 Problème d'allocation généralisé Difficulté NP
22 Problème de correspondance maximal P
23 Problème de correspondance de poids P
24 Problème de correspondance stable (P)

Courons

Au démarrage de Docker

Installez Docker Toolbox et à partir de Kitematic, image Docker tsutomu7 / typique_optimization Veuillez exécuter le. Après l'exécution, ouvrez http: // localhost: 8888. Le mot de passe du Jupyter Notebook est jupyter. Pour l'installation de Docker, veuillez également vous reporter à Jusqu'à ce que vous démarriez Jupyter avec Docker.

Lors de l'installation et de l'exécution localement

Veuillez installer le logiciel suivant. Après l'installation, vous pouvez exécuter le code lié à chacun des problèmes ci-dessus.

--Installation de Python et pip: Sélectionnez le système d'exploitation cible dans le Guide de construction de l'environnement et installez-le.

--ortoolpy: pour les problèmes typiques. Certains ont une fonctionnalité minimale et certains sont inefficaces. PuLP (modeleur et solveur pour l'optimisation mathématique) est également installé.

--Référence: Il existe également une méthode utilisant Anaconda, mais la gestion de la bibliothèque est différente de la méthode ci-dessus (Anaconda intègre Python et divers packages pour la science et la technologie). C'est une distribution qui a été faite).

référence

Recommended Posts

Combinaison de problèmes typiques d'optimisation et comment le faire
exécution et erreur de pytube
Classes et méthodes statiques
Optimisation de combinaison - problème typique de problème de sac à dos
Optimisation de combinaison - problème typique de conditionnement n-dimensionnel
Problème FizzBuzz ceci et cela
Diverses méthodes de classe et méthodes statiques
Optimisation de combinaison - problème typique - problème de couverture de vertex minimum
Problème de correspondance stable aux problèmes typique d'optimisation de combinaison
Optimisation de combinaison - problème typique d'allocation généralisé
Problème d'optimisation de combinaison-problème typique d'emballage de bac
Optimisation de combinaison - problème typique de correspondance de problème maximum
Optimisation des combinaisons - Problème typique - Problème d'allocation secondaire
Combinaison d'optimisation-problème typique-problème de chemin le plus court
Optimisation combinée - problème typique d'enchères combinées
Optimisation de la combinaison - problème typique - problème de débit maximal
Le problème des menteurs et de l'honnêteté
Combinaison d'optimisation-problème typique de couverture d'agrégat
Problème de correspondance typique de problème-poids par optimisation de combinaison
Problème d'optimisation de combinaison-problème typique de placement des installations
Optimisation de la combinaison - problème typique de l'atelier de travail
Optimisation de la combinaison - problème typique - problème de coupe maximale
Optimisation de combinaison - Problème typique - Problème de vendeur circulaire
Problème d'ordonnancement de travail-problème typique d'optimisation de combinaison