Universal Quantum Speedup for Branch-and-Bound Branch-and-Cut and Tree-Search Algorithms Shouvanik Chakrabarti Pierre Minssen Romina Yalovetzky and Marco Pistoia

2025-05-06 0 0 932.1KB 25 页 10玖币

侵权投诉

Universal Quantum Speedup for Branch-and-Bound,

Branch-and-Cut, and Tree-Search Algorithms

Shouvanik Chakrabarti, Pierre Minssen, Romina Yalovetzky, and Marco Pistoia

Global Technology Applied Research, JPMorgan Chase & Co.

Abstract

Mixed Integer Programs (MIPs) model many optimization problems of interest in Computer Science,

Operations Research, and Financial Engineering. Solving MIPs is NP-Hard in general, but several solvers

have found success in obtaining near-optimal solutions for problems of intermediate size. Branch-and-

Cut algorithms, which combine Branch-and-Bound logic with cutting-plane routines, are at the core of

modern MIP solvers. Montanaro proposed a quantum algorithm with a near-quadratic speedup compared

to classical Branch-and-Bound algorithms in the worst case, when every optimal solution is desired. In

practice, however, a near-optimal solution is satisfactory, and by leveraging tree-search heuristics to search

only a portion of the solution tree, classical algorithms can perform much better than the worst-case

guarantee. In this paper, we propose a quantum algorithm, Incremental-Quantum-Branch-and-Bound,

with universal near-quadratic speedup over classical Branch-and-Bound algorithms for every input, i.e., if

a classical Branch-and-Bound algorithm has complexity Qon an instance that leads to solution depth d,

Incremental-Quantum-Branch-and-Bound oﬀers the same guarantees with a complexity of ˜

O(√Qd). Our

results are valid for a wide variety of search heuristics, including depth-based, cost-based, and A∗heuristics.

Corresponding universal quantum speedups are obtained for Branch-and-Cut as well as general heuristic

tree search. Our algorithms are directly comparable to MIP solving routines in commercial solvers, and

guarantee near quadratic speedup whenever Qd. We use numerical simulation to verify that Qdfor

typical instances of the Sherrington-Kirkpatrick model, Maximum Independent Set, and Mean-Variance

Portfolio Optimization; as well as to extrapolate the dependence of Qon input size parameters. This allows

us to project the typical performance of our quantum algorithms for these important problems.

1 Introduction

An Integer Program (IP) is a mathematical optimization or feasibility problem in which some or all of

the variables are restricted to be integers. A problem where some of the variables are continuous is

often referred to as a Mixed Integer Program (MIP). IPs and MIPs are ubiquitous tools in many areas of

Computer Science, Operations Research, and Financial Engineering. They have been used to model and solve

problems such as combinatorial optimization [1], Hamiltonian ground-state computation [2,3], network

design [4,5], resource analysis [6], and scheduling [7,8], as well as various problems in ﬁnance, including

cash-ﬂow management, combinatorial auctions, portfolio optimization with minimum transaction levels or

diversiﬁcation constraints [9]. Integer Programming is NP-Hard in general, but modern solvers [10,11] are

often quite successful at solving practical problems of intermediate sizes, which has led to the development

of the aforementioned applications.

The practicality of IP solvers is due to a host of techniques that are employed to bring down the program’s

execution time, which remains exponential in most cases, but often with signiﬁcant speedups over naive

methods. Such techniques include rounding schemes, cutting-plane methods, search and backtracking

schemes, Bender decomposition techniques, and Branch-and-Bound algorithms. There is some overlap

between these methods, which are often used in combination for best performance. In recent years, Branch-

and-Cut algorithms [9, Chapter 11] have emerged as the central technique for solving MIPs. Notably, the

core method for the two most common commercially available MIP solvers, Gurobi [10] and CPLEX [11],

arXiv:2210.03210v1 [quant-ph] 6 Oct 2022

is a Branch-and-Cut procedure. The phrase Branch-and-Cut refers to the combination of two techniques,

