Search

In many statistical learning problems, it is desired that the optimal solution conform to an a priori known sparsity structure represented by a directed acyclic graph. Inducing such structures by means of convex regularizers requires nonsmooth penalty functions that exploit group overlapping. Our study focuses on evaluating the proximal operator of the latent overlapping group lasso developed by Jacob et al. in 2009. We implemented an alternating direction method of multiplier with a sharing scheme to solve large-scale instances of the underlying optimization problem efficiently. In the absence of strong convexity, global linear convergence of the algorithm is established using the error bound theory. More specifically, the paper contributes to establishing primal and dual error bounds when the nonsmooth component in the objective function does not have a polyhedral epigraph. We also investigate the effect of the graph structure on the speed of convergence of the algorithm. Detailed numerical simulation studies over different graph structures supporting the proposed algorithm and two applications in learning are provided. Summary of Contribution: The paper proposes a computationally efficient optimization algorithm to evaluate the proximal operator of a nonsmooth hierarchical sparsity-inducing regularizer and establishes its convergence properties. The computationally intensive subproblem of the proposed algorithm can be fully parallelized, which allows solving large-scale instances of the underlying problem. Comprehensive numerical simulation studies benchmarking the proposed algorithm against five other methods on the speed of convergence to optimality are provided. Furthermore, performance of the algorithm is demonstrated on two statistical learning applications related to topic modeling and breast cancer classification. The code along with the simulation studies and benchmarks are available on the corresponding author's GitHub website for evaluation and future use. [ABSTRACT FROM AUTHOR]

This paper investigates a decomposition approach for binary optimization problems with nonlinear objectives and linear constraints. Our methodology relies on the partition of the objective function into separate low-dimensional dynamic programming (DP) models, each of which can be equivalently represented as a shortest-path problem in an underlying state-transition graph. We show that the associated transition graphs can be related by a mixed-integer linear program (MILP) so as to produce exact solutions to the original nonlinear problem. To address DPs with large state spaces, we present a general relaxation mechanism that dynamically aggregates states during the construction of the transition graphs. The resulting MILP provides both lower and upper bounds to the nonlinear function, and it may be embedded in branch-and-bound procedures to find provably optimal solutions. We describe how to specialize our technique for structured objectives (e.g., submodular functions) and consider three problems arising in revenue management, portfolio optimization, and healthcare. Numerical studies indicate that the proposed technique often outperforms state-of-the-art approaches by orders of magnitude in these applications. Data and the online appendix are available at https://doi.org/10.1287/mnsc.2017.2849. This paper was accepted by Yinyu Ye, optimization. [ABSTRACT FROM AUTHOR]

With the emergence of ride-sharing companies that offer transportation on demand at a large scale and the increasing availability of corresponding demand data sets, new challenges arise to develop routing optimization algorithms that can solve massive problems in real time. In "Online Vehicle Routing: The Edge of Optimization in Large-Scale Applications," D. Bertsimas, P. Jaillet, and S. Martin present a novel and generalizable backbone algorithm that uses integer optimization to find high-quality solutions to large routing optimization problems. The algorithm, together with the real-time routing optimization software framework developed and shared by the authors, can dispatch thousands of taxis serving more than 25,000 customers per hour. An extensive study with historical simulations of Yellow Cabs in New York City is used to both show that the algorithm improves on the performance of existing heuristics and to provide insights on the optimization opportunities of a large ride-sharing fleet. With the emergence of ride-sharing companies that offer transportation on demand at a large scale and the increasing availability of corresponding demand data sets, new challenges arise to develop routing optimization algorithms that can solve massive problems in real time. In this paper, we develop an optimization framework, coupled with a novel and generalizable backbone algorithm, that allows us to dispatch in real time thousands of taxis serving more than 25,000 customers per hour. We provide evidence from historical simulations using New York City routing network and yellow cab data to show that our algorithms improve upon the performance of existing heuristics in such real-world settings. The online supplement is available at https://doi.org/10.1287/opre.2018.1763. [ABSTRACT FROM AUTHOR]

We study a class of problems with both binary selection decisions and associated continuous choices that result in stochastic rewards and costs. The rewards are received based on the decision maker's selection, and the costs depend both on the decisions and realizations of the stochastic variables. We consider a family of risk-based objective functions that contains the traditional risk-neutral expected-value objective as a special case. A combination of rounding and sample average approximation is used to produce solutions that are guaranteed to be close to the optimal solution with high probability. We also provide an empirical comparison of the performance of the algorithms on a set of randomly generated instances of a supply chain example problem. The computational results illustrate the theoretical claims in the paper that, for this problem, high-quality solutions can be found with small computational effort. [ABSTRACT FROM AUTHOR]

