BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Julian Yarkony

Julian Yarkony appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computer VisionData Structures and AlgorithmsMachine LearningArtificial Intelligencemath.OCComputational Geometry

Catalog footprint

What is connected

14works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

14 published item(s)

preprint2022arXiv

Local Area Routes for Vehicle Routing Problems

We consider an approach for improving the efficiency of column generation (CG) methods for solving vehicle routing problems. We introduce Local Area (LA) route relaxations, an alternative/complement to the commonly used ng-route relaxations and Decremental State Space Relaxations (DSSR) inside of CG formulations. LA routes are a subset of ng-routes and a super-set of elementary routes. Normally, the pricing stage of CG must produce elementary routes, which are routes without repeated customers, using processes which can be computationally expensive. Non-elementary routes visit at least one customer more than once, creating a cycle. LA routes relax the constraint of being an elementary route in such a manner as to permit efficient pricing. LA routes are best understood in terms of ng-route relaxations. Ng-routes are routes which are permitted to have non-localized cycles in space; this means that at least one intermediate customer (called a breaker) in the cycle must consider the starting customer in the cycle to be spatially far away. LA routes are described using a set of special indexes corresponding to customers on the route ordered from the start to the end of the route. LA route relaxations further restrict the set of permitted cycles beyond that of ng-routes by additionally enforcing that the breaker must be a located at a special index where the set of special indexes is defined recursively as follows. The first special index in the route is at index 1 meaning that it is associated with the first customer in the route. The k'th special index corresponds to the first customer after the k-1'th special index, that is not considered to be a neighbor of (considered spatially far from) the customer located at the k-1'th special index. We demonstrate that LA route relaxations can significantly improve the computational speed of pricing when compared to the standard DSSR.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Principled Graph Management

Graph Generation is a recently introduced enhanced Column Generation algorithm for solving expanded Linear Programming relaxations of mixed integer linear programs without weakening the expanded relaxations which characterize these methods. To apply Graph Generation we must be able to map any given column generated during pricing to a small directed acyclic graph for which any path from source to sink describes a feasible column. This structure is easily satisfied for vehicle routing, crew scheduling and various logistics problems where pricing is a constrained shortest path problem. The construction of such graphs trades off the size/diversity of a subset of columns modeled by the graphs versus the additional computational time required to solve the problems induced by larger graphs. Graph Generation (GG) has two computational bottlenecks. The first is pricing. Pricing in GG and Column Generation (CG) is identical because of the structure of the problems solved. The second bottleneck is the restricted master problem (RMP), which is more computationally intensive in GG than in CG given the same number of columns generated. By design GG converges in fewer iterations than CG, and hence requires fewer calls to pricing. Therefore, when the computation time of GG is dominated by pricing, as opposed to solving the RMP, GG converges much faster than CG in terms of time. However GG need not converge faster than CG when the GG RMP, rather than pricing, dominates computation. In this paper we introduce Principled Graph Management (PGM), which is an algorithm to solve the GG RMP rapidly by exploiting its special structure. We demonstrate the effectiveness of PGM inside a GG solution to the classical Capacitated Vehicle Routing Problem. We demonstrate that PGM solves the GG RMP hundreds of times faster than the baseline solver and that the improvement in speed increases with problem size.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Accelerating Column Generation via Flexible Dual Optimal Inequalities with Application to Entity Resolution

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. The project page is available at the following url, https://github.com/lokhande-vishnu/EntityResolution

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Integer Programming for Multi-Robot Planning: A Column Generation Approach

We consider the problem of coordinating a fleet of robots in a warehouse so as to maximize the reward achieved within a time limit while respecting problem and robot specific constraints. We formulate the problem as a weighted set packing problem where elements are defined as being the space-time positions a robot can occupy and the items that can be picked up and delivered. We enforce that robots do not collide, that each item is delivered at most once, and that the number of robots active at any time does not exceed the total number available. Since the set of robot routes is not enumerable, we attack optimization using column generation where pricing is a resource-constrained shortest-path problem.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Relaxed Dual Optimal Inequalities for Relaxed Columns: with Application to Vehicle Routing

We address the problem of accelerating column generation for set cover problems in which we relax the state space of the columns to do efficient pricing. We achieve this by adapting the recently introduced smooth and flexible dual optimal inequalities (DOI) for use with relaxed columns. Smooth DOI exploit the observation that similar items are nearly fungible, and hence should be associated with similarly valued dual variables. Flexible DOI exploit the observation that the change in cost of a column induced by removing an item can be bounded. We adapt these DOI to the problem of capacitated vehicle routing in the context of ng-route relaxations. We demonstrate significant speed ups on a benchmark data set, while provably not weakening the relaxation.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Smooth and flexible dual optimal inequalities

