scroll identifier for mobile
main-content

Über dieses Buch

This book features a selection of contributions that were presented at the Modeling and Optimization: Theory and Applications Conference (MOPTA) held at Lehigh University in B ethlehem, Pennsylvania, USA between August 16-18, 2017. The conference brought together a diverse group of researchers and practitioners working on both theoretical and practical aspects of continuous and discrete optimization. Topics covered include algorithms for solving convex, network, mixed-integer, nonlinear, and global optimization problems, and address the application of deterministic andstochastic optimization techniques in energy, finance, logistics, analytics, health, and other important fields. The selected contributions in this book illustrate the broad diversity of ideas discussed at the meeting.

Inhaltsverzeichnis

A Model of Residential Mail Delivery by Drones

Abstract
This paper proposes and analyzes a model of mail delivery in mid-size Canadian urban areas consisting of retrofitting current delivery trucks with a limited number of drones, which can be flown to a number of addresses in a given urban area. Such a truck would then travel between specific locations (called truck-stops), where drone deployment would be executed from. The designated truck-stops are outputs of a proposed algorithm that uses delivery demand data and drone characteristics; they change depending on the needed delivery coverage on a given day. We discuss whether this delivery method could be used in different types of urban areas, where the time to delivery to customers can be shortened, as compared to classic door-to-door delivery.
Monica G. Cojocaru, Edward W. Thommes, Sierra Gillies

On the Value of Dual-Firing Power Generation Under Uncertain Gas Network Access

Abstract
This work is concerned with the impact of gas network disruptions on dual-firing power generation. The question is addressed through the following optimization problem. Markets drive the price of gas, oil, and electricity. The log-prices evolve as correlated mean-reverting processes in discrete time. A generating unit has dual-firing capabilities, here in the sense that it can convert either gas or oil to electricity. Oil and gas are subject to different constraints and uncertainties. Gas is obtained in real time through the gas network. Due to gas supply disruptions, gas access is not guaranteed. Oil is stored locally and available in real time. The oil storage capacity is limited onsite. Oil can be reordered to replenish the oil tank, with a lead time between the order time and the delivery time. Oil is paid for at the order time price. In this paper, we formulate the stochastic optimization problem for a risk-neutral operator, and study the sensitivity of the value of the dual-firing generating unit to the gas network availability parameters.
Boris Defourny, Shu Tu

Efficient Piecewise Linearization for a Class of Non-convex Optimization Problems: Comparative Results and Extensions

Abstract
This research work originates from a challenging control problem in space engineering that gives rise to hard nonlinear optimization issues. Specifically, we need the piecewise linearization (PL) of a large number of non-convex univariate functions, within a mixed integer linear programming (MILP) framework. For comparative purposes, we recall a well-known classical PL formulation, an alternative approach based on disaggregated convex combination (DCC), and a more recent approach proposed by Vielma and Nemhauser. Our analysis indicates that—in the specific context of our study—the DCC-based approach has computational advantages: this finding is supported by experimental results. We discuss extensions and variations of the basic DCC paradigm. Extensions to a number of possible application areas in robotics and automation are also envisioned.
Giorgio Fasano, János D. Pintér

Smooth Minimization of Nonsmooth Functions with Parallel Coordinate Descent Methods

Abstract
We study the performance of a family of randomized parallel coordinate descent methods for minimizing a nonsmooth nonseparable convex function. The problem class includes as a special case L1-regularized L1 regression and the minimization of the exponential loss (“AdaBoost problem”). We assume that the input data defining the loss function is contained in a sparse $$m\times n$$ matrix A with at most $$\omega$$ nonzeros in each row and that the objective function has a “max structure”, allowing us to smooth it. Our main contribution consists in identifying parameters with a closed-form expression that guarantees a parallelization speedup that depends on basic quantities of the problem (like its size and the number of processors). The theory relies on a fine study of the Lipschitz constant of the smoothed objective restricted to low dimensional subspaces and shows an increased acceleration for sparser problems.
Olivier Fercoq, Peter Richtárik

Second-Order Cone Optimization Formulations for Service System Design Problems with Congestion

