Degree Type

Dissertation

Date of Award

2012

Degree Name

Doctor of Philosophy

Department

Industrial and Manufacturing Systems Engineering

First Advisor

Lizhi Wang

Abstract

This thesis consists of three journal papers I have worked on during the past three years of

my PhD studies.

In the first paper, we presented a multi-objective integer programming model for the gene stacking problem. Although the gene stacking problem is proved to be NP-hard, we have been able to obtain Pareto frontiers for smaller sized instances within one minute using the state-of-the-art commercial computer solvers in our computational experiments.

In the second paper, we presented an exact algorithm for the bilevel mixed integer linear programming (BMILP) problem under three simplifying assumptions. Compared to these existing ones, our new algorithm relies on weaker assumptions, explicitly considers infinite optimal, infeasible, and unbounded cases, and is proved to terminate infinitely with the correct output. We report results of our computational experiments on a small library of BMILP test instances, which we have created and made publicly available online.

In the third paper, we presented the watermelon algorithm for the bilevel integer linear programming (BILP) problem. To our best knowledge, it is the first exact algorithm which promises to solve all possible BILPs, including finitely optimal, infeasible, and unbounded cases. What is more, our algorithm does not rely on any simplifying condition, allowing even the case of unboundedness for the high point problem. We prove that the watermelon algorithm must finitely terminate with the correct output. Computational experiments are also reported showing the efficiency of our algorithm.

DOI

https://doi.org/10.31274/etd-180810-47

Copyright Owner

Pan Xu

Language

en

File Format

application/pdf

File Size

78 pages

Share

COinS