as Branch-and-Cut is a Branch-and-Bound [12] algorithm augmented with cutting-plane methods. Branch-

and-Cut algorithms have the desirable feature that while they proceed, they maintain a bound on the gap

between the quality of the solution found at any point and the optimal solution. This allows for early

termination whenever the gap falls to 0 or below a precision parameter input by the user.

Due to the ubiquity and usefulness of Branch-and-Cut algorithms, it is natural to ask whether quantum

algorithms can provide a provable advantage over classical algorithms for Branch-and-Bound or, more

generally, Branch-and-Cut. In recent years, quantum algorithms have been shown to be provably advanta-

geous for many continuous optimization problems, including Linear Systems [13], Zero-Sum Games [14],

Generalized Matrix Games [15], Semi-deﬁnite Programs [16], and General Zeroth-Order Convex Optimiza-

tion [17,18], as well as some discrete optimization problems, such as Dynamic Programming [19] and

Backtracking [20]. There are also conditional provable speedups for some interior point methods, for ex-

ample for Linear Programs (LPs), Semi-Deﬁnite Programs (SDPs) [21], and Second-Order Cone Programs

(SOCPs) [21].

Montanaro [22] proposed an algorithm with a provable near-quadratic quantum speedup over the worst-

case classical Branch-and-Bound algorithms where the task is to ensure that all optimal solutions are found.

However, this quantum algorithm does not accommodate early stopping based on the gap, thereby not

accounting for the fact that, in most practical situations, one is satisﬁed with any solution whose quality is

within some precision parameter of the optimal. Therefore, the true performance of classical Branch-and-

Bound on a problem can be very diﬀerent from the worst case considered by Montanaro. Furthermore,

simply estimating the worst-case classical performance can be much more computationally intensive than

simply ﬁnding an approximate solution to an IP. This makes it diﬃcult to know whether the quantum

advantage holds for any practical problem, as well as to estimate what the true expected performance of the

quantum algorithm would be.

Therefore, we look for a stronger notion of quantum speedup, which we term “universal speedup”. We

say that a quantum algorithm for a task has a universal speedup over a classical algorithm if the speedup is

over the actual performance of the classical algorithm in every case. Informally, this means that if a classical

algorithm gets “lucky” on a particular family of inputs, so does the associated quantum algorithm. Universal

speedup also allows the true performance of the quantum algorithm to be empirically inferred from that of

the classical variant, as every classical execution has a provably more eﬃcient quantum variant.

Ambainis and Kokainis [23] gave a universal speedup for the backtracking problem. The question of whether

such a speedup is possible for Branch-and-Bound has been left open in Montanaro’s work [22]. The main

goal of this paper is to shed a light on this question.

1.1 Classical Branch-and-Cut

1.1.1 Branch-and-Bound

While there are many possible Branch-and-Bound algorithms (see [24,25] for a survey of techniques), they

all follow a formally similar approach, where an input MIP is solved using a tree of relaxed optimization

problems that can be solved eﬃciently: each of them yields a solution that may not be feasible. If the solution

is not feasible, it is then used to produce new relaxed sub-problems, each of which produces a solution of

worse quality than its parent, but is chosen so that the solution obtained is more likely to be feasible for the

original MIP. Eventually, this process leads to feasible solutions, which form the leaves of the explored tree.

Classical Branch-and-Bound methods search for the leaf with the best solution quality.

Treating the relaxed problems as the nodes of a tree allows a Branch-and-Bound algorithm to be described

as exploring a Branch-and-Bound tree, speciﬁed by the following parameters:

1. The root N0of the tree

2. A branching function branch that for any input node Nreturns the set of the children of N

3. A cost function cost mapping any node to a real number

For a tree Tto be a valid Branch-and-Bound tree, it must be ﬁnite, and satisfy the so called Branch-and-Bound

condition, which states that for any node N∈ T , we have cost(N)≤minN0∈branch(N){cost(N0)}, i.e., any

