Asee peer logo

Board 101 : A Steepest Edge Rule for a Column Generation Approach to the Convex Recoloring Problem

Download Paper |


2018 ASEE Annual Conference & Exposition


Salt Lake City, Utah

Publication Date

June 23, 2018

Start Date

June 23, 2018

End Date

July 27, 2018

Conference Session

Industrial Engineering Division Poster Session

Tagged Division

Industrial Engineering

Page Count




Permanent URL

Download Count


Request a correction

Paper Authors


Ergin Erdem Robert Morris University

visit author page

Ergin Erdem is an assistant professor of Department of Engineering at Robert Morris University. Dr. Erdem holds BS and MS degrees in industrial engineering from Middle East Technical University, Turkey and a PhD in Industrial and Manufacturing Engineering from North Dakota State University He has previously worked as a lecturer and research associate at Atilim University and North Dakota State University. His research interests include; modeling for facility planning, genetic algorithms, education of manufacturing technologies, RFID applications in food and pharmaceutical applications, operations management in healthcare industry.

visit author page


Sangho Shim Robert Morris University

visit author page

Dr. Sangho Shim is an Assistant Professor in the Department of Engineering at Robert Morris University (RMU) in Pennsylvania.

Before Dr. Shim joined RMU in Fall 2015, he had performed research projects on combinatorial optimization as a research staff member of Kellogg School of Management at Northwestern University under supervisory of Sunil Chopra. He also performed the General Motors Renewable Energy Portfolio project with Industrial Engineering and Management Sciences Department of Northwestern University since 2011. At Northwestern University and Georgia Institute of Technology, he also conducted the KT (Korea Telecom Corp) Smart Grid Project and the KT-LG Illinois Smart Building Project as Manager of KT in 2010-2011.

Dr. Shim was an Instructor at Georgia Institute of Technology in 2009-2010 since his PhD degree in Industrial and Systems Engineering (Major: Optimization, Advisor: Ellis L. Johnson) from the institute.

Before he came to the US, he got BS in Mathematics at Seoul National University and MS in Computational Mathematics at POSTECH in Korea.

visit author page

Download Paper |


We develop case study materials for innovative biological application of computational methods in Industrial Engineering; Convex Recoloring (CR) Problem on a Phylogenetic Tree.

The convex recoloring (CR) problem is to recolor the nodes of a colored graph at minimum number of color changes such that each color induces a connected subgraph, where the colored graph is a phylogenetic tree with leaf nodes assigned to pieces of protein sequences. If the minimum number is too large, the species represented in colors need to merge into one species. In the history of bioinformatics, linear programming has not been used while it is used in Industrial Engineering to solve many problems raised in almost every industry.

We adjust to the convex recoloring problem the column generation framework developed by Johnson, Mehrotra and Nemhauser in 1993. A column generation framework saves a lot of space complexity and can be developed in Excel Worksheet. For the convex recoloring problem on a phylogenetic tree, the subproblem to generate columns can be solved by Excel Solver as the size of the subproblem is very small.

The initial Excel Worksheet is designed by the authors to check in toy model if the column generation framework works well for the CR problem on a phylogenetic tree. The research appears in a decent proceedings in Industrial Engineering. The Worksheet is being refined by students taking an undergraduate optimization course as course project in Fall 2017. To increase the scale of the problem instances, they use Open Solver another add-in to Micro Soft Excel which is endorsed by Computational Infrastructure for Operations Research (COIN-OR.) The Worksheet will be used as course material in undergraduate optimization courses and computational methods courses in biomedical engineering.

Erdem, E., & Shim, S. (2018, June), Board 101 : A Steepest Edge Rule for a Column Generation Approach to the Convex Recoloring Problem Paper presented at 2018 ASEE Annual Conference & Exposition , Salt Lake City, Utah. 10.18260/1-2--29857

ASEE holds the copyright on this document. It may be read by the public free of charge. Authors may archive their work on personal websites or in institutional repositories with the following citation: © 2018 American Society for Engineering Education. Other scholars may excerpt or quote from these materials with the same citation. When excerpting or quoting from Conference Proceedings, authors should, in addition to noting the ASEE copyright, list all the original authors and their institutions and name the host city of the conference. - Last updated April 1, 2015