Abstract
We consider the service system design problem with congestion. This problem arises in a number of practical applications in the literature and is concerned with determining the location of service centers, the capacity level of each service center, and the assignment of customers to the facilities so that the customers demands are satisfied at total minimum cost. We present seven mixed-integer second-order cone optimization formulations for this problem, and compare their computational performances between them, and with the performance of other exact methods in the literature. Our results show that the conic formulations are competitive and may outperform the current leading exact methods. One advantage of the conic approach is the possibility of using off-the-shelf state-of-the-art solvers directly. More broadly, this study provides insights about different conic modeling approaches and the significant impact of the choice of approach on the efficiency of the resulting model.
Julio C. Góez, Miguel F. Anjos

The Iteration-Complexity Upper Bound for the Mizuno-Todd-Ye Predictor-Corrector Algorithm is Tight

Abstract
It is an open question whether there is an interior-point algorithm for linear optimization problems with a lower iteration-complexity than the classical bound $$\mathcal {O}(\sqrt{n} \log (\frac{\mu _1}{\mu _0}))$$. This paper provides a negative answer to that question for a variant of the Mizuno-Todd-Ye predictor-corrector algorithm. In fact, we prove that for any $$\varepsilon >0$$, there is a redundant Klee-Minty cube for which the aforementioned algorithm requires $$n^{( \frac{1}{2}-\varepsilon )}$$ iterations to reduce the barrier parameter by at least a constant. This is provably the first case of an adaptive step interior-point algorithm where the classical iteration-complexity upper bound is shown to be tight.
Murat Mut, Tamás Terlaky

Optimization of Inventory and Distribution for Hip and Knee Joint Replacements via Multistage Stochastic Programming

Abstract
We introduce a multistage stochastic programming model to optimize the distribution–production network of medical devices; in particular, artificial hip and knee joints for orthopedic surgery. These devices are distributed to hospitals in kits that contain multiple sizes of the joint; the surgeon uses one device from the kit and then returns the rest of the kit to the distributor, which replaces the part that has been removed and distributes the kit anew. Therefore, the distribution problem for artificial joints has a shareability property and thus is related to closed-loop supply chains. We assume that demands for the devices follow a discrete probability distribution and therefore we use scenarios to model the random demands over time. We compare the results of our optimization model to an approximation of the simple distribution strategy that our industry partner currently uses. The proposed approach outperforms the present approach in terms of optimal cost. We also explore the sensitivity of the model’s computation time as the numbers of scenarios, hospitals, and time periods change. Finally, we extend the model to investigate the production of shareable items in sharing systems using a numerical example.

TopSpin: TOPic Discovery via Sparse Principal Component INterference

Abstract
We propose a novel topic discovery algorithm for unlabeled images based on the bag-of-words (BoW) framework. We first extract a dictionary of visual words and subsequently for each image compute a visual word occurrence histogram. We view these histograms as rows of a large matrix from which we extract sparse principal components (PCs). Each PC identifies a sparse combination of visual words which co-occur frequently in some images but seldom appear in others. Each sparse PC corresponds to a topic, and images whose interference with the PC is high belong to that topic, revealing the common parts possessed by the images. We propose to solve the associated sparse PCA problems using an Alternating Maximization (AM) method, which we modify for the purpose of efficiently extracting multiple PCs in a deflation scheme. Our approach attacks the maximization problem in SPCA directly and is scalable to high-dimensional data. Experiments on automatic topic discovery and category prediction demonstrate encouraging performance of our approach. Our SPCA solver is publicly available.
Martin Takáč, Selin Damla Ahipaşaoğlu, Ngai-Man Cheung, Peter Richtárik

Exact Optimal Solution to Nonseparable Concave Quadratic Integer Programming Problems

Abstract
Nonseparable quadratic integer programming problems have extensive applications in real world and have received considerable attentions. In this paper, a new exact algorithm is presented for nonseparable concave quadratic integer programming problems. This algorithm is of a branch and bound frame, where the lower bound is obtained by solving a quadratic convex programming problem and the branches are partitioned via a special domain cut technique by which the optimality gap is reduced gradually. The optimal solution to the primal problem can be found in a finite number of iterations. Numerical results are also reported to illustrate the efficiency of our algorithm.
Fenlan Wang
Weitere Informationen