node has lower cost than its children. Note that these conditions simply formalize the description above: we

choose cost to capture the quality of the solution at a node (where lower is better). In this correspondence, a

node represents a more restricted subproblem than its parent and must therefore have a higher cost.

Given this deﬁnition, we have the following abstract formulation of the Branch-and-Bound problem:

Deﬁnition 1.1 (Abstract Branch-and-Bound Problem).Given a tree Twith root N0, error parameter , and oracles

branch,cost satisfying the Branch-and-Bound condition, return a node Nso that Nis a leaf, and for any leaf Lof

T,cost(N)≤cost(L) + .

An example of a Branch-and-Bound speciﬁcation is in Mixed Integer Programming with a linear, convex

quadratic, or general convex function. This situation is common in ﬁnancial engineering, e.g., for portfolio

optimization. Consider an MIP Iwhose objective is to minimize a function f:F → R, where F ⊆ RD1×ZD2

is speciﬁed by a set of mconstraints. A relaxed problem can be obtained by expanding the domain of

optimization, for example by removing the integrality constraints on the last D2variables. The resulting

relaxed problem can be solved eﬃciently, i.e., in time poly(m, D), where D=D1+D2. Each node of the

Branch-and-Bound tree contains such a relaxed problem. Speciﬁcally, for each node N,cost(N)is deﬁned

as the value of the objective at the solution of the relaxed problem at N. We generate sub-problems as

follows. Let the optimal solution ~x at Nhave a coordinate xj:j > D1with value c /∈Z. We obtain new

problems by adding either xj≤ bccor xj≥ dceas constraints to the relaxed problem at N.

A Branch-and-Bound algorithm proceeds by searching the Branch-and-Bound tree using a search heuristic

Hto ﬁnd the leaf with minimum cost. We use the following terminology in the rest of the paper. The nodes

of the tree are grouped into three categories: “undiscovered”, “active”, and “explored”:

1. Undiscovered nodes are those that the algorithm has not seen yet, i.e., they have not been returned as

the output of any branch oracle call.

2. An active node is one that has been discovered by the algorithm, but has not had the branch oracle

called on it, i.e., the node has been discovered, but its children have not.

3. An explored node is one that has been discovered and whose children have also been discovered by

calling the branch oracle on the node itself.

With this setup, we can describe the algorithm as follows for a tree T:

1. The list of active nodes active is initialized to contain only the root node, N0.

2. The next candidate for exploring is returned by applying the search heuristic, H, to the list Lactive.

Once a node is explored, it is removed from Lactive and its children are added.

3. During exploration, two quantities are maintained:

(a) The incumbent: the minimum cost of any discovered leaf. This is an upper bound on the possible

value of the optimal solution.

(b) The best-bound: the minimum cost of any active node. Any newly discovered node will have a

greater cost than this so this is a lower bound on the optimal solution.

4. The gap between the incumbent value and the best-bound is an upper bound on the sub-optimality

of the incumbent solution. Thus, when the gap falls below some , the incumbent can be returned as

an -approximate solution.

1.1.2 Cutting Planes

Consider a MIP with feasible set Fand let F0be the feasible set with its integrality constraints relaxed. A

cutting plane is a hyperplane constraint that can be added, such that the true feasible set Fis unchanged, but

some infeasible solutions are removed from the relaxed feasible set F0. A cutting-plane algorithm repeatedly

adds cutting planes to the relaxed MIP until the solution to the relaxed problem is feasible for the original

(unrelaxed) MIP. Since no such solutions are removed due the cutting planes, the solution thus obtained is

optimal. Branch-and-Cut combines cutting planes with Branch-and-Bound. As the Branch-and-Bound tree

Tis searched, cutting-plane methods are used at various nodes to obtain new cutting planes. A cutting

plane at a node Nis local if it is only a valid cutting plane for the sub-tree of Trooted at N, and global if it

applies to the whole tree. A classical Branch-and-Cut problem simply searches the Branch-and-Bound tree

