Improving Branch-and-bound algorithms for MILPs.
Abstract
Since its inception a little over sixty years ago, mathematical models known as Mixed-Integer Linear Programs (MILPs) have been used to represent a vast array of decision problems in such diverse scenarios as energy and power systems, logistics and supply-chain design, manufacturing, network interdiction and cyberattacks, military operations research, national defense, finance, and airline operations. MILP solvers have been developed and are commercially available, but the underlying mathematical difficulty associated with solving MILPs, coupled with the increasingly complex nature of problems under consideration, requires more efficient methodologies. Such solvers are based on branch-and-bound algorithms that attempt to efficiently enumerate through the feasible decision alternatives, together with enhancements that include pre-solve routines, cutting-planes, and heuristics. The two main components of branch-and-bound are- (i) the branching mechanism for keeping track of solutions considered and prescribing new solutions to explore within an enumerative tree, and (ii) a bounding routine for eliminating infeasible and-or nonoptimal solutions from further consideration. This effort seeks to gain a better understanding of the sizes of the branch-and-bound trees that will be encountered based on the branching mechanisms employed, both for general and specially-structured problems.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Mar 07, 2023
- Source ID
- FA95502210052
Entities
People
- Santanu S. Dey
Organizations
- Air Force Office of Scientific Research
- Georgia Tech Research Corporation
- United States Air Force