Julian Yarkony

In this research we consider an approach for improving the efficiency and tightness of column generation (CG) methods for solving vehicle routing problems. This work builds upon recent work on Local Area (LA) routes. LA routes rely on pre-computing (prior to any call to pricing during CG) the lowest cost elementary sub-route (called an LA arc) for each tuple consisting of the following: (1) a customer to begin the LA arc, (2) a customer to end the LA arc, which is far from the first customer… Show more

In this research we consider an approach for improving the efficiency and tightness of column generation (CG) methods for solving vehicle routing problems. This work builds upon recent work on Local Area (LA) routes. LA routes rely on pre-computing (prior to any call to pricing during CG) the lowest cost elementary sub-route (called an LA arc) for each tuple consisting of the following: (1) a customer to begin the LA arc, (2) a customer to end the LA arc, which is far from the first customer, (3) a small set of intermediate customers nearby the first customer. LA routes are constructed by concatenating LA arcs where the final customer in a given LA arc is the first customer in the subsequent LA arc. A Decremental State Space Relaxation (DSSR) method is used to construct the lowest reduced cost elementary route during the pricing step of CG. We demonstrate that LA route based solvers can be used to efficiently tighten the standard set cover vehicle routing relaxation using a variant of subset row inequalities (SRI). However, SRI are difficult to use in practice as they alter the structure of the pricing problem in a manner that makes pricing difficult. SRI in their simplest form state that the number of routes servicing two or three members of a given set of three customers cannot exceed one. We introduce LA-SRI, which in their simplest form state that the number of LA arcs (in routes in the solution) including two or more members of a set of three customers (excluding the final customer of the arc) cannot exceed one. We exploit the structure of LA arcs inside a Graph Generation based formulation to accelerate convergence of CG. We apply our LA-SRI to CVRP and demonstrate that we tighten the LP relaxation, often making it equal to the optimal integer solution, and solve the LP efficiently without altering the structure of the pricing problem. Show less

Column generation (CG) algorithms are well known to suffer from convergence issues due, mainly, to the degenerate structure of their master problem and the instability associated with the dual variables involved in the process. In the literature, several strategies have been proposed to overcome this issue. These techniques rely either on the modification of the standard CG algorithm or on some prior information about the set of dual optimal solutions. In this paper, we propose a new… Show more

Column generation (CG) algorithms are well known to suffer from convergence issues due, mainly, to the degenerate structure of their master problem and the instability associated with the dual variables involved in the process. In the literature, several strategies have been proposed to overcome this issue. These techniques rely either on the modification of the standard CG algorithm or on some prior information about the set of dual optimal solutions. In this paper, we propose a new stabilization framework, which relies on the dynamic generation of aggregated rows from the CG master problem. To evaluate the performance of our method and its flexibility, we consider instances of three different problems, namely, vehicle routing with time windows (VRPTW), bin packing with conflicts (BPPC), and multiperson pose estimation (MPPEP). When solving the VRPTW, the proposed stabilized CG method yields significant improvements in terms of CPU time and number of iterations with respect to a standard CG algorithm. Huge reductions in CPU time are also achieved when solving the BPPC and the MPPEP. For the latter, our method has shown to be competitive when compared with a tailored method. Show less

We address the problem of accelerating column generation (CG) for set-covering formulations via dual optimal inequalities (DOIs). We study two novel classes of DOIs, which are referred to as Flexible DOIs (F-DOIs) and Smooth-DOIs (S-DOIs), respectively (and jointly as SF-DOIs). F-DOIs provide rebates for covering items more than necessary. S-DOIs describe the payment of a penalty to permit the undercoverage of items in exchange for the overinclusion of other items. Unlike other classes of DOIs… Show more