as discussed previously and, when a cutting plane is found, adds it to the constraints.

1.1.3 Search Heuristics

A Branch-and-Bound algorithm requires a search heuristic Hto specify which active node is to be explored

next. For a heuristic Hto be practically usable, it must have an implicit description that does not require

explicitly writing down a full permutation over Telements (where Tis often exponential in problem-size

parameters).

In the rest of the paper, we restrict ourselves to the class of search heuristics consisting of those that rank

nodes based on a combination of local information (that can be computed by calling branch,cost at the node

itself) and information that can be obtained from the output of branch,cost at the parents of the node. We

deﬁne the corresponding family of heuristics as follows:

Deﬁnition 1.2 (Branch-Local Heuristics).ABranch-Local Heuristic for Branch-and-Bound tree, is any heuristic

that ranks nodes in ascending order of the value of some function heur, where for any node Nat depth d(N)in the

tree, with path r→n1→ ··· → nd(N)−1→Nfrom the root,

heur(N) = f(hlocal(N),hparent(r),hparent(n1). . . , hparent(nd(n)−1), d(N)) (1.1)

where each of hlocal,hparent makes a constant number of queries to branch,cost, and fis a function with no

dependence on N.

The above deﬁnition captures all commonly used search heuristics that we are aware of, including the three

following main categories:

1. Depth-ﬁrst heuristics The heuristic his speciﬁed by a sub-function h0:N 7→ S(2) that orders the

children of any node. The tree is explored via a depth-ﬁrst search where among two children of the

same node, the child ordered ﬁrst by h0is explored ﬁrst.

2. Cost-based heuristics The heuristic ranks nodes simply by the value of the cost function. Despite its

simplicity, this is the most commonly used search heuristic for Branch-and-Bound and is used by both

Gurobi and CPLEX [10,11]. A simple generalization is to consider arbitrary functions of the cost.

3. A∗heuristics These heuristics rank nodes by the value of heur(N) = hcost(N) + d(N), where

hcost(n)makes a constant number of queries to branch and cost, and d(N)is the depth of N.

The family of heuristics in Deﬁnition 1.2 is probably broader than needed to include all search methods used

in practice. In particular, it includes all the search strategies for Branch-and-Bound discussed in [25, Section

3], and for parallel Branch-and-Bound in [26]. Nevertheless, it is possible that some Branch-and-Bound

algorithm uses a heuristic that does not fall under this deﬁnition and such algorithms will not be covered by

our results. Finally, we note that Deﬁnition 1.2 does not require the explored tree to be a Branch-and-Bound

tree and can be easily extended to any tree, even one where there is no cost oracle, in which case we simply

take cost to be a constant. In the presentation, we will therefore often omit explicitly passing cost to

functions unless required.

1.2 Discussion of Existing Results

The primary existing result on Branch-and-Bound algorithms is the following due to Montanaro [22].

Theorem 1.1 ([22, Theorem 1]).Consider a Branch-and-Bound tree Tspeciﬁed by oracles branch,cost. Let dbe

the depth of T, and the cost of the solution node be cmin. Let cmax be a given upper bound on the cost of any explored

node. Assume further that Thas Tmin nodes with cost ≤cmin. Then there exists a quantum algorithm solving the

Branch-and-Bound problem on Twith failure probability at most δusing ˜

O√Tmind3/2log(cmax)1

δ2queries to

branch,cost.

We note that, due to the subsequent reﬁnement of a tree search algorithm by Apers, et al. [27], the query

complexity in Theorem 1.1 is trivially improved to ˜

O√Tmindlog(cmax)1

δ2. A classical Branch-and-Bound

