{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Mini tutoriel pour la résolution de programmes linéaires avec Python - ENS Rennes 2021"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Références si vous êtes curieux-ses\n",
"\n",
"Un très bon tutoriel :\n",
"\n",
"- https://realpython.com/linear-programming-python/\n",
"\n",
"Documentation de `scipy.optimize` :\n",
"\n",
"- https://docs.scipy.org/doc/scipy/reference/optimize.html\n",
"\n",
"D'autres tutoriels :\n",
"- https://scipy-lectures.org/advanced/mathematical_optimization/index.html\n",
"- https://medium.com/better-programming/how-to-solving-linear-programming-problems-with-examples-and-implementation-in-python-a7b7061bafc9\n",
"- http://stackoverflow.com/questions/10697995/ddg#10705799"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Auteur : [Lilian Besson](https://perso.crans.org/besson/)\n",
"- License : [MIT](https://lbesson.mit-license.org/)\n",
"- Date : 27/01/2021\n",
"- Cours : [ALGO2](http://people.irisa.fr/Francois.Schwarzentruber/algo2/) @ [ENS Rennes](http://www.dit.ens-rennes.fr/)"
]
},
{
"cell_type": "markdown",
"metadata": {
"toc": true
},
"source": [
"Table of Contents
\n",
""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Pré-requis pour exécuter ce notebook\n",
"\n",
"- Soit vous le téléchargez et vous l'utilisez localement, dans ce cas il faut que vous ayez installé le module `scipy`.\n",
" + Utilisez votre gestionnaire de paquet système (`apt-get` par exemple) si Python installé par ce gestionnaire ;\n",
" + Utilisez `pip install scipy` ou pip3, ou avec `sudo pip` (Linux/Mac) ou pip.exe (Windows) si modules Python gérés avec [pip](https://pypi.org/) (recommandé) ;\n",
" + Utilisez `conda install scipy` si modules Python gérés avec conda (si installé avec [Anaconda](https://www.anaconda.com/products/individual).\n",
"\n",
"- Soit vous utilisez le lien fourni dans Discord pour exécuter ce notebook dans un environnement en ligne, avec [MyBinder](https://mybinder.org/) (gratuit libre et sans connexion)."
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-26T19:13:27.274893Z",
"start_time": "2021-01-26T19:13:27.266094Z"
}
},
"outputs": [],
"source": [
"try:\n",
" import scipy.optimize\n",
"except ImportError:\n",
" print(\"Vous avez lu le paragraphe précédent...?\")\n",
" print(\"Je t'envoie sur https://scipy.org/install.html et tu auras plus d'informations...\")\n",
" import webbrowser\n",
" webbrowser.open_new_tab(\"https://scipy.org/install.html\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# Quelques petits problèmes linéaires"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Premier problème linéaire\n",
"\n",
"Il vient du tutoriel [susmentionné](https://medium.com/better-programming/how-to-solving-linear-programming-problems-with-examples-and-implementation-in-python-a7b7061bafc9) :"
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-26T19:29:53.092729Z",
"start_time": "2021-01-26T19:29:53.083403Z"
}
},
"outputs": [],
"source": [
"# Objective Function: 50x_1 + 80x_2\n",
"# Constraint 1: 5x_1 + 2x_2 <= 20\n",
"# Constraint 2: -10x_1 + -12x_2 <= -90\n",
"\n",
"result = scipy.optimize.linprog(\n",
" [50, 80], # Cost function: 50x_1 + 80x_2\n",
" A_ub=[[5, 2], [-10, -12]], # Coefficients for inequalities\n",
" b_ub=[20, -90], # Constraints for inequalities: 20 and -90\n",
" bounds=(0, None), # Bounds on x, 0 <= x_i <= +oo by default\n",
")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On utilise les fonctionnalités de scipy pour les problèmes linéaires ([doc](https://docs.scipy.org/doc/scipy/reference/optimize.html#linear-programming)), et pour commencer [la seule fonction `scipy.optimize.linprog`](https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linprog.html#scipy.optimize.linprog) :"
]
},
{
"cell_type": "code",
"execution_count": 45,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-26T19:29:53.913661Z",
"start_time": "2021-01-26T19:29:53.900937Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"X1: 1.5 hours\n",
"X2: 6.25 hours\n"
]
}
],
"source": [
"if result.success:\n",
" print(f\"X1: {round(result.x[0], 2)} hours\")\n",
" print(f\"X2: {round(result.x[1], 2)} hours\")\n",
"else:\n",
" print(\"No solution\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Et voilà, pas plus compliqué !\n",
"\n",
"Vous pourrez observer que le résultat de l'appel à cette fonction (si tout marche bien) est un objet qui encapsule plusieurs choses :\n",
"\n",
"- la valeur de la solution, `result.x` ;\n",
"- le nombre d'itérations, `result.nit` ;\n",
"- l'état des slacks variables (cf cours sur le simplexe), `result.slack` ;\n",
"- évaluation de l'état de l'optimisation, `result.success`, et `result.message` ;\n",
"- et même la valeur de la fonction objectif à ce point solution (c'est utile pour gagner du temps, si cette fonction objectif est très couteuse, par exemple quand on apprend un gros réseau de neurone, avec d'autres solveurs)."
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-26T19:17:33.649678Z",
"start_time": "2021-01-26T19:17:33.642916Z"
},
"scrolled": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" con: array([], dtype=float64)\n",
" fun: 574.99999998789\n",
" message: 'Optimization terminated successfully.'\n",
" nit: 4\n",
" slack: array([ 3.34711814e-10, -1.83780458e-09])\n",
" status: 0\n",
" success: True\n",
" x: array([1.5 , 6.25])\n"
]
}
],
"source": [
"print(result)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Problème exemple du cours sur le simplexe\n",
"\n",
"Attention, généralement les solveurs cherchent à **minimiser** la fonction de coût, pas à la maximiser !\n",
"\n",
"C'est un piège classique, on rentre le problème, le solveur répond [0,0,..,0] comme solution, et on ne sait pas ce qui n'a pas marché..."
]
},
{
"cell_type": "code",
"execution_count": 54,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-26T19:32:00.345509Z",
"start_time": "2021-01-26T19:32:00.332614Z"
}
},
"outputs": [],
"source": [
"# Objective Function: x_1 + 6*x_2 + 13*x_3\n",
"# Constraint 1: x_1 <= 200\n",
"# Constraint 2: x_2 <= 300\n",
"# Constraint 3: x_1 + x_2 + x_3 <= 400\n",
"# Constraint 4: x_2 + 3*x_3 <= 600\n",
"# les variables sont supposées positives par défaut\n",
"# x_1 >= 0\n",
"# x_2 >= 0\n",
"# x_3 >= 0\n",
"\n",
"result = scipy.optimize.linprog(\n",
" [-1, -6, -13], # Cost function: -x_1 + -6*x_2 + -13*x_3 to MINIMIZE\n",
" A_ub=[ # Coefficients for inequalities\n",
" [1, 0, 0], # for C1: 1*x_1 + 0*x_2 + 0*x_3 <= 200\n",
" [0, 1, 0], # for C2: 0*x_1 + 1*x_2 + 0*x_3 <= 300\n",
" [1, 1, 1], # for C3: 1*x_1 + 1*x_2 + 1*x_3 <= 400\n",
" [0, 1, 3], # for C4: 0*x_1 + 1*x_2 + 3*x_3 <= 600\n",
" ],\n",
" b_ub=[200, 300, 400, 600], # Constraints for inequalities: 200, 300, 400, 600\n",
" bounds=(0, None), # Bounds on x, 0 <= x_i <= +oo by default\n",
" method=\"simplex\",\n",
")"
]
},
{
"cell_type": "code",
"execution_count": 55,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-26T19:32:00.687595Z",
"start_time": "2021-01-26T19:32:00.681180Z"
},
"scrolled": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" con: array([], dtype=float64)\n",
" fun: -3100.0\n",
" message: 'Optimization terminated successfully.'\n",
" nit: 5\n",
" slack: array([2.00000000e+02, 5.68434189e-14, 0.00000000e+00, 0.00000000e+00])\n",
" status: 0\n",
" success: True\n",
" x: array([ 0., 300., 100.])\n"
]
}
],
"source": [
"print(result)"
]
},
{
"cell_type": "code",
"execution_count": 56,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-26T19:32:01.091149Z",
"start_time": "2021-01-26T19:32:01.083242Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"X1: 0.0 chocolats simples\n",
"X2: 300.0 pyramides\n",
"X2: 100.0 pyramides de luxe\n"
]
}
],
"source": [
"if result.success:\n",
" print(f\"X1: {round(result.x[0], 2)} chocolats simples\")\n",
" print(f\"X2: {round(result.x[1], 2)} pyramides\")\n",
" print(f\"X2: {round(result.x[2], 2)} pyramides de luxe\")\n",
"else:\n",
" print(\"No solution\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On trouve donc la solution commerciale optimale pour Charlie le chocolatier : 300 pyramides, et 100 pyramides de luxe."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### **Exercice 1** : sur ce problème, cherchez quelles contraintes (inégalités) sont saturées (devenues des égalités)\n",
"\n",
"Indice : lire le tableau `result.slack` et l'interpréter."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-26T19:33:44.390142Z",
"start_time": "2021-01-26T19:33:44.379415Z"
}
},
"outputs": [],
"source": [
"# TODO\n",
"print(result)\n",
"\n",
"print(\"Variables slack:\")\n",
"print(result.slack)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### **Exercice 2** : résoudre un autre problème vu en cours"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Bonus : réfléchir à une situation de votre vie personnelle qui pourrait être mis en forme comme un problème linéaire\n",
"\n",
"Un exemple que j'ai beaucoup est le suivant, qui généralise l'idée de « régime diététique optimal » : https://jeremykun.com/2014/06/02/linear-programming-and-the-most-affordable-healthy-diet-part-1/ (très bon blogue à suivre si ça vous plaît)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Comparer différentes méthodes :"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Comme le dit la documentation :\n",
"\n",
"> The linprog function supports the following methods:\n",
"\n",
" linprog(method=’simplex’)\n",
" linprog(method=’interior-point’)\n",
" linprog(method=’revised simplex’)\n",
" linprog(method=’highs-ipm’)\n",
" linprog(method=’highs-ds’)\n",
" linprog(method=’highs’)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"> Certaines méthodes peuvent ne pas être disponible sur votre installation, mais normalement `\"simplex\"` et `\"interior-point\"` sont disponibles partout."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### **Exercice 3** : sur un problème de votre choix, testez au moins deux méthodes.\n",
"\n",
"Ce petit morceau de code peut vous aider :"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-26T19:17:59.519423Z",
"start_time": "2021-01-26T19:17:59.515892Z"
}
},
"outputs": [],
"source": [
"methods = [\n",
" \"simplex\",\n",
" \"interior-point\",\n",
" #\"revised-simplex\",\n",
" #\"highs-ipm\",\n",
" #\"highs-ds\",\n",
" #\"highs\",\n",
"]"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-26T19:17:59.855672Z",
"start_time": "2021-01-26T19:17:59.845988Z"
}
},
"outputs": [],
"source": [
"def solve_problem_1(method):\n",
" return scipy.optimize.linprog(\n",
" [50, 80], # Cost function: 50x_1 + 80x_2\n",
" A_ub=[[5, 2], [-10, -12]], # Coefficients for inequalities\n",
" b_ub=[20, -90], # Constraints for inequalities: 20 and -90\n",
" method=method\n",
" )"
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-26T19:18:00.294594Z",
"start_time": "2021-01-26T19:18:00.247153Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n",
"- Pour la méthode #0, simplex...\n",
"La solution trouvée est con: array([], dtype=float64)\n",
" fun: 575.0\n",
" message: 'Optimization terminated successfully.'\n",
" nit: 2\n",
" slack: array([0., 0.])\n",
" status: 0\n",
" success: True\n",
" x: array([1.5 , 6.25])\n",
"\n",
"- Pour la méthode #1, interior-point...\n",
"La solution trouvée est con: array([], dtype=float64)\n",
" fun: 574.99999998789\n",
" message: 'Optimization terminated successfully.'\n",
" nit: 4\n",
" slack: array([ 3.34711814e-10, -1.83780458e-09])\n",
" status: 0\n",
" success: True\n",
" x: array([1.5 , 6.25])\n"
]
}
],
"source": [
"for i, method in enumerate(methods):\n",
" # solve problem with this method\n",
" print(f\"\\n- Pour la méthode #{i}, {method}...\")\n",
" solution = solve_problem_1(method)\n",
" print(f\"La solution trouvée est {solution}\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### **Exercice 4** : Chercher un problème qui donne une réponse différente sur deux méthodes différentes."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Avec le code ci-dessous, cherchez un problème plus compliqué qui donne une solution différente.\n",
"Même si la différence est faible, commentez là :\n",
"\n",
"- en terme de nombre d'étape ?\n",
"- valeurs de x* ?\n",
"- valeur de f(x*) ?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"## Conclusion\n",
"\n",
"Si vous êtes très curieux, regardez un peu les références données en haut de ce document.\n",
"\n",
"N'hésitez pas à nous contacter si vous avez des questions !"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.9"
},
"toc": {
"base_numbering": 1,
"nav_menu": {},
"number_sections": true,
"sideBar": true,
"skip_h1_title": false,
"title_cell": "Table of Contents",
"title_sidebar": "Contents",
"toc_cell": true,
"toc_position": {},
"toc_section_display": true,
"toc_window_display": true
},
"varInspector": {
"cols": {
"lenName": 16,
"lenType": 16,
"lenVar": 40
},
"kernels_config": {
"python": {
"delete_cmd_postfix": "",
"delete_cmd_prefix": "del ",
"library": "var_list.py",
"varRefreshCmd": "print(var_dic_list())"
},
"r": {
"delete_cmd_postfix": ") ",
"delete_cmd_prefix": "rm(",
"library": "var_list.r",
"varRefreshCmd": "cat(var_dic_list()) "
}
},
"types_to_exclude": [
"module",
"function",
"builtin_function_or_method",
"instance",
"_Feature"
],
"window_display": false
}
},
"nbformat": 4,
"nbformat_minor": 4
}