We address the problem of accelerating column generation (CG) for set-covering formulations via dual optimal inequalities (DOIs). We study two novel classes of DOIs, which are referred to as Flexible DOIs (F-DOIs) and Smooth-DOIs (S-DOIs), respectively (and jointly as SF-DOIs). F-DOIs provide rebates for covering items more than necessary. S-DOIs describe the payment of a penalty to permit the undercoverage of items in exchange for the overinclusion of other items. Unlike other classes of DOIs from the literature, the S-DOIs and F-DOIs rely on very little problem-specific knowledge and, as such, have the potential to be applied to a vast number of problem domains. In particular, we discuss the application of the new DOIs to three relevant problems: the single-source capacitated facility location problem, the capacitated p-median problem, and the capacitated vehicle-routing problem. We provide computational evidence of the strength of the new inequalities by embedding them within a column-generation solver for these problems. Substantial speedups can be observed as when compared with a nonstabilized variant of the same CG procedure to achieve the linear-relaxation lower bound on problems with dense columns and structured assignment costs. Show less

Significant progress has been made in the field of computer vision because of the development of supervised machine learning algorithms, which efficiently extract information from high-dimensional data such as images and videos. Such techniques are particularly effective at recognizing the presence or absence of entities in the domains where labeled data are abundant. However, supervised learning is not sufficient in applications where one needs to annotate each unique entity in crowded scenes… Show more

Significant progress has been made in the field of computer vision because of the development of supervised machine learning algorithms, which efficiently extract information from high-dimensional data such as images and videos. Such techniques are particularly effective at recognizing the presence or absence of entities in the domains where labeled data are abundant. However, supervised learning is not sufficient in applications where one needs to annotate each unique entity in crowded scenes respecting known domain-specific structures of those entities. This problem, known as data association, provides fertile ground for the application of combinatorial optimization. In this review paper, we present a unified framework based on column generation for some computer vision applications, namely multiperson tracking, multiperson pose estimation, and multicell segmentation, which can be formulated as set packing problems with a massive number of variables. To solve them, column generation algorithms are applied to circumvent the need to enumerate all variables explicitly. To enhance the solution process, we provide a general approach for applying subset-row inequalities to tighten the formulations and introduce novel dual-optimal inequalities to reduce the dual search space. The proposed algorithms and their enhancements are successfully applied to solve the three aforementioned computer vision problems and achieve superior performance over benchmark approaches. The common framework presented allows us to leverage operations research methodologies to efficiently tackle computer vision problems. Show less

In this paper, we introduce a new optimization approach to Entity Resolution. Traditional approaches tackle entity resolution with hierarchical clustering, which does not benefit from a formal optimization formulation. In contrast, we model entity resolution as correlation-clustering, which we treat as a weighted set-packing problem and write as an integer linear program (ILP). In this case, sources in the input data correspond to elements and entities in output data correspond to… Show more

In this paper, we introduce a new optimization approach to Entity Resolution. Traditional approaches tackle entity resolution with hierarchical clustering, which does not benefit from a formal optimization formulation. In contrast, we model entity resolution as correlation-clustering, which we treat as a weighted set-packing problem and write as an integer linear program (ILP). In this case, sources in the input data correspond to elements and entities in output data correspond to sets/clusters. We tackle optimization of weighted set packing by relaxing integrality in our ILP formulation. The set of potential sets/clusters can not be explicitly enumerated, thus motivating optimization via column generation. In addition to the novel formulation, we also introduce new dual optimal inequalities (DOI), that we call flexible dual optimal inequalities, which tightly lower-bound dual variables during optimization and accelerate column generation. We apply our formulation to entity resolution (also called de-duplication of records), and achieve state-of-the-art accuracy on two popular benchmark datasets. Our F-DOI can be extended to other weighted set-packing problems. Show less

We present a novel approach to solve dynamic programs (DP), which are frequent in computer vision, on tree-structured graphs with exponential node state space. Typical DP approaches have to enumerate the joint state space of two adjacent nodes on every edge of the tree to compute the optimal messages. Here we propose an algorithm based on Nested Benders Decomposition (NBD) that iteratively lower-bounds the message on every edge and promises to be far more efficient. We apply our NBD algorithm… Show more

