নোট

এই পেজটি docs/tutorials/01_quadratic_program.ipynb থেকে তৈরি হয়েছে।

দ্বিঘাত (কোয়াড্র্যাটিক) প্রোগ্রামস#

ভূমিকা#

In this tutorial, we briefly introduce how to build optimization problems using Qiskit optimization module. Qiskit optimization introduces the QuadraticProgram class to make a model of an optimization problem. More precisely, it deals with quadratically constrained quadratic programs given as follows:

\[\begin{split}\begin{align} \text{minimize}\quad& x^\top Q_0 x + c^\top x\\ \text{subject to}\quad& A x \leq b\\ & x^\top Q_i x + a_i^\top x \leq r_i, \quad 1,\dots,i,\dots,q\\ & l_i \leq x_i \leq u_i, \quad 1,\dots,i,\dots,n, \end{align}\end{split}\]

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. In addition to "\(\leq\)" constraints QuadraticProgram also supports "\(\geq\)" and "\(=\)".

Loading a QuadraticProgram from an LP file#

সেটআপ হিসাবে, আপনাকে নিম্নলিখিত মডিউলটি আমদানি (ইম্পোর্ট) করতে হবে।

[1]:
from qiskit_optimization import QuadraticProgram
from qiskit_optimization.translators import from_docplex_mp

You start with an empty model. How to add variables and constraints to a model is explained in the section Directly constructing a QuadraticProgram.

Qiskit optimization module supports the conversion from Docplex model. You can easily make a model of an optimization problem with Docplex. You can find the documentation of Docplex at https://ibmdecisionoptimization.github.io/docplex-doc/mp/index.html

from_docplex ফাংশন ব্যবহার করে QuadraticProgram -এ একটা ডকপ্লেক্স মডেল লোড করা হয়।

একটি ডকপ্লেক্স নকশা (মডেল) থেকে একটি Quadratic Program লোড করা#

[2]:
# Make a Docplex model
from docplex.mp.model import Model

mdl = Model("docplex model")
x = mdl.binary_var("x")
y = mdl.integer_var(lb=-1, ub=5, name="y")
mdl.minimize(x + 2 * y)
mdl.add_constraint(x - y == 3)
mdl.add_constraint((x + y) * (x - y) <= 1)
print(mdl.export_as_lp_string())
\ This file has been generated by DOcplex
\ ENCODING=ISO-8859-1
\Problem name: docplex model

Minimize
 obj: x + 2 y
Subject To
 c1: x - y = 3
 qc1: [ x^2 - y^2 ] <= 1

Bounds
 0 <= x <= 1
 -1 <= y <= 5

Binaries
 x

Generals
 y
End

QuadraticProgram has a method prettyprint to generate a comprehensive string representation.

[3]:
# load from a Docplex model
mod = from_docplex_mp(mdl)
print(type(mod))
print()
print(mod.prettyprint())
<class 'qiskit_optimization.problems.quadratic_program.QuadraticProgram'>

Problem name: docplex model

Minimize
  x + 2*y

Subject to
  Linear constraints (1)
    x - y == 3  'c0'

  Quadratic constraints (1)
    x^2 - y^2 <= 1  'q0'

  Integer variables (1)
    -1 <= y <= 5

  Binary variables (1)
    x

সরাসরি একটি QuadraticProgram তৈরি করা#

We then explain how to make model of an optimization problem directly using QuadraticProgram. Let’s start from an empty model.

[4]:
# make an empty problem
mod = QuadraticProgram("my problem")
print(mod.prettyprint())
Problem name: my problem

Minimize
  0

Subject to
  No constraints

  No variables

The QuadraticProgram supports three types of variables:

  • Binary variable

  • Integer variable

  • Continuous variable

