Mixed Integer Solver Technology for Accelerated Computing Systems (SBIR)

Solicitation PDF

• Original at OSTI
• Cached local copy

Selected Pages

Selected Extracts

This topic is focused on specific technologies that are required to advance the state of accelerated computing applied to mixed integer programming (MIP) problems arising in scientific applications. The primary focus of this topic is on the computer science needed to address the challenges in manifestation of scalable, distributed (multi-node) algorithmic techniques and not on combinatorial theory development.

MIP problems underlie many important application areas of interest to DOE, including biological systems, transportation networks, electric grids, and user facility infrastructures. While significant advances have been made in the theory and implementation of MIP solver methods on conventional central processing unit (CPU)- based hardware, new advances are necessary to fully utilize the DOE investments in accelerated computing platforms such as graphical processing unit (GPU)-based computers and high-performance computing systems. Preference may be given to applications that leverage existing ASCR software investments.

Grant applications focused on the following will be considered out of scope:

• Cut generation, cut storage, cut manipulation methods,
• Column generation methods,
• Theory,
• Fragments of technology that are isolated and cannot be demonstrated as part of a working MIP solver on standard problems such as found in the MIPLIB series, and
• Solutions that cannot be demonstrated to run on GPU-based accelerators used in current or planned supercomputing systems of DOE leadership computing facilities.

Grant applications are sought in the following subtopics:

a. Efficient Distributed Tree Management This topic is focused on tree management that arises in branch-and-bound or branch-and-cut (B&C) methods to MIP solution methods. Research must focus on efficient representation and encoding of the B&C tree on accelerated memory hierarchies and address the challenges of efficient tree node movement, including exploitation of direct memory access (DMA) of accelerated memory across high-speed networks. Methods must solve the problem of scalable and efficient manipulation of B&C tree nodes. This includes the ability to query the quality of linear program relaxation, node ancestor identification, node deletion, and updates to the node data.

b. Efficient Linear Program Relaxation Solution Implementations of interior or exterior point methods must be developed specifically optimized for accelerated hardware using single-instruction-multiple-thread (SIMT) control flows or reconfigurable field programmable gate arrays (FPGAs). Methods must build on existing or new sparse and dense solvers and capable of static or dynamic (on-the-fly) choice of sparse versus dense solver based on the density of matrices20 Return to Table of Contents encountered in the input scenarios. Applicants may propose solving the linear program relaxations of MIP problem matrices that either fit entirely within a single node’s memory or large problem sizes where matrices do not fit within a single node’s memory but span multiple node memories. Milestones must aim to solve the relaxations of root nodes in increasing fractions (10%, 50%, 75%, 90%) of the problems in the MIPLIB 2017 problem set (with priming or probing methods not necessarily applied to the root problems).