We present a novel approach to solve dynamic programs (DP), which are frequent in computer vision, on tree-structured graphs with exponential node state space. Typical DP approaches have to enumerate the joint state space of two adjacent nodes on every edge of the tree to compute the optimal messages. Here we propose an algorithm based on Nested Benders Decomposition (NBD) that iteratively lower-bounds the message on every edge and promises to be far more efficient. We apply our NBD algorithm along with a novel Minimum Weight Set Packing (MWSP) formulation to a multi-person pose estimation problem. While our algorithm is provably optimal at termination it operates in linear time for practical DP problems, gaining up to 500× speed up over traditional DP algorithm which have polynomial complexity. Show less

We study the problem of multi-target tracking and data association in video. We formulate this in terms of selecting a subset of high-quality tracks subject to the constraint that no pair of selected tracks is associated with a common detection (of an object). This objective is equivalent to the classic NP-hard problem of finding a maximum-weight set packing (MWSP) where tracks correspond to sets and is made further difficult since the number of candidate tracks grows exponentially in the… Show more

We study the problem of multi-target tracking and data association in video. We formulate this in terms of selecting a subset of high-quality tracks subject to the constraint that no pair of selected tracks is associated with a common detection (of an object). This objective is equivalent to the classic NP-hard problem of finding a maximum-weight set packing (MWSP) where tracks correspond to sets and is made further difficult since the number of candidate tracks grows exponentially in the number of detections. We present a relaxation of this combinatorial problem that uses a column generation formulation where the pricing problem is solved via dynamic programming to efficiently explore the space of tracks. We employ row generation to tighten the bound in such a way as to preserve efficient inference in the pricing problem. We show the practical utility of this algorithm for pedestrian and particle tracking. Show less

We study the problem of hierarchical clustering on planar graphs. We formulate this in terms of finding the closest ultrametric to a specified set of distances and solve it using an LP relaxation that leverages minimum cost perfect matching as a subroutine to efficiently explore the space of planar partitions. We apply our algorithm to the problem of hierarchical image segmentation.

The random phase approximation (RPA) is an increasingly popular post-Kohn–Sham correlation method, but its high computational cost has limited molecular applications to systems with few atoms. Here we present an efficient implementation of RPA correlation energies based on a combination of resolution of the identity (RI) and imaginary frequency integration techniques. We show that the RI approximation to four-index electron repulsion integrals leads to a variational upper bound to the exact RPA… Show more

The random phase approximation (RPA) is an increasingly popular post-Kohn–Sham correlation method, but its high computational cost has limited molecular applications to systems with few atoms. Here we present an efficient implementation of RPA correlation energies based on a combination of resolution of the identity (RI) and imaginary frequency integration techniques. We show that the RI approximation to four-index electron repulsion integrals leads to a variational upper bound to the exact RPA correlation energy if the Coulomb metric is used. Auxiliary basis sets optimized for second-order Møller–Plesset (MP2) calculations are well suitable for RPA, as is demonstrated for the HEAT [A. Tajti et al., J. Chem. Phys. 121, 11599 (2004)] and MOLEKEL [F. Weigend et al., Chem. Phys. Lett. 294, 143 (1998)] benchmark sets. Using imaginary frequency integration rather than diagonalization to compute the matrix square root necessary for RPA, evaluation of the RPA correlation energy requires 𝑂(𝑁4log𝑁)
operations and 𝑂(𝑁3) storage only; the price for this dramatic improvement over existing algorithms is a numerical quadrature. We propose a numerical integration scheme that is exact in the two-orbital case and converges exponentially with the number of grid points. For most systems, 30–40 grid points yield 𝜇H accuracy in triple zeta basis sets, but much larger grids are necessary for small gap systems. The lowest-order approximation to the present method is a post-Kohn–Sham frequency-domain version of opposite-spin Laplace-transform RI-MP2 [J. Jung et al., Phys. Rev. B 70, 205107 (2004)]. Timings for polyacenes with up to 30 atoms show speed-ups of two orders of magnitude over previous implementations. The present approach makes it possible to routinely compute RPA correlation energies of systems well beyond 100 atoms, as is demonstrated for the octapeptide angiotensin II. Show less