Informs Annual Meeting 2017

WA72

INFORMS Houston – 2017

WA70

3 - Cyclic Best First Search: using Contours to Guide Branch-and-bound Algorithms

371E Data Mining Contributed Session Chair: Tejas Huddar, Texas A&M University-Kingsville, San Antonio, TX, United States, tejashuddar@gmail.com 1 - A Novel MILP Based Approach to Multi-class Data Classification Problem Fatih Rahim, Koç University, Koç Üniversitesi, Rumelifeneri Yolu, Sariyer, Istanbul, 34450, Turkey, frahim@ku.edu.tr, Metin Turkay Multi-class data classification is a supervised machine learning problem that involves assigning data to multiple groups. We present a novel MILP-based approach that splits each class’s data set into subsets such that the subsets of different classes are separable by a hyperplane. The hyperplanes form a polyhedral region for each subset and the regions of different classes are disjoint. A MILP model is used to find the optimal separation by minimizing the total number of regions and misclassified samples. A preprocessing step is proposed to simplify the problem considering pairwise separation of classes. We evaluated the convex hulls of subsets and the polyhedral regions for the testing phase. 2 - What Factors Influence Consumer’s Online Purchase Decision? the Driving Effect of Customer Perceived Value Peng Zhu, Nanjing University of Science and Technology, 200 Xiaolingwei Street, Nanjing, 210094, China, p.zhu@outlook.com, Yuefen Wang, Mingsheng Zhao What factors influence consumers’ online purchase decisions? This paper points out that in the online shopping mode, customer perceived value includes three dimensions: Product perceived value, Service perceived value and Social perceived value. Based on this three dimensions, the paper constructs online purchase decision impact model and collects Taobao’s massive consumer purchase behavior data. Through large sample analysis, the research found that the length of online reviews, the volume of goods sold, the sellers’ credit rating, the sellers’ DSR service score and the time length of the online shop have positive impact on the consumer’s online purchase decision. 3 - Decision Making Process for Selecting Efficient and Cost Effective Motors for Humanoid Robot Arm Selecting an option from numerous available choices in market has always been a vague task, especially, in a component selection of robot systems. The objective of this research is to develop a decision-making process for the best set selection of motors from various options considering three criteria: weight, cost and lifting capacity. The suggested decision-making process uses profile model, checklist model, AHP and lastly presents LP and NLP models using the correlations of the criteria. The results show that the suggested method is effective yet efficient not only in this problem but also in cases that need to select the best candidate from large available options. Tejas Huddar, Mechanical Engineer, Texas A&M.University- Kingsville, 4510 Eisenhauer Rd, San Antonio, TX, 78218, United States, tejashuddar@gmail.com, Joon-Yeoul Oh

Wenda Zhang, University of Illinois at Urbana-Champaign, 1618 Melrose Park Court, Apt 1722, Urbana, IL, 61801, United States, wzhang95@illinois.edu, David R.Morrison, Jason Sauppe, Sheldon H. Jacobson, Edward C. Sewell The cyclic best-first search (CBFS) strategy is a modification of BFS that groups search tree subproblems into contours, and repeatedly cycles through all non- empty contours to select subproblems to explore. In this paper, the theoretical properties of CBFS are analyzed. CBFS is proved to be a generalization of all other search strategies. Further, a bound is proved between the number of subproblems explored by BFS and the number of children generated by CBFS, given a fixed branching strategy and set of pruning rules. Finally, a discussion of heuristic contour-labeling functions is provided, and proof-of-concept computational results for mixed-integer programming problems are shown. 4 - Decentralized Online Integer Programming Ezgi Karabulut, Georgia Institute of Technology, Atlanta, GA, United States, ezgi.karabulut@gatech.edu, Shabbir Ahmed, George L. Nemhauser We consider a set of agents that need to coordinate their actions to optimize the sum of their objectives while satisfying a common resource constraint. The objective functions of the players are unknown to them a priori and are revealed in an online manner. The resulting problem is an online optimization problem to optimally allocate the resource among the players prior to observing the item values. We show that for any deterministic online algorithm for this problem, there exists a lower bound of Ω (T) on regret. Furthermore, when the players’ integer programs satisfy a special concavity condition, we propose a randomized online algorithm that guarantees an upper bound of O( √ T) on the expected regret. 372A Optimization, Network Contributed Session Chair: Onur Tavaslioglu, University of Pittsburgh, Houston, TX, United States, ont1@pitt.edu 1 - Advancements of the Double Pivot Simplex Method Fabio T.Vitor, Kansas State University, 2061 Rathbone Hall, 1701B Platt St., Manhattan, KS, 66506, United States, fabioftv@k-state.edu, Todd W. Easton Recently, Vitor and Easton introduced the Double Pivot Simplex Method (DPSM). Each iteration of the Simplex Method (SM) pivots on exactly one variable. In contrast, DPSM can pivot on two variables at a time. The talk will briefly present DPSM and focus on the computational comparison of DPSM and SM. Both methods are implemented using several CPLEX routines. Computational experiments demonstrate that DPSM requires approximately 40% fewer pivots than SM when tested on some benchmark instances. Additional comments will be provided on DPSM’s impact to degenerate linear programs. 2 - Diet Problem with Ingredient Preferences Fariborz Y. Partovi, Professor, Drexel University, 3141 Chestnut St, Philadelphia, PA, 19104, United States, partovi@drexel.edu It has been close to seventy years since the Diet problem was introduced by Stigler (Stigler 1945). However the problem with the classical Diet models is based on lack of proper presentation of food preferences. For many people, especially when they are eating outside their home, the content of the food as far as nutrition is concern, maybe not, as important as the taste of the food or other consumptions. In this article we modify Diet problem using extensions of Data Envelopment analysis to satisfy customer’s preferences. 3 - Finding Enclosures of the Optimal Set of Interval Linear Programming Problems: An Empirical Analysis Mohsen Mohammadi Dehcheshmeh, University of Louisville, Louisville, KY, United States, m0moha15@louisville.edu, Monica Gentili Determining the set of optimal solutions for an interval linear programming problem is challenging due to the possibility of non-convex and/or disconnected optimal sets. Several approximation methods have been developed to compute enclosures of the optimal set, that is a super set that includes it. In this study, we present an experimental analysis to compare the quality of the enclosures obtained by different existing methods in the literature. WA72

WA71

371F Optimization, Large Scale Contributed Session Chair: Ezgi Karabulut, Georgia Institute of Technology, Atlanta, GA,

United States, ezgi.karabulut@gatech.edu 1 - Team Formation in Social Networks Nihal Berktas, Bilkent University, Ankara, Turkey, nihal.berktas@bilkent.edu.tr, Hande Yaman

People work in teams to complete a job or project that requires a number of skills and that needs to be finished by a deadline that cannot be met by one individual. The success of a team depends on the technical capabilities of people as well as the quality of the communication among them. We study the team formation problem in which communication is taken into consideration by assuming the potential members constitute a social network. We develop integer programs for different versions of the problem and present computational results using different data sets. 2 - An Overview of Recent Advances in Pyomo William E. Hart, Sandia National Laboratories, 8625 Napa Valley Road NE, Albuquerque, NM, 87122, United States, wehart@sandia.gov, John Siirola Pyomo is a Python-based, open-source optimization modeling language with a diverse set of optimization capabilities. This presentation will review significant advances in recent Pyomo releases, including advanced modeling of subproblems with blocks, automatic differentiation, modeling with units, and a new kernel software layer for advanced scripting applications.

467