create_boolean.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CP-SAT: Create booleans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from ortools.sat.python import cp_model"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Only enforce a constraint when a condition is verified"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A great thing in CP SAT is being able to enable constraint only when some bool is true. \n",
    "\n",
    "However, this method doesn't work out of the box with linear expressions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "'BoundedLinearExpression' object is not iterable",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m/home/haxxor/projects/cpsat-fun/create_boolean.ipynb Cell 5\u001b[0m in \u001b[0;36m<cell line: 10>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      <a href='vscode-notebook-cell:/home/haxxor/projects/cpsat-fun/create_boolean.ipynb#W4sZmlsZQ%3D%3D?line=7'>8</a>\u001b[0m model\u001b[39m.\u001b[39mAdd(x \u001b[39m==\u001b[39m \u001b[39m10\u001b[39m)\n\u001b[1;32m      <a href='vscode-notebook-cell:/home/haxxor/projects/cpsat-fun/create_boolean.ipynb#W4sZmlsZQ%3D%3D?line=8'>9</a>\u001b[0m \u001b[39m# The following will fail \u001b[39;00m\n\u001b[0;32m---> <a href='vscode-notebook-cell:/home/haxxor/projects/cpsat-fun/create_boolean.ipynb#W4sZmlsZQ%3D%3D?line=9'>10</a>\u001b[0m model\u001b[39m.\u001b[39;49mAdd(result \u001b[39m==\u001b[39;49m x)\u001b[39m.\u001b[39;49mOnlyEnforceIf(x \u001b[39m>\u001b[39;49m\u001b[39m=\u001b[39;49m \u001b[39m0\u001b[39;49m)\n",
      "File \u001b[0;32m~/ynstant/ynstaenv/lib/python3.9/site-packages/ortools/sat/python/cp_model.py:816\u001b[0m, in \u001b[0;36mConstraint.OnlyEnforceIf\u001b[0;34m(self, *boolvar)\u001b[0m\n\u001b[1;32m    799\u001b[0m \u001b[39mdef\u001b[39;00m \u001b[39mOnlyEnforceIf\u001b[39m(\u001b[39mself\u001b[39m, \u001b[39m*\u001b[39mboolvar):\n\u001b[1;32m    800\u001b[0m     \u001b[39m\"\"\"Adds an enforcement literal to the constraint.\u001b[39;00m\n\u001b[1;32m    801\u001b[0m \n\u001b[1;32m    802\u001b[0m \u001b[39mThis method adds one or more literals (that is, a boolean variable or its\u001b[39;00m\n\u001b[0;32m   (...)\u001b[0m\n\u001b[1;32m    814\u001b[0m \u001b[39m  self.\u001b[39;00m\n\u001b[1;32m    815\u001b[0m \u001b[39m\"\"\"\u001b[39;00m\n\u001b[0;32m--> 816\u001b[0m     \u001b[39mfor\u001b[39;00m lit \u001b[39min\u001b[39;00m ExpandGeneratorOrTuple(boolvar):\n\u001b[1;32m    817\u001b[0m         \u001b[39mif\u001b[39;00m (\u001b[39misinstance\u001b[39m(lit, \u001b[39mbool\u001b[39m) \u001b[39mand\u001b[39;00m\n\u001b[1;32m    818\u001b[0m                 \u001b[39mbool\u001b[39m(lit)) \u001b[39mor\u001b[39;00m (cmh\u001b[39m.\u001b[39mis_integral(lit) \u001b[39mand\u001b[39;00m \u001b[39mint\u001b[39m(lit) \u001b[39m==\u001b[39m \u001b[39m1\u001b[39m):\n\u001b[1;32m    819\u001b[0m             \u001b[39m# Always true. Do nothing.\u001b[39;00m\n\u001b[1;32m    820\u001b[0m             \u001b[39mpass\u001b[39;00m\n",
      "\u001b[0;31mTypeError\u001b[0m: 'BoundedLinearExpression' object is not iterable"
     ]
    }
   ],
   "source": [
    "model = cp_model.CpModel()\n",
    "\n",
    "x = model.NewIntVar(-100, 100, \"x\")\n",
    "result = model.NewIntVar(0, 100, \"result\")\n",
    "\n",
    "# We want to have result == x only if x >= 0\n",
    "# Let's suppose x=10\n",
    "model.Add(x == 10)\n",
    "# The following will fail \n",
    "model.Add(result == x).OnlyEnforceIf(x >= 0)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A trick is to use an intermediate boolean variable, with correct constraints.\n",
    "\n",
    "The boolean variable will be true when the condition is enforced, and false otherwise. \n",
    "\n",
    "Here, we implement this for the condition \"var is non zero\", i.e. `var > 0`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def create_boolean_is_positive(model:cp_model.CpModel, var: cp_model.IntVar):\n",
    "    \"\"\"Create a bool variable such that \n",
    "    If var >= 0 then bool = 1\n",
    "    If var  < 0 then bool = 0 \n",
    "    \"\"\"\n",
    "    boolean_var = model.NewBoolVar(name=var.Name() + \"_is_positive\")\n",
    "\n",
    "    # Bool are casted to 0 if False and 1 if True, so you can do some operations with them\n",
    "    model.Add(var >= 0).OnlyEnforceIf(boolean_var)\n",
    "    model.Add(var < 0).OnlyEnforceIf(boolean_var.Not())\n",
    "\n",
    "    return boolean_var"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's try this function. If x is nonzero positive, we'd like to see the value of x as a result. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution is: 10\n"
     ]
    }
   ],
   "source": [
    "model = cp_model.CpModel()\n",
    "\n",
    "x = model.NewIntVar(-100, 100, \"x\")\n",
    "result = model.NewIntVar(0, 100, \"result\")\n",
    "\n",
    "# We want to have result == x only if x >= 0\n",
    "# We create the intermediate variable \n",
    "x_is_positive = create_boolean_is_positive(model, x)\n",
    "\n",
    "# Let's suppose x=10\n",
    "model.Add(x == 10)\n",
    "# The following will work\n",
    "model.Add(result == x).OnlyEnforceIf(x_is_positive)\n",
    "\n",
    "# Solve\n",
    "solver = cp_model.CpSolver()\n",
    "status = solver.Solve(model)\n",
    "\n",
    "# Divide the result to get a rounded down solution\n",
    "print(f\"Solution is: {solver.Value(result)}\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now if x is nonzero negative, we set the result to be 42. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution is: 42\n"
     ]
    }
   ],
   "source": [
    "model = cp_model.CpModel()\n",
    "\n",
    "x = model.NewIntVar(-100, 100, \"x\")\n",
    "result = model.NewIntVar(0, 100, \"result\")\n",
    "x_is_positive = create_boolean_is_positive(model, x)\n",
    "\n",
    "# Let's suppose x=-10\n",
    "model.Add(x == -10)\n",
    "model.Add(result == x).OnlyEnforceIf(x_is_positive)\n",
    "# And return 42 if x is not positive\n",
    "model.Add(result == 42).OnlyEnforceIf(x_is_positive.Not())\n",
    "\n",
    "\n",
    "# Solve\n",
    "solver = cp_model.CpSolver()\n",
    "status = solver.Solve(model)\n",
    "\n",
    "# Divide the result to get a rounded down solution\n",
    "print(f\"Solution is: {solver.Value(result)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's also inspect the value of the bool if x=0. In the function we decided for the bool to be true. This is indeed what we see. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution is: 1\n"
     ]
    }
   ],
   "source": [
    "model = cp_model.CpModel()\n",
    "\n",
    "x = model.NewIntVar(-100, 100, \"x\")\n",
    "result = model.NewIntVar(0, 100, \"result\")\n",
    "x_is_positive = create_boolean_is_positive(model, x)\n",
    "\n",
    "# Let's test the case x==0 \n",
    "model.Add(x == 0)\n",
    "\n",
    "# Solve\n",
    "solver = cp_model.CpSolver()\n",
    "status = solver.Solve(model)\n",
    "\n",
    "# Divide the result to get a rounded down solution\n",
    "print(f\"Solution is: {solver.Value(x_is_positive)}\")"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Only enforce a constraint when var is equal to value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def create_boolean_is_equal_to(model:cp_model.CpModel, var: cp_model.IntVar, value: int):\n",
    "    \"\"\"Create a bool variable such that\n",
    "    If var == value then bool = 1\n",
    "    Else then bool = 0\n",
    "    \"\"\"\n",
    "    boolean_var = model.NewBoolVar(name=f\"{var.Name()}_is_equal_to_{value}\")\n",
    "    model.Add(value == var).OnlyEnforceIf(boolean_var)\n",
    "    model.Add(value != var).OnlyEnforceIf(boolean_var.Not())\n",
    "\n",
    "    return boolean_var"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO : test"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "ynstaenv",
   "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.9.5"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "60aad423cf61d8722f5f696b996614860486ab31702984425ac69059c5f0f73d"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}