Hello, A yearly allocation for the LCRC cluster has been requested with the following updated information: Submitter/PI: Ashutosh Mahajan Project Name: MINOTAUR Division: MCS Project title: Next-Generation Solvers for Mixed-Integer Nonlinear Programs: Structure, Search, and Implementation Associated funding: DOE, through grant DE-FG02-05ER25694. Other Systems: None Science: One of our objectives in this project is to develop powerful algorithmic frameworks to solve previously intractable mixed-integer nonlinear programs (MINLPs). Another is to deliver implementations of these frameworks in new, publicly available solvers. Towards these ends, we are developing the solver MINOTAUR that can solve such problems found in many diverse applications. The difficulty and consequently, the solution time for these problems grow exponentially in the size of the input. Our objective is to harness the parallel processing machines to solve these problems in reasonable time. Another important part of this development is experimenting with many different algorithms and parameters in order to identify the best operating parameters based on the problem structure. Project description: Minotaur framework, at its core, a generic robust branch-and-bound based tree search. A linear or nonlinear relaxation of the MINLP is obtained by relaxing the integrality restrictions on the variables. This relaxed problem is then solved using an appropriate solver. The solution to this problem provides a lower bound (assuming we are minimizing a function). Integrality is then enforced by creating two subproblems or branches, none of which contain the current solution. The procedure is then recursively applied to both branches. In its current state, Minotaur is essentially a serial code, with several sophisticated algorithms to create relaxations and strengthen them, methods for branching, heuristics etc. We are currently trying novel methods to avoid or reduce the combinatorial explosion associated with branch-and-bound. The branch-and-bound method is naturally attractive for parallelizing because of the sheer number of many different subproblems that need to be solved. However, devising ways to effectively harness multiple cores/cpus is a challenge. Since the difficulty of these problems increases exponentially in size, it means that one may need twice as many cpus for just one new variable. We are working on methods to tackle this problem by eliminating large parts of search tree by doing more analysis and exploiting the problem structure. Techniques like strong branching, bound tightening, probing and primal heuristics can be applied effectively in parallel. We will be developing software that utilizes multiple cores on a single node of Fusion for these purposes. We have a large set of different problems (> 500) that need to be solved. With each instance taking up to 4 hours, we will need to run Minotaur on many nodes simultaneously to solve the whole set in reasonable time. Project URL: Current FY Hours Used: undetermined amount New FY Requested allocation: 48000 Q1: 12000 Q2: 12000 Q3: 12000 Q4: 12000 Justification: Thank You, The LCRC Accounts System