Investigations in Mixed Integer Programming

本研究的主要焦点是发展混合整数规划的有效计算方法。将开发一个基于非线性内点的分支定界求解器，强调在树搜索环境中有效实现非线性子问题求解器，以及它在解决现实世界实例中的实用性。并行性将被用来利用并发计算的优势，并增强求解器解决这些np困难问题的能力。本研究的另一个重点是探索混合整数规划的新应用。由于应用程序为推进不断发展的学科前沿提供了宝贵的见解和动力，因此工作将部分集中在实际应用中产生的结构上。第一个问题来自计算密集型的统计分类领域，它与机器学习、神经网络和模式识别有着密切的联系。这项工作将建立在先前工作的基础上，涉及最初作为非线性MIP制定的分类模型。该模型的新颖之处在于它允许对错误分类概率进行一定程度的控制，并允许将实体分类到保留的判断区域。这种方法非常适合错误分类可能产生可怕后果的应用（例如，医疗诊断）。我们将探索基本模型的变化，试图发现一个既能在计算上处理大规模问题，又能有效地生成产生准确分类的规则的版本。第二个应用涉及近距离治疗的治疗计划优化，近距离治疗是一种放射治疗，涉及在肿瘤内或肿瘤附近植入放射源（种子）。在近距离放射治疗中，放射粒子的最佳放置位置和剂量是一个具有挑战性的问题。提出了一种新的混合整数规划模型，目前的重点是基于该模型的多面体结构开发有效的协同计算策略。临床计算测试将使用前列腺癌病例的数据进行。所得到的优化求解器将与图形化评估工具一起设计，以便在手术室中实时使用。

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.