Informs Annual Meeting 2017

WC71

INFORMS Houston – 2017

WC70

WC71

371E Biotechnology/Bioinformatics Contributed Session Chair: Da Lin, Coventry University, Cantol, United Kingdom, lind7708@gmail.com 1 - Exact Multiple Sequence Alignment by Synchronized Multivalued Decision Diagrams Amin Hosseininasab, Tepper School of Business, 5562 Hobart St, Apt 605, Pittsburgh, PA, 15217, United States, aminh@andrew.cmu.edu, Willem-Jan Van Hoeve We study an exact solution method for the Multiple Sequence Alignment (MSA) problem in computational biology. Our approach uses Multivalued Decision Diagrams (MDD) to model all possible pairwise sequence alignments (PSA). PSA MDDs are synchronized using side constraints to solve the MSA problem, for the first time, in polynomial space complexity. We use filtering techniques to reduce the size of our MDDs, both in PSA, and MSA. In MSA filtering, we develop for the first time, an upper bound to reduce the search space. Finally decomposition techniques are used to solve the synchronized MDDs. 2 - Integer Linear Programming Models for Protein Structure Prediction in Lattice Models Seyed Mojtaba Hosseini, University of California, Irvine, 67306, Verano Place, Irvine, CA, 92617, United States, smhosse1@uci.edu, Ceydu Oguz Protein structure prediction (PSP) consists of predicting the native structure of a protein from its sequence of amino acids by minimizing an energy function. The problem is of vital importance in medical science and molecular biology. In this study, we develop several integer linear programming (ILP) models for PSP problem abstracted to hydrophobic-polar model under cubic and square lattices, along with variety of valid inequalities and symmetry-breaking techniques. Next, we demonstrate that our ILP models are more efficient than the state-of-the-art models. We also establish that our models are effective in finding tight lower bounds via their linear programming relaxations. 3 - A Novel Combinatorial Approach for Cell Identification in Calcium Imaging Movies Quico Spaen, PhD Student, University of California-Berkeley, Etcheverry Hall, Berkeley, CA, 94720, United States, qspaen@berkeley.edu, Roberto J. Asín-Achá, Dorit Simona Hochbaum Calcium imaging has emerged as a workhorse method in neuroscience to investigate patterns of neuronal activity. We present HNCcorr, a novel algorithm for cell identification in calcium imaging movies based on combinatorial optimization. The algorithm identifies cells by finding distinct groups of highly similar pixels in correlation space, where a pixel is represented by the vector of correlations to other pixels. The HNCcorr algorithm achieves the best known results for the Neurofinder cell identification benchmark, and guarantees an optimal solution to the underlying optimization model. 4 - Feature Selection for Biomarker Identification in DNA Methylation Haluk Damgacioglu, PhD Candidate, University of Miami, 1251 Memorial Drive McArthur Engr Bldg Room 305, Coral Gables, FL, 33146, United States, haluk.damgacioglu@miami.edu, Emrah Celik, Nurcin Celik DNA methylation plays a critical role in regulating genome functions and abnormal methylation levels associate with various diseases such as cancer. Recent advances in genetic engineering provide high-dimensional DNA methylation data and it makes feature selection algorithms crucial to find the best subset of attributes for learning methods. Here, we introduce a curve-fitting based feature selection algorithm on the ordinal transformed methylation levels to handle the high-dimensionality. The performance of the proposed algorithm is demonstrated through six real DNA methylation datasets. 5 - Metafrontier Frameworks for the Study of Firm Level Efficiencies and Technology Ratios Da Lin, professor, Coventry University, Cantol, United Kingdom, lind7708@gmail.com, Swaki Kindos Since strategic alignment first rose to prominence with Henderson and Venkatraman’s (1993) seminal paper, research has tended to focus on the extent of fit between IT and business strategy at the firm level. Although useful, a firm- level view of alignment could mask what firms are doing to realize intellectual alignment between business and IT strategy and whether their actions will likely succeed. In this study, we build on an emergent stream of research that considers alignment between IT and business strategy at the process level.strategy and whether their actions will likely succeed. In this study, we build on an emergent stream of research that considers alignment between IT and

