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

\bibitem{asee_peer_29857}
  Erdem, E., \& Shim, S. (2018, June), \emph{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

Ergin Erdem and Sangho Shim.  "Board 101 : A Steepest Edge Rule for a Column Generation Approach to the Convex Recoloring Problem".  2018 ASEE Annual Conference & Exposition , Salt Lake City, Utah, 2018, June.  ASEE Conferences, 2018.  https://peer.asee.org/29857 Internet.  14 Dec, 2024

\bibitem{asee_peer_29857}
  Ergin Erdem and Sangho Shim.
  "Board 101 : A Steepest Edge Rule for a Column Generation Approach to the Convex Recoloring Problem".
  \emph{2018 ASEE Annual Conference \& Exposition , Salt Lake City, Utah, 2018, June}.
  ASEE Conferences, 2018.
  https://peer.asee.org/29857 Internet.  14 Dec, 2024

@INPROCEEDINGS{asee_peer_29857
author = "Ergin Erdem and Sangho Shim"
title = "Board 101 : A Steepest Edge Rule for a Column Generation Approach to the Convex Recoloring Problem"
booktitle = "2018 ASEE Annual Conference \& Exposition "
year = "2018"
month = "June"
address = "Salt Lake City, Utah"
publisher = "ASEE Conferences"
note = {https://peer.asee.org/29857}
number = {10.18260/1-2--29857}
}

TY  - CPAPER
AB  - 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.

AU  - Ergin Erdem
AU  - Sangho Shim
CY  - Salt Lake City, Utah
DA  - 2018/06/23
PB  - ASEE Conferences
TI  - Board 101 : A Steepest Edge Rule for a Column Generation Approach to the Convex Recoloring Problem
UR  - https://peer.asee.org/29857
DO  - 10.18260/1-2--29857
ER  -