bilevel-github-single-bilevel-multi-EX2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# How to cite \n",
    "@software{Alireza_Soroudi_PyomoOptimization, author = {Alireza Soroudi, Alireza}, license = {MIT}, title = {{PyomoOptimization}}, url = {https://github.com/OptimizationExpert/Pyomo%7D }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "executionInfo": {
     "elapsed": 3688,
     "status": "ok",
     "timestamp": 1672412393035,
     "user": {
      "displayName": "Optimization team",
      "userId": "15136432228850492764"
     },
     "user_tz": 0
    },
    "id": "Q81gD3GOtgJD"
   },
   "outputs": [],
   "source": [
    "from pyomo.environ import *\n",
    "import numpy as np \n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Bi-level optimization problem\n",
    "$$\\min_{0 \\leq x} x-4y \\ \\ \\ \\ \\ \\ $$\n",
    "$$\\ \\ \\ \\ Subject \\ to$$\n",
    "$$ \\ \\ \\ \\min_{y\\geq 0} y $$\n",
    "$$ -x-y +3\\leq 0 \\ : \\mu_1 $$\n",
    "$$ -2x+y\\leq 0 \\ : \\mu_2  $$\n",
    "$$ 2x+y -12\\leq 0 \\ : \\mu_3  $$\n",
    "$$ -3x+2y+4\\leq 0 \\ : \\mu_4  $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The min problem should be transformed to max form"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\max_{x,y} f(x,y)$$\n",
    "$$ h_i(x,y) =0 :  \\lambda_i$$\n",
    "$$ g_j(x,y) \\leq 0 : \\mu_j $$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Bi-level optimization problem\n",
    "$$\\min_{0 \\leq x} x-4y \\ \\ \\ \\ \\ \\ $$\n",
    "$$\\ \\ \\ \\ Subject \\ to$$\n",
    "$$ \\ \\ \\ \\max_{y} -y $$\n",
    "$$ -x-y +3\\leq 0 \\ : \\mu_1 $$\n",
    "$$ -2x+y\\leq 0 \\ : \\mu_2  $$\n",
    "$$ 2x+y -12\\leq 0 \\ : \\mu_3  $$\n",
    "$$ -3x+2y+4\\leq 0 \\ : \\mu_4  $$\n",
    "$$ -y\\leq 0 \\ : \\mu_5  $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We need to replace the lower problem with its KKT conditions "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# KKT conditions: \n",
    "- Create Lagrangian      \n",
    "$$\\mathcal{L} = f(x,y) + \\sum_i \\lambda_i h_i(x,y) + \\sum_j \\mu_j g_j(x,y) $$\n",
    "\n",
    "$$ \\mathcal{L} = -y +  (-x-y +3)\\mu_1 \n",
    "+ (-2x+y)\\mu_2 \n",
    "+ (2x+y -12)\\mu_3 \n",
    "+ (-3x+2y+4)\\mu_4  \n",
    "+ (-y)\\mu_5  $$\n",
    "\n",
    "- Differentiate to the lower leb=vel variable (y) = 0       \n",
    "$$ \\frac{\\partial \\mathcal{L}}{\\partial y} = -1 -\\mu_1 + \\mu_2 +\\mu_3 + 2\\mu_4 -\\mu_5 =0  $$\n",
    "\n",
    "- Complementarity slackness conditions \n",
    "$$  (-x-y +3)\\mu_1 = 0 $$\n",
    "$$ (-2x+y)\\mu_2 = 0   $$\n",
    "$$ (2x+y -12)\\mu_3 = 0 $$\n",
    "$$ (-3x+2y+4)\\mu_4 = 0 $$\n",
    "$$ (-y)\\mu_5 = 0  $$\n",
    "$$ \\mu_i \\geq 0 $$\n",
    "\n",
    "- Original conditions: \n",
    "$$ -x-y +3\\leq 0 \\ : \\mu_1 $$\n",
    "$$ -2x+y\\leq 0 \\ : \\mu_2  $$\n",
    "$$ 2x+y -12\\leq 0 \\ : \\mu_3  $$\n",
    "$$ -3x+2y+4\\leq 0 \\ : \\mu_4  $$\n",
    "$$ -y\\leq 0 \\ : \\mu_5  $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "executionInfo": {
     "elapsed": 2851,
     "status": "ok",
     "timestamp": 1672412410924,
     "user": {
      "displayName": "Optimization team",
      "userId": "15136432228850492764"
     },
     "user_tz": 0
    },
    "id": "_WvYMAaHZW2k"
   },
   "source": [
    "# Pyomo code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 268,
     "status": "ok",
     "timestamp": 1672412542172,
     "user": {
      "displayName": "Optimization team",
      "userId": "15136432228850492764"
     },
     "user_tz": 0
    },
    "id": "LkpGUtiS60lD",
    "outputId": "dbe850c3-e499-46a7-a7d9-751aab04ce5c",
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "feasible\n",
      "OF =  -12.0\n",
      "x =  4.0\n",
      "y =  4.0\n",
      "mu_1 =  0.0\n",
      "mu_2 =  -0.0\n",
      "mu_3 =  0.5\n",
      "mu_4 =  0.25\n",
      "mu_5 =  0.0\n"
     ]
    }
   ],
   "source": [
    "# create a model\n",
    "model = AbstractModel()\n",
    "\n",
    "# declare decision variables\n",
    "model.x = Var(initialize = 4,within=NonNegativeReals)\n",
    "model.y = Var(initialize = 4,within=NonNegativeReals)\n",
    "model.mu1 = Var(initialize = 0, within=NonNegativeReals)\n",
    "model.mu2 = Var(initialize = 0, within=NonNegativeReals)\n",
    "model.mu3 = Var(initialize = 0, within=NonNegativeReals)\n",
    "model.mu4 = Var(initialize = 0, within=NonNegativeReals)\n",
    "model.mu5 = Var(initialize = 0, within=NonNegativeReals)\n",
    "\n",
    "# declare constraints\n",
    "model.C1 = Constraint(expr = (-model.x-model.y+3) <= 0)\n",
    "model.C2 = Constraint(expr = (-2*model.x+model.y) <= 0)\n",
    "model.C3 = Constraint(expr = (2*model.x+model.y-12) <= 0)\n",
    "model.C4 = Constraint(expr = (-3*model.x+2*model.y+4) <= 0)\n",
    "model.C5 = Constraint(expr = (-model.y) <= 0)\n",
    "\n",
    "model.lagrange = Constraint(expr = -1-model.mu1+model.mu2+model.mu3+2*model.mu4-model.mu5 == 0)\n",
    "model.Com1 = Constraint(expr = (-model.x-model.y+3)*model.mu1 == 0)\n",
    "model.Com2 = Constraint(expr = (-2*model.x+model.y)*model.mu2 == 0)\n",
    "model.Com3 = Constraint(expr = (2*model.x+model.y-12)*model.mu3 == 0)\n",
    "model.Com4 = Constraint(expr = (-3*model.x+2*model.y+4)*model.mu4 == 0)\n",
    "model.Com5 = Constraint(expr = (-model.y)*model.mu5 == 0)\n",
    "\n",
    "\n",
    "# declare objective\n",
    "model.obj = Objective(expr = model.x -4*model.y, sense=minimize)\n",
    "opt = SolverFactory('ipopt')\n",
    "instance = model.create_instance()# solves and updates instance\n",
    "results = opt.solve(instance)\n",
    "if (results.solver.status == SolverStatus.ok) and (results.solver.termination_condition == TerminationCondition.optimal):\n",
    "    print('feasible')\n",
    "elif (results.solver.termination_condition == TerminationCondition.infeasible):\n",
    "    print('infeasible')\n",
    "else:\n",
    "    print ('Solver Status:',  results.solver.status)\n",
    "\n",
    "print('OF = ', round(value(instance.obj),4) )\n",
    "print('x = ', round(value(instance.x),4) )\n",
    "print('y = ', round(value(instance.y),4) )\n",
    "\n",
    "print('mu_1 = ', round(value(instance.mu1),4) )\n",
    "print('mu_2 = ', round(value(instance.mu2),4) )\n",
    "print('mu_3 = ', round(value(instance.mu3),4) )\n",
    "print('mu_4 = ', round(value(instance.mu4),4) )\n",
    "print('mu_5 = ', round(value(instance.mu5),4) )"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "provenance": [
    {
     "file_id": "1yGk8RB5NXrcx9f1Tb-oCiWzbxh61hZLI",
     "timestamp": 1672409808671
    },
    {
     "file_id": "1yJLvenTT23oHRs9Xen52PAXa7I5TUB7K",
     "timestamp": 1599662141071
    },
    {
     "file_id": "https://github.com/jckantor/ND-Pyomo-Cookbook/blob/master/notebooks/01.02-Running-Pyomo-on-Google-Colab.ipynb",
     "timestamp": 1589571368563
    }
   ]
  },
  "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.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}