2015 Informs Annual Meeting

SA26

INFORMS Philadelphia – 2015

SA27 27-Room 404, Marriott Multi-objective Combinatorial Problems Sponsor: Multiple Criteria Decision Making Sponsored Session

3 - Learning from the Offline Trace: A Case Study of the Taxi Industry Yingjie Zhang, Carnegie Mellon University, 5000 Forbes Avenue,

Pittsburgh, PA, 15213, United States of America, yingjie2@andrew.cmu.edu, Ramayya Krishnan, Siyuan Liu, Beibei Li

The growth of mobile and sensor technologies leads to the digitization of individual’s offline behavior. We instantiate our research by analyzing the digitized taxi tails to study the impact of different type and scale of information on driver behavior. We propose a Bayesian learning model and validate it on a unique data set containing complete information on 10.6M trip records from 11,196 taxis in a large Asian city in 2009. We find strong heterogeneity in individual learning behavior.

Chair: Banu Lokman, Assistant Professor, Middle East Technical University, Department of Industrial Engineering, Cankaya, Ankara, 06800, Turkey, lbanu@metu.edu.tr 1 - A Line Rebalancing Problem with Disruption Cost and Production Rate Criteria Ece Sanci, Research Assistant, Middle East Technical University (1100004144), ODTU Endustri Muhendisligi 325, Ankara, 06800, Turkey, esanci@metu.edu.tr, Meral Azizoglu In this study, we consider a line rebalancing problem with two objectives. We assume that there is an initial set of assignments and a disruption on one or more workstations that could alter the initial assignments. Our stability objective is to minimize the disruption cost which is defined as the weighted distance between the original and new workstations. Our efficiency objective is to maximize the production rate. We develop some exact and heuristic procedures and report on the results. 2 - Optimizing a Linear Function over the Nondominated Set of Multi-objective Optimization Problems Banu Lokman, Assistant Professor, Middle East Technical University, Department of Industrial Engineering, Cankaya, Ankara, 06800, Turkey, lbanu@metu.edu.tr We present an algorithm to optimize a linear function over the nondominated set of multi-objective optimization problems. The algorithm iteratively generates nondominated points and converges to the optimal solution. We also develop a variation of this algorithm to approximate the optimal point with a desired level of accuracy. We conduct experiments on multi-objective combinatorial optimization problems and show that the algorithm works well. 3 - Representative Nondominated Sets in Multi-objective Integer Programs Gokhan Ceyhan, Middle East Technical University, Department of Industrial Engineering, Ankara, 06800, Turkey, gceyhan@metu.edu.tr, Banu Lokman, Murat Koksalan We develop an algorithm to generate a representative nondominated set for multi-objective integer programs. We define a density based representation measure that evaluates the representativeness of a nondominated set considering the estimated regional densities of the nondominated frontier. We also develop a web application that is available to researchers to generate all or a representative subset of nondominated points. 4 - Iterative Method for Finding Pareto-dominant Shift Schedules for a Pediatric Emergency Department Young-chae Hong, University of Michigan, 1205 Beal Avenue, Ann Arbor, MI, 48109, United States of America, hongyc@umich.edu, Amy Cohn Building resident shift schedules for the U-M Pediatric Emergency Department is a multi-objective combinatorial problem. Chiefs cannot provide a single objective function or weights to trade off metrics of patient safety, educational training requirements, and resident satisfaction. We have developed an algorithm for generating Pareto-dominant schedules to reduce the solution space for Chief Residents to review and to help elicit their preferences.

SA26 26-Room 403, Marriott Biotechnology and Bioinformatics Contributed Session

Chair: Kan Wang, Georgia Institute of Technology, 813 Ferst Drive NW, Atlanta, GA, 30332, United States of America, kan.wang@gatech.edu 1 - Convex: De Novo Transcriptome Error Correction by Convexification Meisam Razaviyayn, Stanford University, Packard Building, De novo RNA sequencing with long reads requires accurate denoising as the first step. Unlike the initial combinatorial formulation, we propose an iterative convex reformulation which leads to a parallel algorithm for joint error correction and abundance estimation. The numerical experiments on the heart tissue PacBio samples show that, in addition to computational gain, the proposed algorithm results in 10% improvement in the number of denoised reads as compared to the existing software TOFU. 2 - Collection and Distribution of Cord Blood (CB) and Stem Cells (SC) by EU Blood Banks Katrina Nordstrom, Professor, Aalto University School of Chemical Technology, Department of Biotechnology, Kemistintie 1A, Espoo, 02150, Finland, katrina.nordstrom@aalto.fi, Ari Vepsäläinen Novel biomedical therapies call for expanding involvement of blood banks in collection, storage and distribution of cells. This study examines operations involving UB and SC in several EU countries. Wide variations are evident with major differences in amounts of cells collected and discarded. Most efficient operators are identified by minimized unnecessary collections. 3 - An Extended Formulation of the Convex Recoloring Problem on a Tree Sangho Shim, Northwestern University, 2001 Sheridan Road Suite 548, Kellogg School of Management, Evanston, IL, 60208, United States of America, shim@kellogg.northwestern.edu, Kangbok Lee, Minseok Ryu, Sunil Chopra We introduce a strong extended formulation of the convex recoloring problem on a tree, which has an application in analyzing a phylogenetic tree. The extended formulation has only polynomial number of constraints, but dominates the conventional formulation and the exponentially many valid inequalities which are previously known. The extended formulation solves the problem instances from TreeBASE.org at the root node of the branch-and-bound tree without branching. 4 - Dual-material 3d Printed Metamaterials with Tunable Mechanical Property for Patient-Specific Phantom Kan Wang, Georgia Institute of Technology, 813 Ferst Drive NW, Atlanta, GA, 30332, United States of America, kan.wang@gatech.edu, Mani Vannan, Changsheng Wu, Zhen Qian, Chuck Zhang, Ben Wang Patient-specific phantoms have a wide range of biomedical applications. Current 3D printed phantoms can only mimic Mechanical properties of soft tissues at small strain situations. This study investigated the feasibility of mimicking the strain-stiffening behavior of soft tissues using dual-material 3D printed metamaterials. Both FEA and tensile experiments indicated that those dual- material designs were able to exhibit strain-stiffening effects. Property tuning was also demonstrated. Palo Alto, CA, 94305, United States of America, meisamr@stanford.edu, David Tse, Elizabeth Tseng

SA28 28-Room 405, Marriott Combinatorial Auctions Cluster: Auctions Invited Session

Chair: Richard Steinberg, Chair In Operations Research, London School of Economics, Department of Management, NAB 3.08, Houghton Street, London, WC2A 2AE, United Kingdom, r.steinberg@lse.ac.uk 1 - The Performance of Deferred-acceptance Auctions Vasilis Gkatzelis, Stanford University, 474 Gates Building, 353 Serra Mall, Stanford, CA, 94305, United States of America, gkatz@cs.stanford.edu, Paul Duetting, Tim Roughgarden Milgrom and Segal recently introduced deferred-acceptance auctions and proved that they satisfy a remarkable list of incentive guarantees. We study these auctions through the lens of two canonical welfare-maximization problems. For knapsack auctions, we show a strong separation between deferred-acceptance mechanisms and arbitrary strategyproof mechanisms. For single-minded combinatorial auctions, we design novel deferred-acceptance mechanisms with near-optimal approximation guarantees.

46