Michael C. Ferris - US grants

Efficient serial and parallel algorithms, backed by a mathematical programming theory, are developed. Emphasis is placed on effective distribution of constraints among processors as well as line-search stabilization techniques nonlinear complementarity and other problems. Finite termination of algorithms via weak sharp minima and related concepts will investigated.

9970122
Ferris

This award will support participants at the ICCP99: International Conference
on Complementarity Problems: Contemporary Applications and Algorithms
to be held at the Wisconsin Center of the University of Wisconsin-Madison
from June 9-12, 1999. The general goal of the conference is to bring
together researchers from a variety of backgrounds who are involved in
theoretical, applied, and/or computational research on complementarity
problems. They will present and discuss the latest results in this area, and
offer suggestions for collaborative research and further development of the
field. The conference will focus on three major themes: (1) finance and
economic applications, (2) engineering and machine learning, and (3)
computational methods.

Modeling languages are heavily used in practice and therefore supply a critical vehicle for collaborative research in optimization. This project will faciliate this interaction by broadening the usage of optimization tools and environments in application areas. Due to the increasing demands in the size and complexity of applications, it has become vitally important for mathematical programmers to develop algorithms and tools within a modeling framework in order to advance the state-of-the-art in both applications and optimization. The thrust of the research will be in providing explicit examples of optimization technology, within targeted projects, and will address computational and tlieoretical aspects of large scale optimization in a practical setting.
The new tools, environments, and algorithms of this proposal will enable an interactive approach to modeling with direct input from application and optimization experts during model development. The proposal will demonstrate such interactions within four application areas, namely the architectural design of video on-demand systems, cancer treatment plans in the context of tomotherapy, mathematical programming approaches to data mining, and the solution of complementarity problems arising in economics. A pivotal need is for visualization of optimization results within the application; a link between modeling languages and MATLAB will be provided for this purpose. An additional benefit of this link is the provision of a sophisticated mathematical programming capability to the MATLAB programniing environment.
To address important issues and facets identified by domain experts, the resulting optimization problems are very large and require vast amounts of computing resources. Several new tools to enable the formulation and solution of such optimization problems on a metacomputer will be generated, all utilizing a pool of pre-existing, "off-the-shelf" workstations via Condor. A key component of the research will derive new algorithms that work within the proposed framework and exploit the metacomptiting resources. These include several new solvers for large scale complementarity problems and a fault tolerant parallel mixed integer programming solver.
A fundamental goal of this effort is to educate researchers in other disciplines, primarily senior level undergraduates and graduate students, on the utility, use and power of these tools. Several of the application collaborations detailed in this proposal are direct consequences of interactions with colleagues and students during the first teaching of a course based on the topics of this project.

This project will use new techniques from computational optimization to design radiation therapy planning for cancer treatment.

Radiation therapy applies ionizing radiation to cancerous tissue, damaging the DNA and interfering with the ability of the cancerous cells to grow and divide. This also damages healthy cells, but they are more able to repair the damage and return to normal function. The therapy planning problem is to specify the shapes of the applied radiation beams, times of exposure, etc., to deliver a specified dose to the tumor but not an excessive dose to the surrounding healthy tissue. New medical devices allow much control over the characteristics of the radiation, thus allowing much scope for the therapy planning. However, the full potential of these devices to deliver optimal treatment plans has yet to be realized due to the complexity of the treatment design process. By using advanced modeling techniques, state-of-the-art optimization algorithms, and implementations on parallel computing platforms this project will provide radiation oncologists with important new computational tools for treatment planning. These tools will be flexible enough to adapt to the varying priorities of different planners and different patients and robust enough to give good solutions to the most difficult planning problems. The project involves collaboration between three researchers whose collective expertise encompasses radiation oncology modeling, optimization algorithms, and parallel implementations. It builds on previous collaborations of these researchers on treatment planning and on NSF-funded work on algorithms for solving large optimization problems.

The institutions involved in the project are the University of Wisconsin and the University of
Maryland School of Medicine.

Proposal: DMS-0427689
PI: Michael C. Ferris
Institution: University of Wisconsin-Madison
Title: ITR-(ASE)-(dmc): Overcoming Fractionation Errors in Cancer Treatment Planning

ABSTRACT

The investigators study the use of optimization techniques in designing radiation treatment plans for cancer patients. In external-beam radiotherapy, beams of radiation are aimed into the patient's body from different angles. The treatment planning process chooses the shapes, intensities, and angles of the beams such that the cancerous tumor receives a high dose of radiation, while critical organs and normal tissue adjacent to the tumor are spared, to the extent possible. Radiation is not delivered in a single dose, but rather in fractionated daily doses over a period of up to 9 weeks. The latest generation of radiation devices allows the delivery of highly optimized and accurate treatment plans. This project uses the power of distributed computing and of advances in modeling and optimization to realize the full potential of these devices. Advances are being made on two major fronts. First, the quality of the initial treatment plan is improved by using stochastic and nonlinear optimization methodology to construct formulations of the treatment planning problem that take uncertainty explicitly into account. Second, imaging data gathered at each treatment session is used to perform adaptive radiotherapy, in which the treatment plan is adjusted between sessions to compensate for organ movement, tumor shrinkage, and other fractionation errors that occurred in previous treatment sessions. Handling of huge data sets and large quantities of compute cycles is needed to perform the required calculations in real time---in part, while the patient is lying on the couch of the treatment device.

