Optimization Problems
Introduction
In our daily lives, we solve several optimization problems, consciously and unconsciously. Reducing utility bills, making investments with maximum returns, choosing a route with less traffic are examples. Such problems, where we chose the best possible solution from a set of alternatives, are called optimization problems.
The best way to solve an optimization problem is to create a mathematical model, often described using the following parameters.
An objective function or the cost function that minimizes or maximizes a quantity and it is a measure of the performance of the system.
The variables of the system.
The allowable range of the variables are the constraints of the system that needs to be satisfied.
Let us illustrate this with a pedagogical example.
Example
Find the dimensions of a tray with the maximum volume, which can be made from a cardboard of size 20cm ×40cm.
Solution
A tray can be constructed by folding the edges of the cardboard and joining the corners, as illustrated in the following figure. Depending upon the extent of the fold (\(x\) in the figure), the volume of the tray changes. The goal is to find the optimal extent of the fold (that is, the height of the tray), so as to maximize the volume of the tray.
We can solve this problem mathematically. Let \(x\) be the height of the tray and \(V\) be its volume. Our goal is to maximize the volume \(V\) of the tray. The volume of the tray can be calculated by multiplying the length, breadth, and height.
Indeed, the volume of the tray needs to be \(>0\), which means \(x>0\). The height of the tray should also be lower than one-half of the breadth. Hence the constraint of the system is \(0<x<10\). Since \(V\left(x\right)\) is a continuous function over the interval \(0<x<10\), it must have an absolute maximum and a minimum value. We can find these values using calculus by taking the derivative of \(V\left(x\right)\) and equating the derivative to zero. The derivative of \(V\left(x\right)\) is given by:
Where \(V^\prime\left(x\right)\) is the first order derivative of \(V\left(x\right)\) over \(x\). The maximum and minimum values of \(x\) can be found by equating this equation to zero.
The above is a quadratic equation (that is, a polynomial equation of degree 2) of the form \(ax^2+bx+c=0\). Recall that the solution to a quadratic equation of the standard form can be calculated using the quadratic formula \(x=\ \frac{-b\ \pm\sqrt{b^2-4ac}}{2a}\). Using this formula, the solution to our equation can be written as:
Solving this equation, we find that the values of \(x\) are \(10+\ \frac{10}{\sqrt3}\) and \(10-\ \frac{10}{\sqrt3}\). Out of these two values, \(10+\ \frac{10}{\sqrt3}\) is outside our range for \(x\). Hence, we can say that \(x=10-\ \frac{10}{\sqrt3}\ \approx4.20\) is the optimal solution. Once we know \(x\), the dimensions of the tray and its volume can be calculated easily, which we leave as a simple exercise to the readers.
Combinatorial optimizations
Combinatorial optimizations are a class of optimization problems where the solution space is discrete. The algorithms that solve combinatorial optimization problems find the optimal or close to the optimal solution from a finite set of possible solutions. Such algorithms reduce the solution space to make the search faster and find the best possible solution even if an optimal solution cannot be found efficiently. The optimality of the solution is defined by an objective or cost function \(C\) that needs to be minimized or maximized.
Mathematically, a combinatorial optimization problem maximizes (or minimizes) \(C\left(x\right)\), where \(x\) is a variable in some domain \(S\), a discrete but large configuration space. Note that \(x\) could be constrained to a subset \(S\subset D\) of possible solutions. Combinatorial optimizations have several industrial applications. The following are some pedagogical examples.
Resource utilization problems: Sharing resources efficiently among tasks, such that all tasks can be completed in a given time.
Bin packing problem: When given a set of bins, each with a specific volume, the goal is to pack objects of different volumes into a finite number of bins in such a way that the number of bins used is minimized.
Traveling salesman problem: Given the latitude and longitude of a list of cities, the goal is to find the shortest path that visits all cities only once.
Boolean satisfiability problem: Check whether the variables of a Boolean expression can be consistently assigned true or false values in such a way that the Boolean expression evaluates true.
Such problems are considered NP-hard problems. Since the search space is usually large, these problems cannot be efficiently solved using brute-force methods. There are some heuristic and exact algorithms available, and these problems can be approximated on a classical computer with a very low degree of error.
Binary optimization problems
Binary optimization problems are combinatorial optimization problems where the decision variables can take only values [1] \(\left\{0,1\right\}\).
The goal of a binary optimization problem is to maximize the objective function.
where the \(n\)-bit binary string \(z=\ z_1z_2z_3\ldots z_n\). The function \(C_\alpha\left(z\right)\) queries the binary string \(z\) to check if it meets \(m\) constraints, such that,
There are \(2^n\) available combinations for the binary string \(z\). Our goal is to find the \(z\) that maximizes the objective function \(C\left(z\right)\). Classically, this can be solved by calling \(C_\alpha\left(z\right)\) with each possible \(z\), which has an exponential complexity \(O\left(2^n\right)\). However, there are some approximate solutions to this problem, and we shall study a quantum version in the following sections. The maximum cut (Max-Cut) problem and the \(0-1\) knapsack problem are some examples of binary optimization problems.
Footnotes