Source author record

Arvind U Raghunathan

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

ResearcherUnclaimed source record

math.OC Data Structures and Algorithms

Catalog footprint

What is connected

3works

2topics

4close collaborators

Actions

Connect this record

Open graph Browse works

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.

preprint2022arXiv

Recursive McCormick Linearization of Multilinear Programs

Linear programming (LP) relaxations are widely employed in exact solution methods for multilinear programs (MLP). One example is the family of Recursive McCormick Linearization (RML) strategies, where bilinear products are substituted for artificial variables, which deliver a relaxation of the original problem when introduced together with concave and convex envelopes. In this article, we introduce the first systematic approach for identifying RMLs, in which we focus on the identification of linear relaxation with a small number of artificial variables and with strong LP bounds. We present a novel mechanism for representing all the possible RMLs, which we use to design an exact mixed-integer programming (MIP) formulation for the identification of minimum-size RMLs; we show that this problem is NP-hard in general, whereas a special case is fixed-parameter tractable. Moreover, we explore structural properties of our formulation to derive an exact MIP model that identifies RMLs of a given size with the best possible relaxation bound is optimal. Our numerical results on a collection of benchmarks indicate that our algorithms outperform the RML strategy implemented in state-of-the-art global optimization solvers.

preprint2022arXiv

Seamless Multimodal Transportation Scheduling

Ride-hailing services have expanded the role of shared mobility in passenger transportation systems, creating new markets and creative planning solutions for major urban centers. In this paper, we consider their use for the first-mile or last-mile passenger transportation in coordination with a mass transit service to provide a seamless multimodal transportation experience for the user. A system that provides passengers with predictable information on travel and waiting times in their commutes is immensely valuable. We envision that the passengers will inform the system of their desired travel and arrival windows so that the system can jointly optimize the schedules of passengers. The problem we study balances minimizing travel time and the number of trips taken by the last-mile vehicles, so that long-term planning, maintenance, and environmental impact are all taken into account. We focus on the case where the last-mile service aggregates passengers by destination. We show that this problem is NP-hard, and propose a decision diagram-based branch-and-price decomposition model that can solve instances of real-world size (10,000 passengers spread over an hour, 50 last-mile destinations, 600 last-mile vehicles) in computational time (~1 minute) that is orders-of-magnitude faster than other methods appearing in the literature. Our experiments also indicate that aggregating passengers by destination on the last-mile service provides high-quality solutions to more general settings.

preprint2021arXiv

Homogeneous Formulation of Convex Quadratic Programs for Infeasibility Detection

Convex Quadratic Programs (QPs) have come to play a central role in the computation of control action for constrained dynamical systems. In this paper, we present a novel Homogeneous QP (HQP) formulation which is obtained by embedding the original QP in a larger space. The key properties of the HQP are: (i) is always feasible, (ii) an optimal solution to QP can be readily obtained from a solution to HQP, and (iii) infeasibility of QP corresponds to a particular solution of HQP. An immediate consequence is that all the existing algorithms for QP are now also capable of robustly detecting infeasibility. In particular, we present an Infeasible Interior Point Method (IIPM) for the HQP and show polynomial iteration complexity when applied to HQP. A key distinction with prior IPM approaches is that we do not need to solve second-order cone programs. Numerical experiments on the formulation are provided using existing codes.