Forty percent of all cancer patients receive radiation therapy as a key part of their treatment regimen, and devices that deliver radiation treatments are becoming progressively more sophisticated and powerful. This collaboration between mathematicians, computer scientists, and medical physicists is improving the effectiveness of the treatment planning process by choosing the shapes and intensities of the radiation beams used during treatments to target the cancerous regions more accurately and avoid radiation damage to healthy tissues. The optimization techniques being developed and implemented in the project also allow for day-to-day adjustment of the treatment plan, to account for changes in the internal organs and patient movement during treatment. The key feature of the project is its use of advanced computing platforms in conjunction with optimization methods to improve the effectiveness of a vitally important medical procedure.

Integer programming is an optimization technique that supports optimal decision making in organizations. Traditionally, it has been successfully applied to strategic planning problems where solution time is not an issue. The innovation of this research is to extend the applicability to operational and tactical decision making where rapid solution times are necessary. A key characteristic of problems arising in real-time environments is that consecutive instances typically differ only slightly, indicating a need for technology that supports incremental problem solving. Further, the algorithms developed will be designed to exploit the computational power and data delivery capabilities of the emerging cyberinfrastructure. The applicability of the research will be demonstrated in three specific application areas: supply chain management, airline disruption recovery, and radiation therapy treatment planning.

The successful development of real-time integer programming technology has huge potential for addressing difficult operational problems. Its tactical use may dramatically improve airlines' ability to recover from disruptions, significantly enhance the quality of radiation therapy for cancer patients or provide huge economic benefits by increasing the agility of supply chains. Another high-impact aspect of the research will be its pioneering use of cyberinfrastructure. This proposal will open up new possibilities for the operations research community to exploit the computational, data storage, and communication resources that are now becoming available for use in real-time decision making. Moreover, the methods and frameworks developed in this research will help to shape how cyberinfrastructure is harnessed to provide decision support in a wide
variety of application areas.

Abstract
NSF-0511905

Mangasarian, Olvi

Massive datasets occur in all types of settings ranging from the highly scientific to the ubiquitous internet. Making sense of this massive data requires sophisticated computer sciences techniques such as data classification, approximation and optimization. All of these techniques can be improved substantially by making effective use of prior knowledge that is often readily available. For example doctors' experience can be utilized in obtaining improved classifiers for various types of important problems, such as medical diagnosis and prognosis. Since the most powerful state-of the-art classifiers are based on support vector machines, which in turn are formulated as constrained or unconstrained optimization problems, the aim is that prior knowledge be incorporated into various optimization-based applications such as classification and approximation problems as well into the theory of optimization itself. To a large degree, this proposal is motivated by the investigators' extensive collaborative work with oncologists, surgeons and medical physicists and the investigators' desire to make full use of the expertise of such practitioners by incorporating it into computable but rigorous models.

The intellectual merit of the proposed work lies in the use of rigorous theory and problem analysis techniques that incorporate domain specific information into general optimization problems. The research will first incorporate knowledge into a linear or nonlinear support vector machine classifier and show that such incorporation is possible by appending additional constraints to the original problem. Preliminary tests indicate improvements in classifier accuracy. Secondly, prior knowledge will be introduced into approximation problems. Thus, in addition to given discrete data that is normally used to generate an approximation to an unknown function, prior knowledge is also taken into account. Finally, prior knowledge will be incorporated into general constrained or unconstrained optimization problems, wherein the prior knowledge consists of new constraints to be imposed on the behavior of the objective function on various regions. The generality of these new techniques will facilitate the integration of information from disparate sources, since the theory allows multiple sets of prior information to be included concurrently. Specific application to radiotherapy treatment planning problems will ensure the computer science advancements are demonstrably useful in a particular problem domain.

The optimization, modeling, and computational techniques will provide a boost to advances in cancer diagnosis and prognosis, chemotherapy, and other treatment regimes. The knowledge-based approach encompasses a broad spectrum of important classification and approximation problems that have wide applicability
in science and engineering. The work will also raise the profile of data mining techniques in other areas such as surgery, pharmacology, and medical research, by demonstrating how the methodologies can be
utilized to incorporate prior knowledge into both planning and design issues, and improving both efficiency of delivery and effectiveness of treatment in many clinical settings. By coupling the education of several
computer science and engineering students with the proposed work, a new group of multidisciplinary researchers will be trained that will ensure the technical advances are applied to further application domains.

The second International Conference on Continuous Optimization will be held at McMaster University, Hamilton, Ontario, Canada in August 2007. The Conference will be preceded by a two-day Summer School, where several distinguished scholars will offer classes on selected topics in continuous optimization for advanced graduate students and postdoctoral fellows. The goal of the Conference is threefold: (a) to provide a focused forum for US and international researchers and practitioners to facilitate the rapid exchange of state-of-the-art results and promising ideas within continuous optimization, (b) to offer educational opportunities to graduate students and junior researchers to learn about the latest developments in continuous optimization, and (c) to encourage women and minority researchers to work in this important area of Operations Research and Computational Science. This project is supported by the Operations Research Program of the Civil, Mechanical & Manufacturing Innovation Division, and the Office of International Science and Engineering.

