Tutorials/jump_infeasibilities.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# JuMP: Diagnosing infeasible models\n",
    "\n",
    "Notebooks 1 and 2 define basic objects in JuMP such as variables, constraints, and expressions. This tutorial builds further to discuss how to diagnose infeasible models."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Install Gurobi\n",
    "\n",
    "Diagnosing infeasibilities is much easier with an advanced solver such as Gurobi, which has the ability to find infeasible constraints for you. A solver such as Gurobi will also be helpful for solving larger models later in the class, and for your final project.\n",
    "\n",
    "Let's start by installing a Gurobi academic license. To start, first go to https://www.gurobi.com and click \"Register\" at the top right to create an account. Follow through the steps to confirm your account. Then, once you are logged in, click \"Licenses\", click \"Request\", and generate a \"Named-User Academic\" license. Follow the steps to install the license. Once a license is installed, you can run \"gurobi_cl\" in the command line to check that the license was installed correctly.\n",
    "\n",
    "Next, open Julia and install the Gurobi package. Once it is installed, you can continue with the rest of this notebook."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Diagnosing an infeasible model\n",
    "\n",
    "Let's start with the same factory optimization example from notebook 2. We are going to purposefully add an infeasible constraint, and then figure out how to diagnose it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "using JuMP\n",
    "using Gurobi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Set parameter Username\n",
      "Academic license - for non-commercial use only - expires 2024-09-14\n"
     ]
    },
    {
     "data": {
      "text/latex": [
       "$$ \\begin{aligned}\n",
       "\\max\\quad & 150 x + 175 y\\\\\n",
       "\\text{Subject to} \\quad & 10 x + 8 y \\leq 80\\\\\n",
       " & 7 x + 11 y \\leq 77\\\\\n",
       " & x \\geq 0\\\\\n",
       " & y \\geq 0\\\\\n",
       " & x \\leq 8\\\\\n",
       "\\end{aligned} $$"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "factory_model = Model(Gurobi.Optimizer);\n",
    "@variables(factory_model, begin\n",
    "    8 >= x >= 0\n",
    "    y >= 0\n",
    "    end)\n",
    "@constraints(factory_model, begin\n",
    "    time_constraint, 10x + 8y <= 80\n",
    "    materials_constraint, 7x + 11y <= 77    \n",
    "    end)\n",
    "@expression(factory_model, objective, 150x + 175y)\n",
    "@objective(factory_model, Max, objective)\n",
    "print(factory_model)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Gurobi Optimizer version 10.0.2 build v10.0.2rc0 (mac64[arm])\n",
      "\n",
      "CPU model: Apple M2\n",
      "Thread count: 8 physical cores, 8 logical processors, using up to 8 threads\n",
      "\n",
      "Optimize a model with 2 rows, 2 columns and 4 nonzeros\n",
      "Model fingerprint: 0x3b4095a3\n",
      "Coefficient statistics:\n",
      "  Matrix range     [7e+00, 1e+01]\n",
      "  Objective range  [2e+02, 2e+02]\n",
      "  Bounds range     [8e+00, 8e+00]\n",
      "  RHS range        [8e+01, 8e+01]\n",
      "Presolve time: 0.00s\n",
      "Presolved: 2 rows, 2 columns, 4 nonzeros\n",
      "\n",
      "Iteration    Objective       Primal Inf.    Dual Inf.      Time\n",
      "       0    1.7500000e+32   1.187500e+30   1.750000e+02      0s\n",
      "       2    1.4138889e+03   0.000000e+00   0.000000e+00      0s\n",
      "\n",
      "Solved in 2 iterations and 0.00 seconds (0.00 work units)\n",
      "Optimal objective  1.413888889e+03\n",
      "\n",
      "User-callback calls 47, time in user-callback 0.00 sec\n"
     ]
    }
   ],
   "source": [
    "optimize!(factory_model)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(4.888888888888888, 3.888888888888889)"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "value.(x), value.(y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let's try adding a constraint that is clearly in conflict with the constraint x<=8. What happens when we solve the model?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$ \\begin{aligned}\n",
       "\\max\\quad & 150 x + 175 y\\\\\n",
       "\\text{Subject to} \\quad & x \\geq 10\\\\\n",
       " & 10 x + 8 y \\leq 80\\\\\n",
       " & 7 x + 11 y \\leq 77\\\\\n",
       " & x \\geq 0\\\\\n",
       " & y \\geq 0\\\\\n",
       " & x \\leq 8\\\\\n",
       "\\end{aligned} $$"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "@constraint(factory_model,test_constraint,x>=10) ;\n",
    "\n",
    "print(factory_model)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Gurobi Optimizer version 10.0.2 build v10.0.2rc0 (mac64[arm])\n",
      "\n",
      "CPU model: Apple M2\n",
      "Thread count: 8 physical cores, 8 logical processors, using up to 8 threads\n",
      "\n",
      "Optimize a model with 3 rows, 2 columns and 5 nonzeros\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 1e+01]\n",
      "  Objective range  [2e+02, 2e+02]\n",
      "  Bounds range     [8e+00, 8e+00]\n",
      "  RHS range        [1e+01, 8e+01]\n",
      "Iteration    Objective       Primal Inf.    Dual Inf.      Time\n",
      "       0    1.4138889e+03   5.111111e+00   0.000000e+00      0s\n",
      "\n",
      "Solved in 1 iterations and 0.00 seconds (0.00 work units)\n",
      "Infeasible model\n",
      "\n",
      "User-callback calls 20, time in user-callback 0.00 sec\n"
     ]
    }
   ],
   "source": [
    "optimize!(factory_model)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Diagnosing the problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Gurobi is reporting that we have an \"Infeasible model.\" This means that there is nowhere in the space of decision variables where all the constraints are obeyed. We can figure out which constraints in particular are causing the infeasibility by running \"compute_conflict!\" on the model, and printing out the results:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "IIS computed: 1 constraints and 1 bounds\n",
      "IIS runtime: 0.00 seconds (0.00 work units)\n"
     ]
    },
    {
     "data": {
      "text/latex": [
       "$$ \\begin{aligned}\n",
       "\\max\\quad & 150 x + 175 y\\\\\n",
       "\\text{Subject to} \\quad & x \\geq 10\\\\\n",
       " & x \\leq 8\\\\\n",
       "\\end{aligned} $$"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "compute_conflict!(factory_model) ;\n",
    "\n",
    "if get_attribute(factory_model, MOI.ConflictStatus()) == MOI.CONFLICT_FOUND\n",
    "    iis_model, _ = copy_conflict(factory_model)\n",
    "    print(iis_model)\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voila! Gurobi has identified the set of constraints that are leading to the infeasibility. In this context it was obvious where the infeasibility came from, but in larger models it can be quite difficult to identify what you did wrong, which is why this method is helpful."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.9.3",
   "language": "julia",
   "name": "julia-1.9"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.9.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}