Investigations in Mixed Integer Programming

点击翻译按钮获取中文摘要

A primary focus of this research is to develop effective computational methods for mixed integer programs. A nonlinear interior-point based branch-and-bound solver will be developed, emphasizing effective implementation of the nonlinear subproblem solver within the tree search environment, and its practicality in solving real-world instances. Parallelism will be exploited to take advantage of concurrent computing and to enhance the solver's capability for solving these NP-hard problems. Another focus of this research is to explore new applications of mixed integer programming. As applications provide invaluable insight and motivation for advancing the frontiers of an evolving discipline, the work will, in part, focus on structures arising from practical applications. The first problem arises from the computationally intensive area of statistical classification, which has close connections with machine learning, neural networks and pattern recognition. This work will build on previous work involving a classification model formulated initially as a nonlinear MIP. The novel aspects of the model are that it allows a level of control on misclassification probabilities and allows entities to be classified into a reserved judgment region. Such an approach is well-suited for applications in which misclassification can have dire consequences (e.g., medical diagnosis). Variations in the basic model will be explored in an attempt to uncover a version that is both computationally tractable for large scale problems, and effective in generating rules that yield accurate classification. A second application concerns treatment planning optimization for brachytherapy --- a type of radiation therapy that involves implanting radioactive sources (seeds) in or near tumors. The optimal placement and dosage of the radioactive seeds in brachytherapy is a challenging problem. A novel mixed integer programming model has been developed, and the focus now lies in developing effective co mputational strategies based on the polyhedral structure of the model. Clinical computational tests will be performed using data from prostate cancer cases. The resulting optimization solver will be designed, along with graphical evaluation tools, for real-time use in the operating room.