Algorithms for approximating the nondominated set of multiobjective optimization problems are reviewed. The approaches are categorized into general methods that are applicable under mild assumptions and, thus, to a wide range of problems, and into algorithms that are specifically tailored to structured problems. All in all, this survey covers 52 articles published within the last 41 years, that is, between 1979 and 2020. Summary of Contribution: In many problems in operations research, several conflicting objective functions have to be optimized simultaneously, and one is interested in finding Pareto optimal solutions. Because of the high complexity of finding Pareto optimal solutions and their usually very large number, however, the exact solution of such multiobjective problems is often very difficult, which motivates the study of approximation algorithms for multiobjective optimization problems. This research area uses techniques and methods from algorithmics and computing in order to efficiently determine approximate solutions to many well-known multiobjective problems from operations research. Even though approximation algorithms for multiobjective optimization problems have been investigated for more than 40 years and more than 50 research articles have been published on this topic, this paper provides the first survey of this important area at the intersection of computing and operations research. [ABSTRACT FROM AUTHOR]

The ℓ0-minimization problem that seeks the sparsest point of a polyhedral set is a long-standing, challenging problem in the fields of signal and image processing, numerical linear algebra, and mathematical optimization. The weighted ℓ1-method is one of the most plausible methods for solving this problem. In this paper we develop a new weighted ℓ1-method through the strict complementarity theory of linear programs. More specifically, we show that locating the sparsest point of a polyhedral set can be achieved by seeking the densest possible slack variable of the dual problem of weighted ℓ1-minimization. As a result, ℓ0-minimization can be transformed, in theory, to ℓ0-maximization in dual space through some weight. This theoretical result provides a basis and an incentive to develop a new weighted ℓ1-algorithm, which is remarkably distinct from existing sparsity-seeking methods. The weight used in our algorithm is computed via a certain convex optimization instead of being determined locally at an iterate. The guaranteed performance of this algorithm is shown under some conditions, and the numerical performance of the algorithm has been demonstrated by empirical simulations. [ABSTRACT FROM AUTHOR]

In this paper, we consider the so-called worst-case linear optimization (WCLO) with uncertainties on the right-hand side of the constraints. Such a problem often arises in applications such as in systemic risk estimation in finance and stochastic optimization. We first show that the WCLO problem with the uncertainty set corresponding to the l p-norm ((WCLOp)) is NP-hard for p ɛ (1,∞). Second, we combine several simple optimization techniques, such as the successive convex optimization method, quadratic convex relaxation, initialization, and branch-and-bound (B&B), to develop an algorithm for (WCLO2) that can find a globally optimal solution to (WCLO2) within a prespecified ε-tolerance. We establish the global convergence of the algorithm and estimate its complexity. We also develop a finite B&B algorithm for (WCLO∞) to identify a global optimal solution to the underlying problem, and establish the finite convergence of the algorithm. Numerical experiments are reported to illustrate the effectiveness of our proposed algorithms in finding globally optimal solutions to medium and large-scale WCLO instances. [ABSTRACT FROM AUTHOR]

One of the most attractive recent approaches to processing well-structured large-scale convex optimization problems is based on smooth convex-concave saddle point reformulation of the problem of interest and solving the resulting problem by a fast first order saddle point method utilizing smoothness of the saddle point cost function. In this paper, we demonstrate that when the saddle point cost function is polynomial, the precise gradients of the cost function required by deterministic first order saddle point algorithms and becoming prohibitively computationally expensive in the extremely large-scale case, can be replaced with incomparably cheaper computationally unbiased random estimates of the gradients. We show that for large-scale problems with favorable geometry, this randomization accelerates, progressively as the sizes of the problem grow, the solution process. This extends significantly previous results on acceleration by randomization, which, to the best of our knowledge, dealt solely with bilinear saddle point problems. We illustrate our theoretical findings by instructive and encouraging numerical experiments. [ABSTRACT FROM AUTHOR]

In the stochastic orienteering problem, we are given a finite metric space, where each node contains a job with some deterministic reward and a random processing time. The processing time distributions are known and independent across nodes. However the actual processing time of a job is not known until it is completely processed. The objective is to compute a nonanticipatory policy to visit nodes (and run the corresponding jobs) so as to maximize the total expected reward, subject to the total distance traveled plus the total processing time being at most a given budget of B. This problem combines aspects of the stochastic knapsack problem with uncertain item sizes as well as the deterministic orienteering problem. In this paper, we consider both nonadaptive and adaptive policies for Stochastic Orienteering. We present a constant-factor approximation algorithm for the nonadaptive version and an O(log logB)-approximation algorithm for the adaptive version. We extend both these results to directed metrics and a more general sequence orienteering problem. Finally, we address the stochastic orienteering problem when the node rewards are also random and possibly correlated with the processing time and obtain an O(log n logB)-approximation algorithm; here n is the number of nodes in the metric. All our results for adaptive policies also bound the corresponding "adaptivity gaps". [ABSTRACT FROM AUTHOR]