We address the problem of accelerating column generation (CG) for set-covering formulations via dual optimal inequalities (DOI). DOI use knowledge of the dual solution space to derive inequalities that might be violated by intermediate solutions to a restricted master problem, and as such are efficient at reducing the number of iterations and the oscillations of the dual variables commonly observed in column generation procedures. We study two novel classes of DOI which are referred to as Flexible DOI (F-DOI) and Smooth-DOI (S-DOI), respectively (and jointly as SF-DOI). F-DOI provide rebates for covering items more than necessary. S-DOI describe the payment of a penalty to permit the under-coverage of items in exchange for the over-inclusion of other items. Unlike other classes of DOI from the literature, the S-DOI and F-DOI rely on very little to no problem-specific knowledge, and as such have the potential to be applied to a vast number of problem domains. In particular, we illustrate the efficiency of the new inequalities by embedding them within a column generation solver for the single source capacitated facility location problem (SSCFLP). A speed-up of a factor of up to 130x can be observed as when compared to a non-stabilized variant of the same CG procedure to achieve the linear relaxation lower bound on problems with dense columns and structured assignments costs.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Convex Optimization For Non-Convex Problems via Column Generation

We apply column generation to approximating complex structured objects via a set of primitive structured objects under either the cross entropy or L2 loss. We use L1 regularization to encourage the use of few structured primitive objects. We attack approximation using convex optimization over an infinite number of variables each corresponding to a primitive structured object that are generated on demand by easy inference in the Lagrangian dual. We apply our approach to producing low rank approximations to large 3-way tensors.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Efficient Pose and Cell Segmentation using Column Generation

We study the problems of multi-person pose segmentation in natural images and instance segmentation in biological images with crowded cells. We formulate these distinct tasks as integer programs where variables correspond to poses/cells. To optimize, we propose a generic relaxation scheme for solving these combinatorial problems using a column generation formulation where the program for generating a column is solved via exact optimization of very small scale integer programs. This results in efficient exploration of the spaces of poses and cells.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Tracking Objects with Higher Order Interactions using Delayed Column Generation

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 tracking problems in natural and biological video datasets.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Planar Ultrametric Rounding for Image Segmentation

We study the problem of hierarchical clustering on planar graphs. We formulate this in terms of an LP relaxation of ultrametric rounding. To solve this LP efficiently we introduce a dual cutting plane scheme that uses minimum cost perfect matching as a subroutine in order to efficiently explore the space of planar partitions. We apply our algorithm to the problem of hierarchical image segmentation.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Fast Planar Correlation Clustering for Image Segmentation

We describe a new optimization scheme for finding high-quality correlation clusterings in planar graphs that uses weighted perfect matching as a subroutine. Our method provides lower-bounds on the energy of the optimal correlation clustering that are typically fast to compute and tight in practice. We demonstrate our algorithm on the problem of image segmentation where this approach outperforms existing global optimization techniques in minimizing the objective and is competitive with the state of the art in producing high-quality segmentations.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Tightening MRF Relaxations with Planar Subproblems

We describe a new technique for computing lower-bounds on the minimum energy configuration of a planar Markov Random Field (MRF). Our method successively adds large numbers of constraints and enforces consistency over binary projections of the original problem state space. These constraints are represented in terms of subproblems in a dual-decomposition framework that is optimized using subgradient techniques. The complete set of constraints we consider enforces cycle consistency over the original graph. In practice we find that the method converges quickly on most problems with the addition of a few subproblems and outperforms existing methods for some interesting classes of hard potentials.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Planar Cycle Covering Graphs

We describe a new variational lower-bound on the minimum energy configuration of a planar binary Markov Random Field (MRF). Our method is based on adding auxiliary nodes to every face of a planar embedding of the graph in order to capture the effect of unary potentials. A ground state of the resulting approximation can be computed efficiently by reduction to minimum-weight perfect matching. We show that optimization of variational parameters achieves the same lower-bound as dual-decomposition into the set of all cycles of the original graph. We demonstrate that our variational optimization converges quickly and provides high-quality solutions to hard combinatorial problems 10-100x faster than competing algorithms that optimize the same bound.

0 citations0 reviewsNo code linkedOpen access