IBM

Cyber-Infrastructure Goals

Our major goals are the following:

  1. Create a library of optimization problems in different application areas in which one or several alternative models are presented with their derivation. In addition, each model has one or several instances that can serve to test various algorithms.
  2. Provide a mechanism for researchers and users to contribute towards the creation of the library of optimization problems.
  3. Provide a forum of discussion for algorithm developers and application users where alternative formulations can be discussed as well as performance and comparison  of algorithms.
  4. Provide information on MINLP tutorials and bibliography to disseminate this information.

Optimization is one of the strategic technologies for cyber infrastructure computational tools since this area deals with the selection of the "best" design or plan among many possible alternatives. The choice of the "best" alternative can mean, for instance, finding a transportation route that requires minimum time, finding the cheapest production path for a product, or finding a molecular configuration of a protein in the state of minimum energy. Many of the challenging application models require the use of discrete variables (mostly 0-1 variables) to represent logic choices, as well as the handling of nonlinearities in order to accurately predict the performance of physical, chemical, biological, financial or social systems. This optimization area is known as Mixed-Integer Nonlinear Programming (MINLP); mixed-integer because of the discrete and continuous variables, nonlinear because of the need of handling nonlinear models. It is the most general tool for addressing deterministic optimization models. Problems in practice that lead to MINLP models include engineering design and synthesis of manufacturing systems, planning, scheduling and control of production systems, design of molecular structures, X-ray crystallography, design of metabolic pathways, protein design, finance and agricultural economics , just to mention a few. We also consider in this cyber infrastructure site as particular cases Mixed-Integer Linear Programming (MILP) models and pure Nonlinear Programs (NLP), which can be regarded as MINLP models with linear objective function and linear constraints in the first case and with only continuous variables in the second case. Furthermore, we also consider as an alternative representation to MINLP problems, Generalized Disjunctive Programming (GDP), which involves boolean and continuous variables in algebraic constraints, disjunctions and logic propositions. GDP problems can be both linear and nonlinear.

While MINLP optimization can be applied to a very wide class of problems, it represents one of the most challenging optimization problems. On the combinatorial side, MINLP are known to be "NP hard" problems, meaning that in the worst case these models require solution times that scale exponentially with problem size. On the side of nonlinearities, many MINLP models are nonconvex, which means that in the continuous space they may give rise to many local solutions. (Note that even convex problems might be very challenging when integer variables are present.) Hence, finding the global solution of large-scale MINLP models (e.g. above 1,000 variables) in reasonable computational times (a few hours) is a major challenge, and currently a largely unsolved problem.

This cyber infrastructure site on MINLP is aimed at the optimization community that is increasingly interested in the solution and application of large-scale MINLP problems. This community involves academics and people from industry, and is highly multidisciplinary. It involves operations researchers, industrial, chemical and mechanical engineers, economists, chemists and biologists. This community, however, is largely disconnected, especially between algorithm developers and application domain researchers. Thus, our goal with this cybersite has been to develop a virtual collaboration environment that on the one hand can support the application of new algorithms and software, and on the other hand can make available these tools to applications researchers who are not specialists in the optimization field, but who would like to benefit from the use of advanced MINLP tools.