Search

Solution methods are presented for a mixed-integer program (MIP) associated with a method for constrained discrimination. In constrained discrimination, one wishes to maximize the probability of correct classification subject to intergroup misclassification limits. The misclassification limits are satisfied by allowing the placement of observations in a reserved judgment group. The approach investigated here involves modifying a standard classification rule by solving an optimization problem. A polynomial-time algorithm for solving the problem is given for two-group discrimination. The decision problem upon which the optimization problem is based is shown to be NP complete for a general number of groups. For three or more groups, an MIP is used to solve the problem. Solution methods incorporating cutting planes from conflict graphs are presented for solving instances in a branch-and-bound framework. These methods are used to enhance industry-standard software, and are shown to provide as much as a 20-fold reduction in computational time over the software alone. Computational experiments illustrate the tradeoff between misclassification rates and reserved judgment rates. Some base classifiers are not well suited to be modified to a constrained discrimination rule. The method for constrained discrimination studied here performs particularly well in the presence of class imbalance. For certain other data sets, however, the method is outperformed by a simple centroid method. [ABSTRACT FROM AUTHOR]

Cervical cancer has a high mortality rate (approximately 35 percent) in the United States and is difficult to treat successfully. One promising treatment is high-dose-rate brachytherapy, which entails delivering high-dose radiation to the tumor via the temporary implantation of radioactive seeds. This treatment promises to be particularly effective in eradicating tumors while preserving the organs. Yet, major obstacles to successful treatment remain, especially (1) determining the best seed type, spatial configuration of seeds, and seed dwelling time, and (2) improving the probability that the treatment will eliminate all malignant cells. We developed an advanced planning model to simultaneously address both of these issues. To permit taking advantage of the best available information, our model works with inputs from positron emission tomography. We begin with a multiobjective, nonlinear, mixed-integer programming model that is initially intractable. To solve the model, we introduce an original branch-and-cut and local-search approach that couples new polyhedral cuts with matrix reduction and intelligent geometric heuristics. The result has been accurate solutions that are obtained rapidly. Clinical trials at Rush University Medical Center demonstrated superior medical outcomes. These analytical techniques are applicable not only to cervical cancer, but also to other types of cancer, including breast, lung, and prostate cancer. [ABSTRACT FROM AUTHOR]

Classification is concerned with the development of rules for the allocation of observations to groups, and is a fundamental problem in machine learning. Much of previous work on classification models investigates two-group discrimination. Multi-category classification is less-often considered due to the tendency of generalizations of two-group models to produce misclassification rates that are higher than desirable. Indeed, producing “good” two-group classification rules is a challenging task for some applications, and producing good multi-category rules is generally more difficult. Additionally, even when the “optimal” classification rule is known, inter-group misclassification rates may be higher than tolerable for a given classification model. We investigate properties of a mixed-integer programming based multi-category classification model that allows for the pre-specification of limits on inter-group misclassification rates. The mechanism by which the limits are satisfied is the use of a reserved judgment region, an artificial category into which observations are placed whose attributes do not sufficiently indicate membership to any particular group. The method is shown to be a consistent estimator of a classification rule with misclassification limits, and performance on simulated and real-world data is demonstrated. [ABSTRACT FROM AUTHOR]

A parallel implementation of a disjunctive cutting-plane algorithm in a distributed memory environment is described. Guided by a selection of difficult instances from MIPLIB and real instances obtained from brain-tumor research, various strategies of cut synchronization are considered, and their influence on speedup, communication overhead, load balance, and effectiveness in closing the integrality gap are studied. The parallel cutting-plane algorithm is coupled with an LP-based heuristic to assist in returning a good quality integer feasible solution upon termination of the parallel process. The parallel implementation is sufficiently coarse grained to yield an average of less than 6% of the total time performing tasks associated with communication overhead, and it provides reasonable speedup when executing in parallel. Noticeable differences in load-balance scores are observed, depending on the number of processors used, the synchronization scheme used, and the structure of the MIP problem instance. Nevertheless, the synergism of the combined collection of cuts generated locally on each processor is effective in closing the integrality gap in all cases, and there is minimal variability in the amount of the gap closed as the number of processors varies. In particular, the degree of decentralization, as governed by the synchronization schemes, has little effect on the overall quality of the cuts generated. [ABSTRACT FROM AUTHOR]

Mixed integer programming models and computational strategies developed for treatment planning optimization in brachytherapy are described. The problem involves the designation of optimal placement of radioactive sources (seeds) inside a tumor site. Two MIP models are described. The resulting MIP instances are difficult to solve, due in large part to dense constraint matrices with large disparities in the magnitudes of the nonzero entries. A matrix reduction and approximation scheme is presented as a computational strategy for dealing with the dense matrices. Penalty-based primal heuristic and branching strategies to assist in the solution process are also described. Numerical results are presented for 20 MIP instances associated with prostate cancer cases. Compared to currently used computer-aided planning methods, plans derived via the MIP approach use fewer seeds (20-30 fewer) and needles, and provide better coverage and conformity - measures commonly used to assess the quality of treatment plans. Good treatment plans are returned in 15 CPU minutes, suggesting that incorporation of this MIP-based optimization module into a real-time comprehensive treatment planning system is feasible. [ABSTRACT FROM AUTHOR]

Numerical experiments for a parallel implementation of a branch-and-bound mixed 0/1 integer programming code are presented. Among its features, the code includes cutting- plane generation at the root node, and employs a new branching-variable selection rule within the search tree. The code runs on a loosely-coupled cluster of workstations using TreadMarks as the parallel software platform. Numerical tests were performed on all mixed 0/1 MIPLIB instances as well as two previously unsolved MIP instances, one arising from telecommunication networks and the other a multicommodity flow problem. [ABSTRACT FROM AUTHOR]

A nonlinear 0/1 mixed integer programming model is presented for a constrained discriminant analysis problem. The model places restrictions on the numbers of misclassifications allowed among the training entities, and incorporates a ‘reserved judgment’ region to which entities whose classifications are difficult to determine may be allocated. Two linearizations of the model are given — one heuristic and one exact. Numerical results from real-world machine-learning datasets are presented. [ABSTRACT FROM AUTHOR]