Optimization has evolved over the past four decades into a thriving discipline that has strong theoretical underpinnings and plays a major role in many practical application areas. As the need for improved operation of many physical and scientific systems arises, the role of optimization techniques is growing quickly. The conference will provide a stimulus for sustained research in continuous optimization, while the summer school will have a particular emphasis on high-performance computational optimization. Beyond the application specific domains, broader impacts include the exploration of how large-scale continuous optimization will affect and be affected by cyber-infrastructure and multi-core networked computing.

Traditional optimization approaches are no longer effective in solving
practical, large scale, complex problems from many application domains. Typical applications require a sophisticated coupling of a number of optimization and complementarity modeling approaches with specific domain knowledge and expertize to generate solutions in a timely and robust manner. This project will develop tools and algorithms that help in solving coordinated problems of this nature by formulating and exploring the notion of an extended mathematical program (EMP). This provides the ability to model competition between agents using the notion of an embedded model, a feature that is missing from other optimization approaches. Specific instances include dynamic games that are used to analyze interactions between agents in multiple fields, including industrial organization, labor and financial bargaining and contracts, government design of fiscal and monetary policies, auction design, political decision-making and international conflict resolution. The major benefits are threefold: EMP will make the modelers task easier, in that the model can be described more naturally and at a higher conceptual level; the actual model to be solved can be reliably and efficiently generated; an algorithm can exploit additional structure in an effective computational manner. Building on earlier work, this project will develop theory-based, efficient, fast, reliable, user-friendly numerical methods to solve extended mathematical programs.

If successful, this project will develop a general modeling framework, applicable to a wide range of real problems and will produce a coherent and comprehensive suite of tools for modeling and computation that can be applied to systems in many application areas. It is anticipated that further significant advancements in operations research applications can be achieved via identification of specific problem structures within a given model, a notion that forms the core of an EMP. Difficulties associated with multiplicity of equilibria and the large dimension of the underlying problems will be addressed by communicating structure to solvers and developing new algorithms that explicitly utilize that structure for more robust solution. The project aims to demonstrate that the availability of such structure fosters the generation of new features to existing solvers and drives the development of new classes of algorithms. The algorithms and methods that will be implemented here will be made available to the whole user community via modeling system hookups to GAMS, AMPL and MATLAB, and via broad dissemination via the internet using resources such as the NEOS server and the COIN-OR project.

This project explores the hypothesis that compelling learning games based on contemporary science that offer opportunities to contribute to scientific inquiry will lead to increased interest in science, increased career choice of science, increased conceptual understanding of science content, and better scientific literacy around what scientists do. The idea is to capitalize on crowd sourcing both to shed light on the answers to open scientific questions and to engage the public in authentic and needed scientific inquiry in meaningful ways. The PIs will extend four games that are already designed and built or that are under construction and develop a platform for supporting a broad range of participatory science games that offer the public opportunities to contribute to scientific inquiry. The chosen games all encourage sustained and deep participation, include apprenticeship opportunities and opportunities for practicing authentic science, promote reflection in and on action, and are designed to be emotionally compelling. Games come from four game genres: role-playing, strategy, action, and puzzle, as different people are drawn to different types of experiences. All are in the areas of bioscience and biotechnology, and each addresses some open question in bioscience or biotechnology that participants might shed light on. The broad range of games serves several purposes -- offering a substantial enough range of experiences that a broad range of participants can be expected to join in, offering enough diversity to know that the infrastructure tying the games together has all of the functionality required to support a broad range of such games, and offering enough diversity to answer targeted research questions. Research focuses on identifying the challenges in creating a broad and diverse public gaming community that interacts with more formal and established scientific and educational cultures, how learning occurs in such an environment and how to promote sustained engagement and deep learning, identifying core features and mechanisms of games that promote sustained engagement and science learning, and understanding the design features in the particular games being studied that contribute to sustained engagement and learning.

There is an increasing awareness among scientists that many contemporary science problems require (or could benefit tremendously from) an actively engaged public. Communicating the challenges and opportunities of science, and mobilizing the public to participate in and support scientific inquiry, requires shared understandings about the values, methods, and epistemologies of science (e.g., observation, data collection and analysis, reasoning from evidence, skepticism). This project focuses on design of learning opportunities that are both engaging and informative with respect to scientific literacy. The public is invited to participate in a variety of science-related "games," experiences with scientific inquiry that are engaging and exciting and that can contribute to scientific findings. Participants engage as scientists, carrying out the practices of scientists and reasoning about evidence to draw conclusions, in the process experiencing the thrills and frustrations involved in scientific discovery and inquiry. Investigators observe the participants in these games to draw out principles for designing additional learning experiences that can engage the public in science and promote scientific literacy and learning at the same time. What is learned in this analysis will also be applicable to designing engaging science experiences for use in schools.