371F Optimization, Linear Programming Contributed Session Chair: Victoria Ellison, TiVo Research and Analytics, Carrboro, NC, United States, vmelliso@ncsu.edu 1 - Quantifying the Potential Therapeutic Benefit of Spatiotemporal Dose Modulation in Radiotherapy Ali Adibi, Wichita State University, 1845, Fairmount street, Wichita, KS, 67260-0004, United States, aliadibi.ie@gmail.com, Ehsan Salari It is clinically known that altering the radiation dose distribution over treatment sessions in fractionated radiotherapy may enhance the probability of tumor control without increasing the risk of normal-tissue complications. This research aims at quantifying the extent of this potential gain using a spatiotemporally integrated radiotherapy planning approach, which requires solving a class of large-scale non-convex QCQP problems. Global optimization techniques will be used to obtain near-optimal radiotherapy plans that vary over the treatment course. 2 - Taxi Planning: Branch and Price Approach Angel Marin, Universidad Politécnica de Madrid, ETS.Ingeniería Aeronáutica y del Espacio, Plaza Cardenal Cisneros 3, Madrid, 28040, Spain, angel.marin@upm.es, Luis Marin, Luis Ibáñez Taxi Planning has been formulated as a binary multicommodity flow network representing the aircraft ground movements from the runways to gates and vice versa. The flow capacities and other side constraints have been defined to represent the conflicts between aircrafts in the limited airport capacity. Branch and Price methodology has been adapted to take advantage of the Taxi Planning constraints. The computational tests have been run using data from Madrid- Barajas airport. The computational tests have been oriented to comparing the different methodologies. 3 - Benders Cuts for a Robust Disaster Preparedness Model to Facilitate Fair and Effective Response Gökalp Erbeyoglu, Boazici University, Dept. of Industrial Engineering, Bebek, stanbul, Turkey, gokalp.erbeyoglu@boun.edu.tr, Umit Bilge Decisions made in the preparedness stage of disaster management are critical since they set the frame for all further post-disaster operations. Having strategically located storage and distribution centers is the key that enables effective and fair response to a disaster. The preparedness model we propose selects locations and inventory levels of these facilities in a way to help achieving fairness in the response stage, and it ensures demand satisfaction under any disaster scenario. The Benders decomposition approach proposed to solve this hard problem uses continuous and logic-based cuts, and produces optimal or good solutions to cases with realistic sizes within a reasonable time-frame. 4 - Integrating Fleet Assignment with Passenger Mix Models Xiaodong Luo, Sabre Holdings Inc, 3150 Sabre Drive, Southlake, TX, 76092, United States, Xiaodong.Luo@sabre.com We consider the integration of fleet assignment with various passenger mix models. The passenger mix models address network effect, demand recapture characteristics, the randomness in demand as well as the revenue managementconsiderations. We implemented some simple warm start techniques,heuristic fixing techniques as well as decomposition techniques. Using data from one of our client, we compare performanceof some of these models, under various scenarios. Weuse Monte Carlo simulation to verify the revenue profit savings. 5 - Personnel Scheduling with Employees Transfer Between Departments Monia Rekik, Associate Professor, Universite Laval, 2325 rue de la Tterrasse, Quebec, QC, G1V. 0A6, Canada, monia.rekik@cirrelt.ca, Sana Dahmen, Francois Soumis, Guy Desaulniers We address a personalized multi-department multi-day shift scheduling problem where employees can be transferred between departments. A two-stage solution approach is proposed. Our computational results prove the high performance of the proposed approach on a large set of generated instances. 6 - A Hierarchical Consensus Clustering Extension of the Minimum Cluster Ratio Problem Applied to Gene Expression Profile Data Victoria Ellison, TiVo Research and Analytics, Carrboro, NC, 27510, United States, vmelliso@ncsu.edu We propose a divisive hierarchical consensus clustering algorithm that we show is a natural extension of the minimum cluster ratio problem. A linear parametric programming-based heuristic for this algorithm returns nested consensus clusterings from diverse clusterings derived from gene expression profile data. Numerical tests showed that most of the returned nested consensus clusterings sets contained the optimal solution to the Median Partition problem, thereby providing the ‘optimal’ answer to the consensus clustering problem as well as reflecting the nested nature of consensus clusters.

527