This work funded in part by US Dept of Energy, MICS Division, and by the Sandia National Laboratories Laboratory-Directed Research and Development program.
PICO will be able to adaptively incorporate application-specific methods (combinatorial approximation algorithms and genetic algorithms), for both lower and upper bounds, to limit the search space explored.
State-of-the-art MIP codes provide performance-enhancing features that are specific to MIP, but not application-specific. For example, default branching strategies must allow user-defined priorities, and branching based on global ``derivatives'' (pseudocosts), locking of variables, and preprocessing. We will add a novel feature: a genetic algorithm that attempts to round a generic fractional linear-programming solution to a feasible solution. If the procedure is effective, then new solutions can enable faster pruning of suboptimal regions.
If one requires highest performance on a class of instances, some application-specific tuning may be required. Users can supply combinatorial approximation algorithms or genetic algorithms which exploit structure unique to the problem class. These can be run in conjunction with the system defaults or in place of them. Similarly, the user can supply lower-bounding procedures, which can increase pruning by increasing lower bounds. Though the system will provide default cutting planes, particularly for binary integer variables, user-supplied cutting plane methods are likely to provide vastly superior performance.
Mixed-integer programming (MIP) is a core optimization technology, and this capability can be applied in other areas consistent with Sandia's mission: nonproliferation, transportation, infrastructure analysis and design, manufacturing, energy, environment, and tools for massively parallel computation such as meshing.