{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# PLNE des couplages dans un graphe biparti\n",
    "\n",
    "Trouvons un couplage de taille maximum dans le graphe biparti suivant, à l'aide d'un PLNE :\n",
    "<center><img src=img/biparti.png width=200></center>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "import mip\n",
    "\n",
    "m = mip.Model()\n",
    "V = \"abcdefgh\"\n",
    "E = [(\"d\", \"h\"), (\"d\", \"g\"), (\"d\", \"f\"), (\"d\", \"e\"), (\"c\", \"h\"), (\"c\", \"g\"),\n",
    "     (\"c\", \"f\"), (\"b\", \"e\"), (\"a\", \"f\"), (\"a\", \"e\")]\n",
    "x = {e: m.add_var(name=f\"x_{e[0]}{e[1]}\") for e in E}\n",
    "m.objective = mip.maximize(mip.xsum(x[e] for e in E))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "for v in V:\n",
    "    Ev = [e for e in E if v in e] # liste des arêtes contenant v\n",
    "    m += mip.xsum(x[e] for e in Ev) <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<OptimizationStatus.OPTIMAL: 0>"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m.optimize(max_seconds=300)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4.0"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m.objective_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "d -- g\n",
      "c -- h\n",
      "b -- e\n",
      "a -- f\n"
     ]
    }
   ],
   "source": [
    "for e in E:\n",
    "    if x[e].x > 0:\n",
    "        print(f\"{e[0]} -- {e[1]}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "constr(0): +1.0 x_af +1.0 x_ae <= 1.0\n",
      "1.0\n",
      "constr(1): +1.0 x_be <= 1.0\n",
      "1.0\n",
      "constr(2): +1.0 x_ch +1.0 x_cg +1.0 x_cf <= 1.0\n",
      "1.0\n",
      "constr(3): +1.0 x_dh +1.0 x_dg +1.0 x_df +1.0 x_de <= 1.0\n",
      "1.0\n",
      "constr(4): +1.0 x_de +1.0 x_be +1.0 x_ae <= 1.0\n",
      "-0.0\n",
      "constr(5): +1.0 x_df +1.0 x_cf +1.0 x_af <= 1.0\n",
      "-0.0\n",
      "constr(6): +1.0 x_dg +1.0 x_cg <= 1.0\n",
      "-0.0\n",
      "constr(7): +1.0 x_dh +1.0 x_ch <= 1.0\n",
      "-0.0\n"
     ]
    }
   ],
   "source": [
    "for c in m.constrs: # valeurs des variables duales\n",
    "    print(c)\n",
    "    print(c.pi)"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "31f2aee4e71d21fbe5cf8b01ff0e069b9275f58929596ceb00d14d90e3e16cd6"
  },
  "kernelspec": {
   "display_name": "Python 3.9.2 64-bit",
   "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.8.10"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}