The IPOPT Interface to CAPE-OPEN
Yi-dong
Lang and Lorenz T. Biegler
Department of Chemical Engineering
June, 2005
Abstract
Computer aided
decision making often requires the solution of optimization problems to ensure
systematic improvement of objectives. The most general form of this
optimization problem is MINLP (Mixed Integer Nonlinear Programming), while an
important specific case is NLP (Nonlinear Programming). Efficient and effective
solvers are essential for solution of optimization problems. IPOPT is a recently
developed and well-tested advanced NLP solver. Moreover, CAPE-OPEN recently issued
a standard definition of “what should be
done” to interface MINLP or NLP models to solvers. It is expected that
prospective commercial vendors will offer CAPE-OPEN compliant modeling systems
to implement “how to do it”. This
report details the interface that makes IPOPT CAPE-OPEN compliant. That is,
IPOPT can now obtain all required information from any CAPE-OPEN compliant
MINLP modeling system, solve the problem iteratively and find the optimal
solution. As a result, the CAPE-OPEN community can take advantage of IPOPT to solve
its own optimization models easier and faster.
In this report we
briefly describe the IPOPT algorithm and focus on the need for calculation of
exact first and second derivatives through the CAPE-OPEN standard. This is a
key point to fully exploit the performance of IPOPT. Moreover, IPOPT is well
encapsulated and has only two interface ports. One connects to MINLPSystem
created by MINLPSolverManager. Another connects to the MINLP modeling system.
Therefore, as noted in the report, it is relatively easy to make IPOPT
CAPE-OPEN compliant. Finally, to demonstrate CO compliance, the CO-Tester is
used as a pseudo MINLP modeling system and the wrapper from CO-LaN makes the
demonstration straightforward. It is shown that IPOPT successfully solves an
NLP problem formulated with the GUI in the CO-Tester, by communicating
iteratively with the pseudo MINLP modeling system in the CO-Tester.
We hope the
information presented here for wrapping IPOPT within CAPE-OPEN is also useful
as a reference for other groups that would like to implement similar tasks with
other software packages. Also, we note that while this work is based on MS COM
as middleware and the CO-Tester as MINLP vendor, IPOPT remains CAPE-OPEN
compliant as long as the methods in IPOPT interface obtain the required
information from an MINLP vendor with either MS COM or CORBA as middleware.
Introduction
One of the CAPE-OPEN
standards for MINLP is the Optimization Interface issued by CO-LaN in August
2003.
The interface
defines ICapeMINLP for problem formulation. ICapeMINLP contains thirty two
methods for defining an MINLP or MILP problem. A generic MINLP can be expressed
as:
[MINLP]
where 
, 
and 
, 
and 
. An important special case of MINLP is that of nonlinear
programming (NLP). In this case, the
integer space is empty and integer variables y disappear from the formulation. A typical formulation of the NLP
is given by:
[NLP0]
The software tool
to optimize the problem [NLP0] and obtain the optimal solution x = x* is
termed the NLP solver. IPOPT is just that kind of solver. The main
characteristic of IPOPT is its ability to solve large-scale NLP problems
efficiently and effectively; it has been tested extensively at CMU and by numerous
outside investigators.
IPOPT is an NLP solver that applies a 
,
, sL, sU
≥ 0,
) it reformulates [NLP0] to the form:
[NLP]
By converting the
bounds into barrier terms in the objective function of [NLP], it transforms the
problem to an equality constrained NLP without bounds, as follows:
[NLP1]
s.t.
c(z) = 0
The KKT system of
[NLP1] is a set of nonlinear equations solved using
[KKT]
Here l is the vector of Lagrange multipliers, 
and Sk is a diagonal
matrix representing the barrier term. Global convergence is guaranteed using a
novel filter based line search and a number of safeguards are implemented in
IPOPT to make it efficient and reliable. More information on the algorithm can
be found in Wächter and Biegler (2004).
The IPOPT NLP
solver requires necessary information at iteration k in order to solve [KKT], generate search directions and proceed
toward the optimum solution. In particular, values of g(xk) and f(xk), along with their first and second derivatives, must be given by some means. To link to IPOPT, we can treat it as
a black box with two ports or interfaces for input and output (these interfaces
are conceptually different from the interface in COM). To solve the NLP problem
and obtain its optimal solution, we must offer required information for the black
box shown in Figure 1.
Figure 1. Information flows with
IPOPT
There are two ways
to supply to IPOPT the necessary information from the model. One is the conventional
method, writing the model as a subroutine in FORTRAN or a function in C++. The
other is using a modeling system supplied by commercial vendors, such as AMPL,
AIMMS, GAMS, etc.
With the CAPE-OPEN
protocol we can extend this feature. By CAPE-OPEN compliance we assume that
there are CAPE-OPEN compliant models, and IPOPT has functionality to
communicate with them. However, as of this writing we are not aware of any
available commercial CAPE-OPEN compliant modeling systems with MS COM as
middleware.[1]Instead
we use a facility in the CO-Tester to demonstrate that IPOPT has CAPE-OPEN
compliance. The CO-Tester checks the basic conformity with CAPE-OPEN standards
of component implementation; this is the MINLP interface defined in the CO standards.
The CO-Tester acts as a basic simulation environment where software components
can be plugged in. It has been designed to automatically carry out a number of
testing scenarios.
In the CO-Tester
there is a pseudo MINLP modeling system with interface ICapeMINLP and thirty
two methods defined in CAPE-OPEN standard. Clearly, if IPOPT can pass all the
tests in the CO-Tester, there should be no problem to cooperate with any CAPE-OPEN
compliant modeling system to solve large-scale NLP problems, either in academic
or industrial areas.
As shown in
Figure 1, implementation of communication between IPOPT and MINLP begins by
getting values for the initial parameters. During the iterative computations we
further obtain processing information after feeding data to the model object. We
discuss this next in detail.
Connect IPOPT to CAPE-OPEN MINLP
interface
The most recent
version of IPOPT was considered for this interface. Written in C++, it possesses
all features of Objective-Oriented Programs, including encapsulation. The body
of IPOPT communicates only through two ports as illustrated in Figure 2.
Figure 2. IPOPT with two Ports
Port I:
A function, named Cape_Ipopt(ICapeMINLP *pMinlp), is
called by the method ICapeMINLPSystem::solve( ) in COM
class with an interface ICapeMINLPSystem.
The function
first creates an object of an interface class, named CCapeTNLP(ICapeMINLP *pMinlp),
and then creates an object of IPOPT with the pointer of created object CCaperTNLP.
Port II:
Interface Class named CCapeTNLP(ICapeMINLP *pMinlp) is the
main interface for IPOPT to communicate with ICapeMINLP. When created by Port I
with MINLP pointer, IPOPT has the ability to communicate with the MINLP interface
and knows where to obtain its required information.
Thanks to the CAPE-OPEN
MINLP standard, the numerical solver is easy to make CO compliant. The relationship
of IPOPT to the MINLP interface is shown in Figures 2 and 3. A COM class
MINLPSolverManager creates an object of another COM class MINLPSystem and passes
a pointer of the created object ICapeMINLP to MINLPSystem. In MINLPSytem there
is a member method solve( ). It is this method that makes MINLP open to wrap
available solvers. We use the method MINLPSystem::solve() to connect IPOPT, through
Port I, to the function Cape_Ipopt( ICapeMINLP * pMinlp) and
thus obtain the pointer ICapeMINLP. This
pointer then is passed to the object class in IPOPT, CCapeTNLP when it is created.
In this way, IPOPT can communicate with CCapeTNLP through Port II to send its
intermediate results to the MINLP interface and obtain its required information
from MINLP during its iterative computations.
Figure 3. IPOPT in MINLP
Components
Figure 4. IPOPT connects into MINLP
Interfaces
Processing
In the next
section we will describe how the information streams flow across the COM
components and how IPOPT communicates with the MINLP environment.
Preprocessing
Since IPOPT uses a
dynamic memory allocation strategy, it reserves some memory space for solving the
optimization problem at hand. Therefore a preprocessing procedure is required
to obtain the following information or parameters before IPOPT starts its
iterations:
1.
Size information of the model :
·
Number of variables, n,
·
Number of constraint equations, m,
·
Number of non-zero terms in Jacobian of constraint, nnz_jac,
·
Number of non-zero terms in upper(or lower) triangle of the Hessian matrix,
nnz_h.
2.
The bounds information
·
Lower bounds of related variables, x_l,
·
Upper bounds of related variables, x_u,
·
Lower bounds of related constraints, g_l,
·
Upper bounds of related constraints, g_u.
It is worth noting that for any specific variable or
constraint, it may have one of two bounds, both bounds, or no bounds at all.
3.
Starting point, x0
4.
Structures of Jacobian and Hessian
IPOPT takes advantages of sparsity in the Jacobian
and Hessian matrices; to save memory the program stores only nonzero terms in
the sparse matrix. Therefore it must explicitly identify all nonzero terms in
the matrix with the following structure information obtained from the modeling
system for the Jacobian or Hessian:
·
Ordering the nonzero terms,
·
Row index of the nonzero term position in the matrix,
·
Column index of the nonzero term position in the matrix.
Later when the values of nonzero terms fill in
the matrix, the only reference is
their order defined in the sparse data structure.
Iterative Computation
At each iteration,
with given x values, IPOPT requests the
following function values:
- Objective function
- Constraints
- Gradient of objective function with
respect to all x
- All nonzero terms in Jacobian
- All nonzero terms in Hessian
In order to calculate
the Hessian, IPOPT calculates multipliers for each constraint and a factor for
the objective function. Before getting Hessian values, IPOPT must first send
these multipliers to the modeling system.
After a valid new
point is found, IPOPT then sends the x
values at the new point to the modeling system and is ready for the next
iteration.
These iterations
continue until IPOPT decides the optimal solution is found and finally reports
the solution.
CAPE-OPEN
compliance
We developed an
interface for IPOPT to communicate with CAPE-OPEN compliant MINLP modeling
systems with an interface ICapeMINLP. The developed interface allows IPOPT to obtain
all required information from the modeling system and send its resulting values
through the ICapeMINLP interface. Hence, IPOPT can be used among CAPE-OPEN
community as an NLP solver for large-scale problems.
Due to
encapsulation in IPOPT (using the C++ version), we use only two ports to
connect to the interface in MINLP interfaces. We now discuss how IPOPT becomes CAPE-OPEN
compliant.
In the constructor
of class CCapeTNLP, the program first collects size information by calling
GetMINLPSize
Since
GetMINLPSize does not offer the number of nonzeroes in the Hessian, it must
also call
GetMINLPHessianStructure
to get this
number. Then it calls GetMINLPStructure twice (for “LINEAR” and “NONLINEAR” terms,
respectively) for the structure of the Jacobian,
GetMINLPObjectiveFunctionType
For the objective
function (of type maximum or minimum), it calls
GetMINLPObjectiveFunctionDerivativeValues
with “LINEAR”
to get
coefficients of linear terms in the objective function, and it calls
GetMINLPConstraintDerivativeValues
with “LINEAR”
to get the coefficient
matrix of linear terms in the constraint equations.
By calling these
methods in ICapeMINLP, the class CCapeTNLP obtains the n, m, nnz_jac, nnz_h parameters for the structure of the Jacobian
and Hessian. In addition, coefficients of linear terms in the objective
function and the constraint equations are used to calculate values of the first
derivatives of the linear parts in objective and constraints within the class
itself, instead of by the model system. All this information is stored as private
variables in the class.
After collecting
all primary information, the member methods in class CCapeTNLP, derived from
basic class TNLP in IPOPT, implement preprocessing and communication for the
IPOPT iterations.
get_nlp_info( )
transfers model size, n, m, nnz_jac, nnz_h to IPOPT.
get_bounds_info( ) invokes
GetMINLPVariableBounds
GetMINLPConstraintBounds
to collect bounds
information
get_starting_point( ) assigns variable starting values for
IPOPT by calling
GetMINLPVariableValues
eval_f( )
calculates the linear part of the objective function based on variable values
and corresponding coefficients in the objective function. It then sends these
variable values out to get values of nonlinear terms by calling
SetMINLPVariableValues.
GetMINLPNonlinearObjectiveFunctionValue
Finally the linear and nonlinear terms are added together and multiplied
by the appropriate sign based on the type of objective function (1 for minimum
and -1 for maximum).
eval_grad_f( ) --- calculates gradient of the objective function. IPOPT
assumes a dense vector of the gradient of objective function while ICapeMINLP
provides only nonzero terms. Therefore this method resets the dense vector and then
fills it with the linear coefficients accordingly. It then includes the
nonlinear terms by calling
GetMINLPObjectiveFunctionDerivativeValues
with “NONLINEAR” parameter.
eval_g( ) --- calculates current values of
constraints. As in eval_f( ) two steps are needed for each constraint. First
linear parts of all constraints are obtained. Nonlinear parts are calculated
using:
SetMINLPVariableValues.
GetMINLPNonlinearConstraintValues
Finally linear
and nonlinear parts are added for each constraint.
eval_jac_g( ) ---- gets the Jacobian.
When IPOPT calls this method the first
time, it returns the structure of the Jacobian, i.e. only row and column
indices of nonzero terms in the Jacobian. Later, during the IPOPT iterations, it
only returns the values of these nonzero terms.
There are two
parts to the Jacobian. The linear part remains unchanged during solution and
consists of coefficients of linear terms in the constraints. This part is not
calculated. The nonlinear part is calculated according to the new values of x. The method sends out variable values
by
SetMINLPVariableValues.
and then obtains
the nonlinear part by
GetMINLPConstraintDerivativeValues
eval_h_lag( ) --- calculates the Hessian. As in
eval_jac_g() when IPOPT calls this method the first time, it returns the
structure of the Hessian, i.e. only row and column indices for the nonzero terms.
Later, during IPOPT iterations, it only returns the values of these nonzero
terms. The Hessian of the Lagrange function is calculated based on values of x as well as the multiplier
Therefore, this method sends new x
and new λ values by
SetMINLPVariableValues.
SetMINLPLagrangeMultipliers
And then we
obtain the Hessian through
GetMINLPHessianValues
finalize_solution( ) --- when IPOPT terminates successfully, it
feeds back the optimal solution by:
SetMINLPVariableValues.
Then the program
destroys all objects it has created and releases memory it occupied. Here, smart pointers take charge and return
to MINLPSystem::solve().
Remarks
1.
CAPE-OPEN
Compliance
In this report,
we have shown that IPOPT could easily be CO compliant based on MS COM and the CO-Tester
by taking advantage of previously developed results. IPOPT compliance with CO is
not limited by this choice. Vendor software that implements the methods in
MINLP interface defined in CAPE-OPEN, with either MS COM or CORBA as middleware
on the “Problem side”, should have no
problem with the IPOPT CAPE-OPEN interface on the “Solver side” .
2.
Linear and
nonlinear terms
IPOPT does not distinguish between linear and nonlinear terms in the objective
function and constraint equations, although the MINLP standard offers three
options: “LINEAR”, “NONLINEAR” and “BOTH” for some its member methods, and allows
user to select linear, nonlinear and union. For instance, in the CO-Tester, we
have an equation given by:
According to the CAPE-OPEN
MINLP standard, the first part corresponds to “LINEAR” option,
and the second
part to “NONLINEAR”
Only with the
option “BOTH” do we have the general nonlinear term, i.e.,
For x1: 
For x2: 
Since the implementations
of member methods in current CO-Tester are not completed yet for the NLP model;
we had to introduce the following restriction to formulate the problem with
this GUI, i.e.
It is worth
indicating that this restriction is only for the current version of the CO-Tester
along with the GUI for the test problem. It is not necessary for commercial
MINLP implementations.
3.
Safe Arrays
Communication
between IPOPT and MINLP is mainly done through data passing among COM
components. CSafeArray is used in this development to wrap Safe Array for sending
data to MINLP.
4.
MS .NET
2003
All of this work
is developed on MS Windows. The original code of GCOWrapper is developed in
Visual Studio 6.0 with ATL 3.0. Since the smart pointers in IPOPT had trouble
with C++ compiler 6.0, we used IDE .NET 2003 with ATL 7.0 instead.
This was built through: Select NEW project -> Visual C++ Project-> ATL Project ->
Application Setting -> no Attribute -> Executable(.exe)
5.
Source
Codes and Appendices
The IPOPT code
can be downloaded from the COIN-OR website and is freely available as open
source software under a Common Public License (CPL). This license also applies
to the source codes for interface Ports I and II, listed in Appendices A and B,
respectively. Appendix C presents screen shots of the CO-Tester GUI, while
Appendix D shows reports of the Basic, Function and Integration tests. Finally,
details of the Common Public License can be found on http://www.opensource.org/licenses/cpl.php.
Acknowledgements
We could not have
implemented this work without the source codes of the COTester offered by
Michel Pons in CO-LaN and the help from Antonio Espuna in UPC. The source codes of CO-Tester were very
helpful references during our development.
References
IPOPT web page, www.coin-or.org/Ipopt/
Open Interface Specification:
Optimization Interface, CO-LaN www.colan.org/Spec%2010/Optimisation%20Interface%20Specification.pdf (2003)
Wächter, A., and
L. T. Biegler, “On the Implementation of an Interior Point Filter Line Search
Algorithm for Large-Scale Nonlinear Programming,” Mathematical Programming, accepted for publication (2004)