{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Quadratic Programs" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Introduction" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In this tutorial, we briefly introduce how to build optimization problems using Qiskit optimization module.\n", "Qiskit optimization introduces the `QuadraticProgram` class to make a model of an optimization problem.\n", "More precisely, it deals with quadratically constrained quadratic programs given as follows:\n", "\n", "$$\n", "\\begin{align}\n", "\\text{minimize}\\quad& x^\\top Q_0 x + c^\\top x\\\\\n", "\\text{subject to}\\quad& A x \\leq b\\\\\n", "& x^\\top Q_i x + a_i^\\top x \\leq r_i, \\quad 1,\\dots,i,\\dots,q\\\\\n", "& l_i \\leq x_i \\leq u_i, \\quad 1,\\dots,i,\\dots,n,\n", "\\end{align}\n", "$$\n", "\n", "where the $Q_i$ are $n \\times n$ matrices, $A$ is a $m \\times n$ matrix , $x$, and $c$ are $n$-dimensional vectors, $b$ is an $m$-dimensional vector, and where $x$ can be defined as binary, integer, or continuous variables.\n", "In addition to \"$\\leq$\" constraints `QuadraticProgram` also supports \"$\\geq$\" and \"$=$\"." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Loading a `QuadraticProgram` from an LP file" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "As setup, you need to import the following module." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "from qiskit_optimization import QuadraticProgram\n", "from qiskit_optimization.translators import from_docplex_mp" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You start with an empty model. How to add variables and constraints to a model is explained in the section [Directly constructing a QuadraticProgram](#Directly-constructing-a-QuadraticProgram)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Qiskit optimization module supports the conversion from Docplex model. You can easily make a model of an optimization problem with Docplex.\n", "You can find the documentation of Docplex at https://ibmdecisionoptimization.github.io/docplex-doc/mp/index.html\n", "\n", "You can load a Docplex model to `QuadraticProgram` by using `from_docplex_mp` function." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Loading a `QuadraticProgram` from a docplex model" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\\ This file has been generated by DOcplex\n", "\\ ENCODING=ISO-8859-1\n", "\\Problem name: docplex model\n", "\n", "Minimize\n", " obj: x + 2 y\n", "Subject To\n", " c1: x - y = 3\n", " qc1: [ x^2 - y^2 ] <= 1\n", "\n", "Bounds\n", " 0 <= x <= 1\n", " -1 <= y <= 5\n", "\n", "Binaries\n", " x\n", "\n", "Generals\n", " y\n", "End\n", "\n" ] } ], "source": [ "# Make a Docplex model\n", "from docplex.mp.model import Model\n", "\n", "mdl = Model(\"docplex model\")\n", "x = mdl.binary_var(\"x\")\n", "y = mdl.integer_var(lb=-1, ub=5, name=\"y\")\n", "mdl.minimize(x + 2 * y)\n", "mdl.add_constraint(x - y == 3)\n", "mdl.add_constraint((x + y) * (x - y) <= 1)\n", "print(mdl.export_as_lp_string())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "`QuadraticProgram` has a method `prettyprint` to generate a comprehensive string representation." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "\n", "Problem name: docplex model\n", "\n", "Minimize\n", " x + 2*y\n", "\n", "Subject to\n", " Linear constraints (1)\n", " x - y == 3 'c0'\n", "\n", " Quadratic constraints (1)\n", " x^2 - y^2 <= 1 'q0'\n", "\n", " Integer variables (1)\n", " -1 <= y <= 5\n", "\n", " Binary variables (1)\n", " x\n", "\n" ] } ], "source": [ "# load from a Docplex model\n", "mod = from_docplex_mp(mdl)\n", "print(type(mod))\n", "print()\n", "print(mod.prettyprint())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Directly constructing a `QuadraticProgram`" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We then explain how to make model of an optimization problem directly using `QuadraticProgram`.\n", "Let's start from an empty model." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Problem name: my problem\n", "\n", "Minimize\n", " 0\n", "\n", "Subject to\n", " No constraints\n", "\n", " No variables\n", "\n" ] } ], "source": [ "# make an empty problem\n", "mod = QuadraticProgram(\"my problem\")\n", "print(mod.prettyprint())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The `QuadraticProgram` supports three types of variables:\n", "\n", "- Binary variable\n", "- Integer variable\n", "- Continuous variable\n", "\n", "When you add variables, you can specify names, types, lower bounds and upper bounds." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Problem name: my problem\n", "\n", "Minimize\n", " 0\n", "\n", "Subject to\n", " No constraints\n", "\n", " Integer variables (1)\n", " -1 <= y <= 5\n", "\n", " Continuous variables (1)\n", " -1 <= z <= 5\n", "\n", " Binary variables (1)\n", " x\n", "\n" ] } ], "source": [ "# Add variables\n", "mod.binary_var(name=\"x\")\n", "mod.integer_var(name=\"y\", lowerbound=-1, upperbound=5)\n", "mod.continuous_var(name=\"z\", lowerbound=-1, upperbound=5)\n", "print(mod.prettyprint())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You can set the objective function by invoking `QuadraticProgram.minimize` or `QuadraticProgram.maximize`.\n", "You can add a constant term as well as linear and quadratic objective function by specifying linear and quadratic terms with either list, matrix or dictionary.\n", "\n", "Note that in the LP format the quadratic part has to be scaled by a factor $1/2$.\n", "Thus, when printing as LP format, the quadratic part is first multiplied by 2 and then divided by 2 again.\n", "\n", "For quadratic programs, there are 3 pieces that have to be specified: a constant (offset), a linear term ($c^{T}x$), and a quadratic term ($x^{T}Qx$).\n", "\n", "The cell below shows how to declare an objective function using a dictionary. For the linear term, keys in the dictionary correspond to variable names, and the corresponding values are the coefficients. For the quadratic term, keys in the dictionary correspond to the two variables being multiplied, and the values are again the coefficients.\n" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Problem name: my problem\n", "\n", "Minimize\n", " 2*x*y - z^2 + x + 3\n", "\n", "Subject to\n", " No constraints\n", "\n", " Integer variables (1)\n", " -1 <= y <= 5\n", "\n", " Continuous variables (1)\n", " -1 <= z <= 5\n", "\n", " Binary variables (1)\n", " x\n", "\n" ] } ], "source": [ "# Add objective function using dictionaries\n", "mod.minimize(constant=3, linear={\"x\": 1}, quadratic={(\"x\", \"y\"): 2, (\"z\", \"z\"): -1})\n", "print(mod.prettyprint())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Another way to specify the quadratic program is using arrays. For the linear term, the array corresponds to the vector $c$ in the mathematical formulation. For the quadratic term, the array corresponds to the matrix $Q$. Note that the ordering of the variables ($x$ in the mathematical formulation) is the order in which the variables were originally declared in the `QuadraticProgram` object." ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Problem name: my problem\n", "\n", "Minimize\n", " 2*x*y - z^2 + x + 3\n", "\n", "Subject to\n", " No constraints\n", "\n", " Integer variables (1)\n", " -1 <= y <= 5\n", "\n", " Continuous variables (1)\n", " -1 <= z <= 5\n", "\n", " Binary variables (1)\n", " x\n", "\n" ] } ], "source": [ "# Add objective function using lists/arrays\n", "mod.minimize(constant=3, linear=[1, 0, 0], quadratic=[[0, 1, 0], [1, 0, 0], [0, 0, -1]])\n", "print(mod.prettyprint())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You can access the constant, the linear term, and the quadratic term by looking at `Quadratic.objective.{constant, linear, quadratic}`, respectively.\n", "As for linear and quadratic terms, you can get a dense matrix (`to_array`), a sparse matrix (`coefficients`), and a dictionary (`to_dict`).\n", "For dictionaries, you can specify whether to use variable indices or names as keys.\n", "Note that the quadratic terms are stored in a compressed way, e.g., `{('x', 'y'): 1, ('y', 'x'): 2}` is stored as `{('x', 'y'): 3}`.\n", "You can get the quadratic term as a symmetric matrix by calling `to_array(symmetric=True)` or `to_dict(symmetric=True)`.\n", "If you call `to_dict(name=True)`, you can get a dictionary whose keys are pairs of variable names." ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "constant:\t\t\t 3\n", "linear dict:\t\t\t {0: 1}\n", "linear array:\t\t\t [1 0 0]\n", "linear array as sparse matrix:\n", " (0, 0)\t1 \n", "\n", "quadratic dict w/ index:\t {(0, 1): 2, (2, 2): -1}\n", "quadratic dict w/ name:\t\t {('x', 'y'): 2, ('z', 'z'): -1}\n", "symmetric quadratic dict w/ name:\t {('y', 'x'): 1, ('x', 'y'): 1, ('z', 'z'): -1}\n", "quadratic matrix:\n", " [[ 0 2 0]\n", " [ 0 0 0]\n", " [ 0 0 -1]] \n", "\n", "symmetric quadratic matrix:\n", " [[ 0 1 0]\n", " [ 1 0 0]\n", " [ 0 0 -1]] \n", "\n", "quadratic matrix as sparse matrix:\n", " (0, 1)\t2\n", " (2, 2)\t-1\n" ] } ], "source": [ "print(\"constant:\\t\\t\\t\", mod.objective.constant)\n", "print(\"linear dict:\\t\\t\\t\", mod.objective.linear.to_dict())\n", "print(\"linear array:\\t\\t\\t\", mod.objective.linear.to_array())\n", "print(\"linear array as sparse matrix:\\n\", mod.objective.linear.coefficients, \"\\n\")\n", "print(\"quadratic dict w/ index:\\t\", mod.objective.quadratic.to_dict())\n", "print(\"quadratic dict w/ name:\\t\\t\", mod.objective.quadratic.to_dict(use_name=True))\n", "print(\n", " \"symmetric quadratic dict w/ name:\\t\",\n", " mod.objective.quadratic.to_dict(use_name=True, symmetric=True),\n", ")\n", "print(\"quadratic matrix:\\n\", mod.objective.quadratic.to_array(), \"\\n\")\n", "print(\"symmetric quadratic matrix:\\n\", mod.objective.quadratic.to_array(symmetric=True), \"\\n\")\n", "print(\"quadratic matrix as sparse matrix:\\n\", mod.objective.quadratic.coefficients)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Adding/removing linear and quadratic constraints" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You can add linear constraints by setting name, linear expression, sense and right-hand-side value (rhs).\n", "You can use senses 'EQ', 'LE', and 'GE' as Docplex supports." ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Problem name: my problem\n", "\n", "Minimize\n", " 2*x*y - z^2 + x + 3\n", "\n", "Subject to\n", " Linear constraints (3)\n", " x + 2*y == 3 'lin_eq'\n", " x + 2*y <= 3 'lin_leq'\n", " x + 2*y >= 3 'lin_geq'\n", "\n", " Integer variables (1)\n", " -1 <= y <= 5\n", "\n", " Continuous variables (1)\n", " -1 <= z <= 5\n", "\n", " Binary variables (1)\n", " x\n", "\n" ] } ], "source": [ "# Add linear constraints\n", "mod.linear_constraint(linear={\"x\": 1, \"y\": 2}, sense=\"==\", rhs=3, name=\"lin_eq\")\n", "mod.linear_constraint(linear={\"x\": 1, \"y\": 2}, sense=\"<=\", rhs=3, name=\"lin_leq\")\n", "mod.linear_constraint(linear={\"x\": 1, \"y\": 2}, sense=\">=\", rhs=3, name=\"lin_geq\")\n", "print(mod.prettyprint())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You can add quadratic constraints as well as objective function and linear constraints." ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Problem name: my problem\n", "\n", "Minimize\n", " 2*x*y - z^2 + x + 3\n", "\n", "Subject to\n", " Linear constraints (3)\n", " x + 2*y == 3 'lin_eq'\n", " x + 2*y <= 3 'lin_leq'\n", " x + 2*y >= 3 'lin_geq'\n", "\n", " Quadratic constraints (3)\n", " x^2 - y*z + x + y == 1 'quad_eq'\n", " x^2 - y*z + x + y <= 1 'quad_leq'\n", " x^2 - y*z + x + y >= 1 'quad_geq'\n", "\n", " Integer variables (1)\n", " -1 <= y <= 5\n", "\n", " Continuous variables (1)\n", " -1 <= z <= 5\n", "\n", " Binary variables (1)\n", " x\n", "\n" ] } ], "source": [ "# Add quadratic constraints\n", "mod.quadratic_constraint(\n", " linear={\"x\": 1, \"y\": 1},\n", " quadratic={(\"x\", \"x\"): 1, (\"y\", \"z\"): -1},\n", " sense=\"==\",\n", " rhs=1,\n", " name=\"quad_eq\",\n", ")\n", "mod.quadratic_constraint(\n", " linear={\"x\": 1, \"y\": 1},\n", " quadratic={(\"x\", \"x\"): 1, (\"y\", \"z\"): -1},\n", " sense=\"<=\",\n", " rhs=1,\n", " name=\"quad_leq\",\n", ")\n", "mod.quadratic_constraint(\n", " linear={\"x\": 1, \"y\": 1},\n", " quadratic={(\"x\", \"x\"): 1, (\"y\", \"z\"): -1},\n", " sense=\">=\",\n", " rhs=1,\n", " name=\"quad_geq\",\n", ")\n", "print(mod.prettyprint())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You can access linear and quadratic terms of linear and quadratic constraints as in the same way as the objective function." ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "lin_geq: {'x': 1.0, 'y': 2.0} ConstraintSense.GE 3\n", "quad_geq: {'x': 1.0, 'y': 1.0} {('x', 'x'): 1.0, ('y', 'z'): -1.0} ConstraintSense.GE 3\n" ] } ], "source": [ "lin_geq = mod.get_linear_constraint(\"lin_geq\")\n", "print(\"lin_geq:\", lin_geq.linear.to_dict(use_name=True), lin_geq.sense, lin_geq.rhs)\n", "quad_geq = mod.get_quadratic_constraint(\"quad_geq\")\n", "print(\n", " \"quad_geq:\",\n", " quad_geq.linear.to_dict(use_name=True),\n", " quad_geq.quadratic.to_dict(use_name=True),\n", " quad_geq.sense,\n", " lin_geq.rhs,\n", ")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You can also remove linear/quadratic constraints by `remove_linear_constraint` and `remove_quadratic_constraint`." ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Problem name: my problem\n", "\n", "Minimize\n", " 2*x*y - z^2 + x + 3\n", "\n", "Subject to\n", " Linear constraints (2)\n", " x + 2*y <= 3 'lin_leq'\n", " x + 2*y >= 3 'lin_geq'\n", "\n", " Quadratic constraints (2)\n", " x^2 - y*z + x + y == 1 'quad_eq'\n", " x^2 - y*z + x + y >= 1 'quad_geq'\n", "\n", " Integer variables (1)\n", " -1 <= y <= 5\n", "\n", " Continuous variables (1)\n", " -1 <= z <= 5\n", "\n", " Binary variables (1)\n", " x\n", "\n" ] } ], "source": [ "# Remove constraints\n", "mod.remove_linear_constraint(\"lin_eq\")\n", "mod.remove_quadratic_constraint(\"quad_leq\")\n", "print(mod.prettyprint())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You can substitute some of variables with constants or other variables.\n", "More precisely, `QuadraticProgram` has a method `substitute_variables(constants=..., variables=...)` to deal with the following two cases.\n", "\n", "- $x \\leftarrow c$: when `constants` have a dictionary `{x: c}`. \n", "- $x \\leftarrow c y$: when `variables` have a dictionary `{x: (y, c)}`." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Substituting Variables" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Problem name: my problem\n", "\n", "Minimize\n", " -z^2 + 3\n", "\n", "Subject to\n", " Linear constraints (2)\n", " -2*z <= 3 'lin_leq'\n", " -2*z >= 3 'lin_geq'\n", "\n", " Quadratic constraints (2)\n", " z^2 - z == 1 'quad_eq'\n", " z^2 - z >= 1 'quad_geq'\n", "\n", " Continuous variables (1)\n", " -1 <= z <= 1\n", "\n" ] } ], "source": [ "sub = mod.substitute_variables(constants={\"x\": 0}, variables={\"y\": (\"z\", -1)})\n", "print(sub.prettyprint())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "If the resulting problem is infeasible due to lower bounds or upper bounds, the methods returns the status `Status.INFEASIBLE`.\n", "We try to replace variable `x` with -1, but -1 is out of range of `x` (0 <= `x` <= 1). So, it returns `Status.INFEASIBLE`." ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "Infeasible substitution for variable: x\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "QuadraticProgramStatus.INFEASIBLE\n" ] } ], "source": [ "sub = mod.substitute_variables(constants={\"x\": -1})\n", "print(sub.status)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You cannot substitute variables multiple times. \n", "The method raises an error in such a case." ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Error: 'Cannot substitute by variable that gets substituted itself: y <- x 1'\n" ] } ], "source": [ "from qiskit_optimization import QiskitOptimizationError\n", "\n", "try:\n", " sub = mod.substitute_variables(constants={\"x\": -1}, variables={\"y\": (\"x\", 1)})\n", "except QiskitOptimizationError as e:\n", " print(\"Error: {}\".format(e))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note:\n", "When you display your problem as LP format using `export_as_lp_string`,\n", "`Binaries` denotes binary variables and `Generals` denotes integer variables.\n", "If variables are not included in either `Binaries` or `Generals`, such variables are continuous ones with default lower bound = 0 and upper bound = infinity.\n", "Note that you cannot use 'e' or 'E' as the first character of names due to the [specification of LP format](https://www.ibm.com/docs/en/icos/22.1.0?topic=representation-variable-names-in-lp-file-format)." ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\\ This file has been generated by DOcplex\n", "\\ ENCODING=ISO-8859-1\n", "\\Problem name: CPLEX\n", "\n", "Minimize\n", " obj: _e + 2 f + 3 g\n", "Subject To\n", "\n", "Bounds\n", " 0 <= _e <= 1\n", " 0 <= f <= 1\n", "\n", "Binaries\n", " _e f\n", "End\n", "\n" ] } ], "source": [ "mod = QuadraticProgram()\n", "mod.binary_var(name=\"e\")\n", "mod.binary_var(name=\"f\")\n", "mod.continuous_var(name=\"g\")\n", "mod.minimize(linear=[1, 2, 3])\n", "print(mod.export_as_lp_string())" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/html": [ "

Version Information

Qiskit SoftwareVersion
qiskit-terra0.21.0.dev0+dbd3961
qiskit-aer0.10.4
qiskit-ibmq-provider0.19.1
qiskit-optimization0.4.0
System information
Python version3.10.4
Python compilerGCC 11.2.0
Python buildmain, Apr 2 2022 09:04:19
OSLinux
CPUs4
Memory (Gb)14.577545166015625
Wed May 18 16:03:27 2022 JST
" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "

This code is a part of Qiskit

© Copyright IBM 2017, 2022.

This code is licensed under the Apache License, Version 2.0. You may
obtain a copy of this license in the LICENSE.txt file in the root directory
of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.

Any modifications or derivative works of this code must retain this
copyright notice, and modified files need to carry a notice indicating
that they have been altered from the originals.

" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "import tutorial_magics\n", "\n", "%qiskit_version_table\n", "%qiskit_copyright" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "language_info": { "name": "python" } }, "nbformat": 4, "nbformat_minor": 4 }