algorithm that is required to output all optimal solutions (a stronger requirement than in Deﬁnition 1.1

must search at least Tmin nodes of the Branch-and-Bound tree, thereby making at least Tmin queries to

branch,cost.Theorem 1.1 thus provides a nearly quadratic speedup for this scenario, whenever d√Tmin.

In most practical problems Tmin is exponentially larger than dso this condition is satisﬁed.

The problem of returning a single approximate solution (as in Deﬁnition 1.1) may not require O(Tmin)

queries to branch,cost, and it is not clear whether the speedup from Theorem 1.1 does not automatically

apply. In fact, even if the error parameter is 0, the early termination of Branch-and-Bound may be able to ﬁnd

an exact solution without exploring O(√Tmin)queries, as whenever the gap falls to 0the existing incumbent

solution has been proved optimal. True worst-case bounds on classical algorithms for Deﬁnition 1.1 are hard

to characterize analytically, and infeasible to infer from empirical data. Furthermore, the true performance

of the algorithm on practical families of instances can be much (even exponentially) better than the worst

case. Thus even if Theorem 1.1 were to provide a worst case speedup, this may not translate to a speedup

for problems of interest. Finally, the algorithm in Theorem 1.1 is easily augmented with local cutting planes

by modifying the branch oracle, but cannot be used with global cutting planes as the whole algorithm has

only one stage and cutting planes discovered at a node are therefore unavailable to any nodes outside the

subtree containing the descendants of that node.

A closely associated problem to Branch-and-Bound is that of tree search. Backtracking can be abstractly

formulated as the problem of ﬁnding a marked node in a tree. Ambainis and Kokainis demonstrated a

universal speedup for backtracking when the tree is explored using an depth-ﬁrst heuristic, as is common in

backtracking algorithms. We state a version of their result (equivalent to [23, Theorem 7])

Theorem 1.2. Consider a tree Twith depth dspeciﬁed by a branch oracle, and a marking function fthat maps

nodes of the tree to 0 or 1, where a node nis marked if f(n) = 1. Assume that at least one node is marked. Then let

Abe a classical algorithm that explores Qnodes (O(Q)queries to branch) of Tusing some depth-ﬁrst heuristic and

outputs a marked node in T, and otherwise returns 0. For 0≤δ≤1, there exists a quantum algorithm that makes

O√Qd3/2log2nlog(Q)

δqueries to branch and with probability at least 1−δ, returns the same output as A.

In contrast, the best known worst-case quantum algorithm [27] for tree search uses ˜

O(√T d log(1/δ)) queries

to branch. We note that Theorem 1.2 has a worse dependence on the depth d(by a factor of √d). The better

ddependence cannot be obtained by a trivial modiﬁcation of Theorem 1.2 and the question of whether

such a dependence is possible is left open in [27]. The universal speedup is also valid only for depth-ﬁrst

heuristics.

1.3 Contributions of This Work

Branch-and-Bound. Our main result is a universal quantum speedup over all classical Branch-and-Bound

algorithms that explore Branch-and-Bound trees using Branch-Local Heuristics (Deﬁnition 1.2). The quan-

tum algorithm must depend on the heuristic used classically. We therefore introduce a meta-algorithm,

Incremental-Quantum-Branch-and-Bound, that transforms a classical algorithm Ainto a quantum

algorithm Incremental-Quantum-Branch-and-BoundA, with the following guarantee:

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

UniversalQuantumSpeedupforBranch-and-Bound,Branch-and-Cut,andTree-SearchAlgorithmsShouvanikChakrabarti,PierreMinssen,RominaYalovetzky,andMarcoPistoiaGlobalTechnologyAppliedResearch,JPMorganChase&Co.AbstractMixedIntegerPrograms(MIPs)modelmanyoptimizationproblemsofinterestinComputerScience,OperationsR...

展开>> 收起<<

Universal Quantum Speedup for Branch-and-Bound Branch-and-Cut and Tree-Search Algorithms Shouvanik Chakrabarti Pierre Minssen Romina Yalovetzky and Marco Pistoia.pdf

共25页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Universal Quantum Speedup for Branch-and-Bound Branch-and-Cut and Tree-Search Algorithms Shouvanik Chakrabarti Pierre Minssen Romina Yalovetzky and Marco Pistoia

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: