MINLP Methods for Chance-Constrained Problems with Endogenous and Exogenous Uncertainty
Abstract
Chance-constrained mathematical problems are optimization models with stochastic constraints and for which an optimal solution satisfying all constraints with a minimum probability level is sought. These problems are pervasive in logistics and real-time system management. We plan to develop theory and software to solve real-size instances of such problems. More specifically, we will look at the following three applications:Medical Evacuation from the Battlefield. The medical evacuation of severe casualties from the battlefield concern the transport the most urgent casualties to a medical treatment facility (MTF) via a fleet of air ambulances. ? Robust Air Defense Formation for Naval Force. The determination of a robust air defense formation for a naval force with known ship and air defense capabilities is essential. A robust formation is effective against a variety of attack scenarios that may come from uncertain directions. ? Reliable Target Detection with Unmanned Aerial Vehicles. The determination of a robust air defense formation for a naval force with Medical Evacuation from the Battlefield. The medical evacuation of severe casualties from the battlefield concern the transport the most urgent casualties to a medical treatment facility (MTF) via a fleet of air ambulances. ? Robust Air Defense Formation for Naval Force. The determination of a robust air defense formation for a naval force with known ship and air defense capabilities is essential. A robust formation is effective against a variety of attack scenarios that may come from uncertain directions. ? Reliable Target Detection with Unmanned Aerial Vehicles. The determination of a robust air defense formation for a naval force withWhile these three applications seem quite different, their deterministic variants can both be formulated as Nonlinear Facility Location problems where nonlinearities are limited to quadratic monomials in the left-hand side of the inequalities. The type of stochastic nonlinear facility location models studied here is very encompassing, and includes problems when one has to locate both fixed (e.g., hospitals) and mobile (e.g., ambulances) servers and service must be provided within a specified time. This is for example the case in location-routing problems which determine depotlocations, assign trucks to depots, and find routes for trucks to make deliveries from depots to customers within a certain delay.This projects aims at developing methods to solve this type of problems using a Boolean reformulation method based on the binarization of probability distributions. This Boolean reformulation applied to the problems considered in this proposal yields a deterministic problem where nonlinearities are polynomials of degree at most 3. We plan to study various reformulation of these problems, as well as customization of a nonlinear solver tailored to their solution, with the objective to solve problems of size relevant to practice. Some of the reformulation will be exact, meaning that the optimal solution of the reformulation gives the optimal solution of the original problem, while others will be inner approximations (yielding a feasible but possibly suboptimal solution) or outer-approximations (yielding a bound on the optimal value of the solution).
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- May 05, 2017
- Source ID
- N000141712420
Entities
People
- Miguel A. Lejeune
Organizations
- George Washington University
- Office of Naval Research
- United States Navy