Unmanned aircraft systems (UASs) are a promising new mode of transportation for cargo delivery. Although control, navigation, and communication technologies are becoming available on individual flight units, system-level motion management for dense UAS traffic remains an open question. This paper presents a motion-planning model based on nonlinear optimization techniques to centrally coordinate paths for all vehicles traversing a shared two-dimensional (2D) space. An exact bound is derived to characterize the discrete-time separation constraints, and a set of new metrics is proposed to measure 2D traffic flow efficiency. The grand goal is to make all vehicles that come under dispatch reach their respective destinations quickly and efficiently while maintaining a safe intervehicle separation at all times. This infinite-horizon operational problem is formulated as a nonlinear nonconvex optimization model that must be solved in a progressive, receding-horizon fashion. To ensure feasibility and overcome path deadlocks attributed to local optima, a series of heuristic measures are developed. By pivoting on artfully coined intermediate feasibility, the algorithm is able to circumvent imminent deadlocks in a predictive manner and progressively construct the solution with guaranteed feasibility. Simulation experiments are performed at various traffic density levels to generate useful insights for airspace regulators and traffic managers. [ABSTRACT FROM AUTHOR]

We study the design of mechanisms for a sequencing problem where the types of job-agents consist of processing times and waiting costs that are private to the jobs. In the Bayes-Nash setting, we seek to find a sequencing rule and incentive compatible payments that minimize the total expected payments that have to be made to the agents. It is known that the problem can be efficiently solved when jobs have single-dimensional types. Here, we address the problem with two-dimensional types. We show that the problem can be solved in polynomial time by linear programming techniques, answering an open problem formulated by Heydenreich et al. Our implementation is randomized and truthful in expectation. Remarkably, it also works when types are correlated across jobs. The main steps are a compactification of an exponential size linear programming formulation, and a convex decomposition algorithm that allows us to implement the optimal linear programming solution. In addition, by means of computational experiments, we generate some new insights into the implementability in different equilibria. [ABSTRACT FROM AUTHOR]

We consider the problem of scheduling crash tests for new vehicle programs at Ford. We describe the development of a comprehensive web-based system that automates time-consuming scheduling analyses through mathematical optimization, while also institutionalizing expert knowledge about the engineering complexities of crash testing. We present a novel integer programming model and a corresponding solution algorithm that quickly generates efficient schedules. The system's user interface enables engineers to specify key program data and consider multiple scheduling scenarios, while using the underlying optimization model and solution algorithms as a black box. [ABSTRACT FROM AUTHOR]

LU and Cholesky factorizations are computational tools for efficiently solving linear systems that play a central role in solving linear programs and several other classes of mathematical programs. In many documented cases, however, the roundoff errors accrued during the construction and implementation of these factorizations lead to the misclassification of feasible problems as infeasible and vice versa. Hence, reducing these roundoff errors or eliminating them altogether is imperative to guarantee the correctness of the solutions provided by optimization solvers. To achieve this goal without having to use rational arithmetic, we introduce two roundofferror-free factorizations that require storing the same number of individual elements and performing a similar number of operations as the traditional LU and Cholesky factorizations. Additionally, we present supplementary roundoff-error-free forward and backward substitution algorithms, thereby providing a complete tool set for solving systems of linear equations exactly and efficiently. An important property shared by the featured factorizations and substitution algorithms is that their individual coefficients' maximum word length--i.e., the maximum number of digits required for expression--is bounded polynomially. Unlike the rational arithmetic methods used in practice to solve linear systems exactly, however, the algorithms herein presented do not require any gcd calculations to bound the entries' word length. We also derive various other related theoretical results, including the total computational complexity of all the roundoff-error-free processes herein presented. [ABSTRACT FROM AUTHOR]

The dial-a-ride problem (DARP) involves the dispatching of a fleet of vehicles to transport customers requesting service and is one of the most challenging tasks of combinatorial optimization. We study the DARP as a constraint satisfaction problem, where the goal is to find a feasible solution with respect to the time, capacity, and precedence constraints, or to prove infeasibility. The main contribution of our work is a new robust method for this problem formulation. The algorithm is based on a dynamic subroutine that finds for any set of customers a maximum cluster, that is, a maximal set of customers that can be served by a single vehicle. The performance of the algorithm is analyzed and evaluated by means of computational experiments, justifying the efficiency of the solution method. [ABSTRACT FROM AUTHOR]

Fourier-Motzkin elimination is a projection algorithm for solving finite linear programs. We extend Fourier-Motzkin elimination to semi-infinite linear programs, which are linear programs with finitely many variables and infinitely many constraints. Applying projection leads to new characterizations of important properties for primal-dual pairs of semi-infinite programs such as zero duality gap, feasibility, boundedness, and solvability. Extending the Fourier-Motzkin elimination procedure to semi-infinite linear programs yields a new classification of variables that is used to determine the existence of duality gaps. In particular, the existence of what the authors term dirty variables can lead to duality gaps. Our approach has interesting applications in finite-dimensional convex optimization. For example, sufficient conditions for a zero duality gap, such as the Slater constraint qualification, are reduced to guaranteeing that there are no dirty variables. This leads to completely new proofs of such sufficient conditions for zero duality. [ABSTRACT FROM AUTHOR]