আপনি যখন চল রাশি (ভেরিয়েবল) যুক্ত করবেন, আপনি নাম, প্রকার, নিম্ন সীমা(আবদ্ধ ) এবং উপরের সীমা ((আবদ্ধ ) নির্দিষ্ট করতে পারেন।

[5]:
# Add variables
mod.binary_var(name="x")
mod.integer_var(name="y", lowerbound=-1, upperbound=5)
mod.continuous_var(name="z", lowerbound=-1, upperbound=5)
print(mod.prettyprint())
Problem name: my problem

Minimize
  0

Subject to
  No constraints

  Integer variables (1)
    -1 <= y <= 5

  Continuous variables (1)
    -1 <= z <= 5

  Binary variables (1)
    x

আপনি QuadraticProgram.minimize বা QuadraticProgram.maximize- দ্বারা নৈর্ব্যক্তিক অন্বয় (অব্জেক্টিভ ফাংশন) টি সেট করতে পারেন। আপনি তালিকা, ম্যাট্রিক্স বা অভিধানের সাথে লিনিয়ার এবং দ্বিঘাত (কোয়াড্রাটিক) পদগুলি নির্দিষ্ট করে একটি ধ্রুবক পদ পাশাপাশি লিনিয়ার এবং দ্বিঘাত (কোয়াড্রাটিক) নৈর্ব্যক্তিক অন্বয় (অব্জেক্টিভ ফাংশন) যুক্ত করতে পারেন।

টীকা: এল.পি বিন্যাসে দ্বিঘাত (কোয়াড্রাটিক) অংশটি একটি গুণক \(1/2\) দ্বারা মাপতে হবে সুতরাং, এল.পি ফর্ম্যাট হিসাবে মুদ্রণের সময়, দ্বিঘাত (কোয়াড্রাটিক) অংশটি প্রথমে ২ দ্বারা গুণিত হয় এবং তারপরে আবার ২ দিয়ে বিভক্ত হয়।

দ্বিঘাত (কোয়াড্রাটিক) প্রোগ্রামগুলির জন্য, এখানে 3 টি অংশ নির্দিষ্ট করতে হবে: একটি ধ্রুবক (অফসেট), একটি রৈখিক পদ (\(c^{T}x\)), এবং একটি দ্বিঘাত (কোয়াড্রাটিক) পদ (\(x^{T}Qx\))।

নীচের সেলটি দেখায় যে কীভাবে একটি অভিধান ব্যবহার করে কোনও নৈর্ব্যক্তিক অন্বয় (অব্জেক্টিভ ফাংশন) ঘোষণা করতে হয়। রৈখিক পদটির জন্য, অভিধানের কী-গুলি ভেরিয়েবল নামের সাথে মিলে যায় এবং সংশ্লিষ্ট মানগুলি সহগ হয়। দ্বিঘাত (কোয়াড্রাটিক) পদটির জন্য অভিধানের কী-গুলি দুটি চল রাশির (ভেরিয়েবল) সাথে গুণিত হওয়ার সাথে মিলে যায় এবং মানগুলি আবার সহগ হয়।

[6]:
# Add objective function using dictionaries
mod.minimize(constant=3, linear={"x": 1}, quadratic={("x", "y"): 2, ("z", "z"): -1})
print(mod.prettyprint())
Problem name: my problem

Minimize
  2*x*y - z^2 + x + 3

Subject to
  No constraints

  Integer variables (1)
    -1 <= y <= 5

  Continuous variables (1)
    -1 <= z <= 5

  Binary variables (1)
    x

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.

[7]:
# Add objective function using lists/arrays
mod.minimize(constant=3, linear=[1, 0, 0], quadratic=[[0, 1, 0], [1, 0, 0], [0, 0, -1]])
print(mod.prettyprint())
Problem name: my problem

Minimize
  2*x*y - z^2 + x + 3

Subject to
  No constraints

  Integer variables (1)
    -1 <= y <= 5

  Continuous variables (1)
    -1 <= z <= 5

  Binary variables (1)
    x

আপনি যথাক্রমে``Quadratic.objective.{constant, linear, quadratic}``, দেখে ধ্রুবক, রৈখিক পদ এবং দ্বিঘাত (কোয়াড্রাটিক) পদ ব্যবহার করতে পারেন। রৈখিক এবং দ্বিঘাত শর্তাবলী হিসাবে, আপনি একটি ডেন্স ম্যাট্রিক্স (to_array), একটি স্পার্স ম্যাট্রিক্স (coefficients`), এবং একটি অভিধান (``to_dict) পেতে পারেন। অভিধানগুলির জন্য, আপনি "কী" হিসাবে পরিবর্তনশীল সূচক বা নাম ব্যবহার করতে হবে তা নির্দিষ্ট করতে পারেন। টীকা: দ্বিঘাত (কোয়াড্রাটিক) পদগুলি সংকুচিতভাবে সংরক্ষণ করা হয়, উদাহরণস্বরূপ, {('x', 'y'): 1, ('y', 'x'): 2} , {('x', 'y'): 3}. হিসাবে সঞ্চিত হয়। আপনি to_array(symmetric=True) বা to_dict(symmetric=True) কল করে দ্বিঘাত (কোয়াড্রাটিক) পদকে প্রতিসম ম্যাট্রিক্স হিসাবে পেতে পারেন। আপনি যদি to_dict(name=True) কল করেন তবে আপনি একটি অভিধান পেতে পারেন যার কী-গুলি চলক নামের জোড়া।

[8]:
print("constant:\t\t\t", mod.objective.constant)
print("linear dict:\t\t\t", mod.objective.linear.to_dict())
print("linear array:\t\t\t", mod.objective.linear.to_array())
print("linear array as sparse matrix:\n", mod.objective.linear.coefficients, "\n")
print("quadratic dict w/ index:\t", mod.objective.quadratic.to_dict())
print("quadratic dict w/ name:\t\t", mod.objective.quadratic.to_dict(use_name=True))
print(
    "symmetric quadratic dict w/ name:\t",
    mod.objective.quadratic.to_dict(use_name=True, symmetric=True),
)
print("quadratic matrix:\n", mod.objective.quadratic.to_array(), "\n")
print("symmetric quadratic matrix:\n", mod.objective.quadratic.to_array(symmetric=True), "\n")
print("quadratic matrix as sparse matrix:\n", mod.objective.quadratic.coefficients)
constant:                        3
linear dict:                     {0: 1}
linear array:                    [1 0 0]
linear array as sparse matrix:
   (0, 0)       1

quadratic dict w/ index:         {(0, 1): 2, (2, 2): -1}
quadratic dict w/ name:          {('x', 'y'): 2, ('z', 'z'): -1}
symmetric quadratic dict w/ name:        {('y', 'x'): 1, ('x', 'y'): 1, ('z', 'z'): -1}
quadratic matrix:
 [[ 0  2  0]
 [ 0  0  0]
 [ 0  0 -1]]

symmetric quadratic matrix:
 [[ 0  1  0]
 [ 1  0  0]
 [ 0  0 -1]]

quadratic matrix as sparse matrix:
   (0, 1)       2
  (2, 2)        -1

রৈখিক এবং দ্বিঘাত (কোয়াড্রাটিক) সীমাবদ্ধতা যুক্ত করা / সরানো#

You can add linear constraints by setting name, linear expression, sense and right-hand-side value (rhs). You can use senses 'EQ', 'LE', and 'GE' as Docplex supports.

[9]:
# Add linear constraints
mod.linear_constraint(linear={"x": 1, "y": 2}, sense="==", rhs=3, name="lin_eq")
mod.linear_constraint(linear={"x": 1, "y": 2}, sense="<=", rhs=3, name="lin_leq")
mod.linear_constraint(linear={"x": 1, "y": 2}, sense=">=", rhs=3, name="lin_geq")
print(mod.prettyprint())
Problem name: my problem

Minimize
  2*x*y - z^2 + x + 3

Subject to
  Linear constraints (3)
    x + 2*y == 3  'lin_eq'
    x + 2*y <= 3  'lin_leq'
    x + 2*y >= 3  'lin_geq'

  Integer variables (1)
    -1 <= y <= 5

  Continuous variables (1)
    -1 <= z <= 5

  Binary variables (1)
    x

আপনি দ্বিঘাত (কোয়াড্রাটিক) সীমাবদ্ধতার পাশাপাশি নৈর্ব্যক্তিক অন্বয় (অব্জেক্টিভ ফাংশন) এবং রৈখিক (লিনিয়ার) সীমাবদ্ধতা যুক্ত করতে পারেন।.

[10]:
# Add quadratic constraints
mod.quadratic_constraint(
    linear={"x": 1, "y": 1},
    quadratic={("x", "x"): 1, ("y", "z"): -1},
    sense="==",
    rhs=1,
    name="quad_eq",
)
mod.quadratic_constraint(
    linear={"x": 1, "y": 1},
    quadratic={("x", "x"): 1, ("y", "z"): -1},
    sense="<=",
    rhs=1,
    name="quad_leq",
)
mod.quadratic_constraint(
    linear={"x": 1, "y": 1},
    quadratic={("x", "x"): 1, ("y", "z"): -1},
    sense=">=",
    rhs=1,
    name="quad_geq",
)
print(mod.prettyprint())
Problem name: my problem

Minimize
  2*x*y - z^2 + x + 3

Subject to
  Linear constraints (3)
    x + 2*y == 3  'lin_eq'
    x + 2*y <= 3  'lin_leq'
    x + 2*y >= 3  'lin_geq'

  Quadratic constraints (3)
    x^2 - y*z + x + y == 1  'quad_eq'
    x^2 - y*z + x + y <= 1  'quad_leq'
    x^2 - y*z + x + y >= 1  'quad_geq'

  Integer variables (1)
    -1 <= y <= 5

  Continuous variables (1)
    -1 <= z <= 5

  Binary variables (1)
    x

আপনি নৈর্ব্যক্তিক অন্বয় (অব্জেক্টিভ ফাংশন) এর মতন করেই রৈখিক এবং দ্বিঘাত (কোয়াড্রাটিক) শর্তাদির প্রবেশাধিকার পেতে পারেন ।

[11]:
lin_geq = mod.get_linear_constraint("lin_geq")
print("lin_geq:", lin_geq.linear.to_dict(use_name=True), lin_geq.sense, lin_geq.rhs)
quad_geq = mod.get_quadratic_constraint("quad_geq")
print(
    "quad_geq:",
    quad_geq.linear.to_dict(use_name=True),
    quad_geq.quadratic.to_dict(use_name=True),
    quad_geq.sense,
    lin_geq.rhs,
)
lin_geq: {'x': 1.0, 'y': 2.0} ConstraintSense.GE 3
quad_geq: {'x': 1.0, 'y': 1.0} {('x', 'x'): 1.0, ('y', 'z'): -1.0} ConstraintSense.GE 3

আপনি রৈখিক / দ্বিঘাত (কোয়াড্রাটিক) সীমাবদ্ধতাগুলি remove_linear_constraint এবং remove_quadratic_constraint` দ্বারাও মুছে ফেলতে পারেন ।

[12]:
# Remove constraints
mod.remove_linear_constraint("lin_eq")
mod.remove_quadratic_constraint("quad_leq")
print(mod.prettyprint())
Problem name: my problem

Minimize
  2*x*y - z^2 + x + 3

Subject to
  Linear constraints (2)
    x + 2*y <= 3  'lin_leq'
    x + 2*y >= 3  'lin_geq'

  Quadratic constraints (2)
    x^2 - y*z + x + y == 1  'quad_eq'
    x^2 - y*z + x + y >= 1  'quad_geq'

  Integer variables (1)
    -1 <= y <= 5

  Continuous variables (1)
    -1 <= z <= 5

  Binary variables (1)
    x

You can substitute some of variables with constants or other variables. More precisely, QuadraticProgram has a method substitute_variables(constants=..., variables=...) to deal with the following two cases.

  • \(x \leftarrow c\): when constants have a dictionary {x: c}.

  • \(x \leftarrow c y\): when variables have a dictionary {x: (y, c)}.

চল রাশি প্রতিস্থাপন করা#

[13]:
sub = mod.substitute_variables(constants={"x": 0}, variables={"y": ("z", -1)})
print(sub.prettyprint())
Problem name: my problem

Minimize
  -z^2 + 3

Subject to
  Linear constraints (2)
    -2*z <= 3  'lin_leq'
    -2*z >= 3  'lin_geq'

  Quadratic constraints (2)
    z^2 - z == 1  'quad_eq'
    z^2 - z >= 1  'quad_geq'

  Continuous variables (1)
    -1 <= z <= 1

নিম্ন সীমা বা উপরের সীমাগুলির কারণে যদি ফলস্বরূপ সমস্যাটি অক্ষম হয় তবে পদ্ধতিগুলি স্ট্যাটাস Status.INFEASIBLE কে ফিরিয়ে দেয়। আমরা চল রাশি `` x`` কে -1 এর সাথে প্রতিস্থাপন করার চেষ্টা করি, তবে -1 `` x`` (0 <= `` x`` <= 1) এর সীমার বাইরে। সুতরাং, এটি Status.INFEASIBLE ফিরিয়ে দেয়।

[14]:
sub = mod.substitute_variables(constants={"x": -1})
print(sub.status)
Infeasible substitution for variable: x
QuadraticProgramStatus.INFEASIBLE

আপনি একাধিক বার চল রাশি প্রতিস্থাপন করতে পারবেন না। এই ক্ষেত্রে এটি ত্রুটি উত্থাপন করে।

[15]:
from qiskit_optimization import QiskitOptimizationError

try:
    sub = mod.substitute_variables(constants={"x": -1}, variables={"y": ("x", 1)})
except QiskitOptimizationError as e:
    print("Error: {}".format(e))
Error: 'Cannot substitute by variable that gets substituted itself: y <- x 1'

Note: When you display your problem as LP format using export_as_lp_string, Binaries denotes binary variables and Generals denotes integer variables. If variables are not included in either Binaries or Generals, such variables are continuous ones with default lower bound = 0 and upper bound = infinity. Note that you cannot use 'e' or 'E' as the first character of names due to the specification of LP format.

[16]:
mod = QuadraticProgram()
mod.binary_var(name="e")
mod.binary_var(name="f")
mod.continuous_var(name="g")
mod.minimize(linear=[1, 2, 3])
print(mod.export_as_lp_string())
\ This file has been generated by DOcplex
\ ENCODING=ISO-8859-1
\Problem name: CPLEX

Minimize
 obj: _e + 2 f + 3 g
Subject To

Bounds
 0 <= _e <= 1
 0 <= f <= 1

Binaries
 _e f
End

[17]:
import qiskit.tools.jupyter

%qiskit_version_table
%qiskit_copyright

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

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.

[ ]: