<figure><img src="image_13.png" /><figcaption>Figure 4.4: Convex relaxation of $x^3$ by reformulation to bilinear product.</figcaption></figure>

As can be seen from Figure 4.4a, the convex relaxation (4.19)-(4.21) is generally similar to that of Section 4.4 (in that both the underestimator and the overestimator consist of a straight line joined to a curve), but not as tight. This is to be expected in view of theorem 4.4.1.

On the other hand, the convex relaxation (4.19)-(4.21) is slightly tighter than the linear relaxation of Section 4.5 in the sub-interval $[a, e]$ where $e$ is the point at which the curve on the right hand side of (4.20) intersects the tangent line on the right hand side of (4.18); and also in the sub-interval $[f, b]$ where $f$ is the point at which the curve on the left hand side of (4.20) intersects the tangent line on the left hand side of (4.18). However, the linear relaxation of Section 4.5 is tighter everywhere else.

## 4.6.2 Underestimation through $\alpha$ parameter

An alternative approach to deriving convex relaxations of general non-convex functions is the $\alpha$BB algorithm (see [13], [7]). In this case, the convex underestimator $\mathcal{L}_k(x)$ is given by $x^{2k+1} + \alpha_k(x-a)(x-b)$, where $\alpha_k$ is a positive constant that is sufficiently large to render the second derivative $d^2\mathcal{L}_k(x)/dx^2$ positive for all $x \in [a, b]$. Similarly, the concave overestimator $\mathcal{U}_k(x)$ is given by $x^{2k+1} - \beta_k(x-a)(x-b)$ where $\beta_k$ is sufficiently large to render $d^2\mathcal{U}_k(x)/dx^2$ negative
for all $x \in [a, b]$. It can easily be shown that the above conditions are satisfied by the values:

$$ \alpha_k = k(2k+1)|a|^{2k-1} \quad (4.22) $$

$$ \beta_k = k(2k+1)b^{2k-1}. \quad (4.23) $$

The convex relaxation for the case of $k = 1$ (i.e. the function $x^3$) obtained using the above approach in the domain $x \in [-1, +1]$ is shown in Figure 4.5. It is evident that it is looser than those shown in figs. 4.1 and 4.3.

<figure><img src="image_14.png" /><figcaption>Figure 4.5: Convex relaxation of $x^3$ by the $\alpha$ method.</figcaption></figure>

## 4.7 Computational results

In order to illustrate the difference between two of the relaxations described above for $x^{2k+1}$ (those of Section 4.5 and 4.6.1), we solved the problem:

$$ \left. \begin{array}{ll} \min_{x,y} & x - y \\ y & = x^{2k+1} \\ -1 & \le x, y \le 1 \end{array} \right\} \quad (4.24) $$

to global optimality using the spatial Branch-and-Bound algorithm described in [116] within the *ooOPS* implementation [73], both with the tight linear relaxation (equation (4.17)-(4.18))
<figure><img src="image_15.png" /><figcaption>Figure 4.6: Graphical description of simple test problem for $k = 1$ (in 2D).</figcaption></figure>

and with the alternative convex relaxation (equation (4.19)-(4.21)). Table 4.3 lists the number of iterations taken by the algorithm when $k$ varies. The first column lists the results relative to the novel convex relaxation (Section 4.5), the second those relative to the alternative convex relaxation (Section 4.6.1).

The results clearly substantiate the theory: the novel convex relaxation gives better performance in comparison to the alternative relaxation based on reformulation to bilinear product. In the case of $x^3$, we can see why this happens in figures 4.6 and 4.7. The direction of minimization of the objective function $x - y$ is such that the minimum over the original feasible region is very near the minimum over the novel convex relaxation. However, the minimum over the alternative convex relaxation is further away. Hence the performance gain.

## 4.8 Conclusion

We have proposed a convex envelope for monomials of odd degree when the range of the defining variable includes zero, i.e. when they are piecewise convex and concave. We have then compared it with other possible relaxations (based on reformulation to bilinear product and on
<figure><img src="image_16.png" /><figcaption>Figure 4.7: Graphical description of simple test problem for $k = 1$ (in 3D).</figcaption></figure>

$\alpha$ parameter under- and overestimators) and shown that the former performs better than the latter when tested in a Branch-and-Bound algorithm.
<table><caption>Table 4.3: Numerical results from the simple test problem.</caption><thead><tr><th>k</th><th>Iterations<br>(novel rel.)</th><th>Iterations<br>(alternative rel.)</th><th>k</th><th>Iterations<br>(novel rel.)</th><th>Iterations<br>(alternative rel.)</th></tr></thead><tbody><tr><td>1</td><td>17</td><td>21</td><td>8</td><td>19</td><td>27</td></tr><tr><td>2</td><td>17</td><td>31</td><td>9</td><td>21</td><td>27</td></tr><tr><td>3</td><td>17</td><td>27</td><td>10</td><td>7</td><td>25</td></tr><tr><td>4</td><td>17</td><td>29</td><td>11</td><td>7</td><td>25</td></tr><tr><td>5</td><td>19</td><td>31</td><td>12</td><td>7</td><td>25</td></tr><tr><td>6</td><td>19</td><td>27</td><td>13</td><td>7</td><td>25</td></tr><tr><td>7</td><td>19</td><td>27</td><td>14</td><td>7</td><td>23</td></tr></tbody></table>
# Chapter 5

## Spatial Branch-and-Bound algorithm with
symbolic reformulation

The previous two chapters considered issues relating to the (re-)formulation and tight convexification of NLP problems in the context of spatial branch-and-bound (sBB) algorithms for global optimization. We now turn our attention to the sBB algorithm itself and its computer implementation in a form that can be used as a component within larger software systems such as process modelling tools. An important consideration in this context is the large amount of both numerical and symbolic information required by sBB algorithms.

We start with an overview of the common structure of most sBB algorithms reported in the literature. We then provide a more detailed description of Smith's sBB algorithm [114, 116] which forms the basis for our work and propose some algorithmic improvements to improve its performance. Lastly, we describe *ooOPS* (object-oriented OPtimization System), a general software framework for defining and solving optimization problems, and the implementation of our algorithm within this framework.
## 5.1 Overview of spatial Branch-and-Bound algorithms

The spatial Branch-and-Bound algorithm described in this chapter solves NLPs in the following form:

$$ \left. \begin{array}{ll} \min_{x} & f(x) \\ \alpha & \leq g(x) \leq \beta \\ a & \leq x \leq b \end{array} \right\} \qquad (5.1) $$

where $x \in \mathbb{R}^n$ are the (continuous) problem variables, $f: \mathbb{R}^n \to \mathbb{R}$ is the objective function (which may be nonconvex), $g: \mathbb{R}^n \to \mathbb{R}^m$ are a vector of generally nonconvex functions, $\alpha, \beta$ are the lower and upper bounds of the constraints<fnref n="1" />, and $a, b$ are the lower and upper bounds of the variables.

The general mathematical structure and properties of sBB algorithms aimed at solving non-convex NLPs were studied in Section 1.4, and their convergence proofs are similar to that of theorem 1.4.1. The Branch-and-Reduce method [99] is an sBB algorithm with strong emphasis on variable range reduction. The $\alpha$BB algorithm [13, 2, 6, 5] is an sBB whose main feature is that the convex underestimators for general twice-differentiable nonconvex terms can be constructed automatically. The reduced-space Branch-and-Bound algorithm [32] identifies a priori a reduced set of branching variables so that less branching is required. The generalized Branch-and-Cut framework proposed in [61] derived cuts from violated constraints in three sub-problems related to the original problem.

Most sBB algorithms for the global optimization of nonconvex NLPs conform to a general framework of the following form:

1. (Initialization) Initialize a list of regions to a single region comprising the entire set of variable ranges. Set the convergence tolerance $\epsilon$ and the best objective function value $U := \infty$. Optionally, perform optimization-based bounds tightening.

2. (Choice of Region) If the list of regions is empty, terminate the algorithm with solution $U$. Otherwise, choose a region (the “current region”) from the list. Delete this region from the list. Optionally, perform feasibility-based bounds tightening on this region.

3. (Lower Bound) Generate a convex relaxation of the original problem in the selected region and solve it to obtain an underestimation $l$ of the objective function. If $l > U$ or the relaxed problem is infeasible, go back to step 2.

<footnote n="1">¹Equality constraints can be specified by setting $\alpha = \beta$.</footnote>
4. (Upper Bound) Attempt to solve the original (generally nonconvex) problem in the selected region to obtain a (locally optimal) objective function value $u$. If this fails, set $u := +\infty$.

5. (Pruning) If $U > u$, set $U := u$. Delete all regions in the list that have lower bounds bigger than $U$ as they cannot possibly contain the global minimum.

6. (Check Region) If $u - l \le \varepsilon$, accept $u$ as the global minimum for this region and return to step 2. Otherwise, we may not yet have located the region global minimum, so we proceed to the next step.

7. (Branching) Apply a branching rule to the current region to split it into sub-regions. Add these to the list of regions, assigning to them an (initial) lower bound of $l$. Go back to step 2.

## 5.2 Smith's sBB algorithm

The most outstanding feature of Smith's sBB algorithm is the automatic construction of the convex relaxation via symbolic reformulation [114, 116]. This involves identifying all the non-convex terms in the problem and replacing them with the respective convex relaxations. The algorithm that carries out this task is symbolic in nature as it has to recognize the nonconvex operators in any given function.

Smith assumes that the NLP solved by his algorithm is of the form:

$$ \left. \begin{array}{ll} \min_x & f(x) \\ \bar{g}(x) & = \quad 0 \\ a & \le x \le b \end{array} \right\} \qquad (5.2) $$

introducing slack variables to convert any inequalities to the equality constraints $\bar{g}(x) = 0$ above.

Below, we consider some of the key steps of the algorithm in more detail.

### 5.2.1 Choice of region (step 2)

The region selection at step 2 follows the simple policy of choosing the region in the list with the lowest lower objective function bound as the one which is most promising for further con-
sideration.

### 5.2.2 Convex relaxation (step 3)

The convex relaxation solved at step 3 of the algorithm aims to find a guaranteed lower bound to the objective function value. In most global optimization algorithms, convex relaxations are obtained for problems in special (e.g. factorable) forms. In Smith's sBB, the convex relaxation is calculated automatically for a problem in the most generic form (1.1) provided this is available in closed analytic form, which allows symbolic manipulation to be applied to it.

The convex relaxation is built in two stages: first the problem is reduced to a *standard form* where nonlinear terms of the same type are collected in lists; then each nonlinear term is replaced by the corresponding convex under- and overestimators. The standard form also provides ways to simplify branch point calculation, branch variable choice and feasibility based bounds tightening.

#### 5.2.2.1 Reformulation to standard form

This is the first stage toward the construction of the convex relaxation of the original problem via symbolic manipulation of the variables and constraints. In this form, the problem nonlinearities are isolated from the rest of the problem and thus are easy to tackle by symbolic and numerical procedures.

Smith defined the following standard form:

$$ \min x_{obj} \qquad (5.3) $$

$$ l \le Ax \le u \qquad (5.4) $$

$$ x_k = x_i x_j \quad \forall (i, j, k) \in \mathcal{M} \qquad (5.5) $$

$$ x_k = \frac{x_i}{x_j} \quad \forall (i, j, k) \in \mathcal{D} \qquad (5.6) $$

$$ x_k = x_i^\nu \quad \forall (i, k, \nu) \in \mathcal{P} \qquad (5.7) $$

$$ x_k = f_\mu(x_i) \quad \forall (i, k, \mu) \in \mathcal{U} \qquad (5.8) $$

$$ x^L \le x \le x^U \qquad (5.9) $$

where $x = (x_1, \dots, x_n)$ are the problem variables, $A$ is a constant, usually sparse, matrix, $l, u$ are the linear constraint bounds, and $x^L, x^U$ are the variable bounds. Constraints (5.5)–
(5.8), called the *defining constraints*, include all the problem nonlinearities: $\mathcal{M}, \mathcal{D}$ are sets of triplets of variable indices which define bilinear and linear fractional terms respectively. $\mathcal{P}$ is a set of triplets defining power terms; each triplet comprises two variable indices $i, k$ and the corresponding power exponent $\nu \in \mathbb{R}$. $\mathcal{U}$ is a set of triplets which define terms involving univariate functions $f_\mu$; each triplet comprises two variable indices $i, k$ and a third index $\mu$ that identifies the type of the univariate function being applied (e.g. $\exp(.)$, $\ln(.)$).

Each of the constraints (5.5)-(5.8) has one of the forms:

$$ \textit{added variable} = \textit{operand (binary operator) operand} $$

$$ \textit{added variable} = (\textit{unary operator}) \textit{operand} $$

where operand is an original or an “added” variable i.e. one added to the original set of variables by the standardization procedure.

In the interests of simplicity, the objective function is replaced by the added variable $x_{obj}$, and a constraint of the form:

$$ x_{obj} = \textit{objective function} $$

is added to the linear constraints.

An efficient algorithm for reducing an NLP to standard form has been described in detail in [114, 116]. It works by recursively tackling nonlinear terms in the problem and forming linear and defining constraints as it goes along, always aiming at introducing the minimal number of new variables.

### 5.2.2.2 Convexification

This is the second stage of the process where the actual convex relaxation of the original problem within the current region $[x^L, x^U]$ is built. The algorithm for convexification is entirely symbolic (as opposed to numeric) and hence performs very efficiently even in the presence of very complicated mathematical expressions.

Having reduced a problem to standard form, we replace every nonconvex term with a convex envelope consisting of convex over- and underestimating inequality constraints. The rules we follow to construct over- and underestimators are as follows:
1. $x_i = x_j x_k$ is replaced by four linear inequalities (McCormick's envelopes, [80]):

$$x_i \geq x_j^L x_k + x_k^L x_j - x_j^L x_k^L \quad (5.10)$$

$$x_i \geq x_j^U x_k + x_k^U x_j - x_j^U x_k^U \quad (5.11)$$

$$x_i \leq x_j^L x_k + x_k^L x_j - x_j^L x_k^L \quad (5.12)$$

$$x_i \leq x_j^U x_k + x_k^U x_j - x_j^U x_k^U \quad (5.13)$$

2. $x_i = x_j/x_k$ is reformulated to $x_i x_k = x_j$ and the convexification rules for bilinear terms (5.10)-(5.13) are applied.

3. $x_i = f_\mu(x_j)$ where $f_\mu$ is concave univariate is replaced by two inequalities: the function itself and the secant:

$$x_i \leq f_\mu(x_j) \quad (5.14)$$

$$x_i \geq f_\mu(x_j^L) + \frac{f_\mu(x_j^U) - f_\mu(x_j^L)}{x_j^U - x_j^L} (x_j - x_j^L) \quad (5.15)$$

4. $x_i = f_\mu(x_j)$ where $f_\mu$ is convex univariate is replaced by:

$$x_i \leq f_\mu(x_j^L) + \frac{f_\mu(x_j^U) - f_\mu(x_j^L)}{x_j^U - x_j^L} (x_j - x_j^L) \quad (5.16)$$

$$x_i \geq f_\mu(x_j) \quad (5.17)$$

5. $x_i = x_j^\nu$ where $0 < \nu < 1$ is treated as a concave univariate function in the manner described in point 3 above.

6. $x_i = x_j^{2m}$ for any $m \in \mathbb{N}$ is treated as a convex univariate function in the manner described in point 4 above.

7. $x_i = x_j^{2m+1}$ for any $m \in \mathbb{N}$ can be convex, concave, or piecewise convex and concave with a turning point at 0. If the range of $x_j$ does not include 0, the function is convex or concave and falls into a category described above. Smith does not specify a convex envelope for the case where the range includes 0; however, it is desirable to use the linear convex and concave relaxations described in Chapter 4.

### 5.2.3 Branching (step 7)

There are many branching strategies [31] available for use in spatial Branch-and-Bound algorithms. Generally, branching involves two steps, namely determining the point (i.e. set of
variable values) on which to branch, and finding the variable whose domain is to be sub-divided by the branching operation. Smith uses the solution of the upper bounding problem (step 4) as the branching point, if such a solution is found; otherwise the solution of the lower bounding problem (step 3) is used. He then identifies the nonlinear (nonconvex) term with the largest error with respect to its convex relaxation. The branch variable is chosen as the variable whose value at the branching point is nearest to the midpoint of its range.

### 5.2.4 Bounds tightening

These procedures are in steps 1 and 2 of the algorithm structure outlined in Section 5.1. They are optional in the sense that the algorithm will, in principle, converge even without them. Depending on how computationally expensive and how effective these procedures are, in some cases convergence might actually be faster if these optional steps are not performed. In the great majority of cases, however, the bounds tightening steps are essential to achieve fast convergence.

Two major bounds tightening schemes have been proposed in the literature: optimization-based and feasibility-based.

#### 5.2.4.1 Optimization-based bounds tightening (step 1)

This is a computationally expensive procedure which involves solving at least $2n$ convex NLPs (or LPs if a linear relaxation is employed) where $n$ is the number of problem variables. Let $\alpha \le \bar{g}(x) \le \beta$ be the set of constraints in the relaxed (convex) problem. The following procedure will construct sequences $\{x^L\}^{[k]}, \{x^U\}^{[k]}$ of lower and upper bounds which converge to bounds that are at least as tight as, and probably tighter than $x^L, x^U$.

1. Set $\{x^L\}^{[0]} \leftarrow x^L, \{x^U\}^{[0]} \leftarrow x^U, k \leftarrow 0$.

2. Repeat

$$ \{x_i^L\}^{[k]} \leftarrow \min\{x_i \mid \alpha \le \bar{g}(x) \le \beta \land \{x^L\}^{[k-1]} \le x \le \{x^U\}^{[k-1]}\}, \quad \forall i \le n; $$

$$ \{x_i^U\}^{[k]} \leftarrow \max\{x_i \mid \alpha \le \bar{g}(x) \le \beta \land \{x^L\}^{[k-1]} \le x \le \{x^U\}^{[k-1]}\}, \quad \forall i \le n; $$

$$ k \leftarrow k + 1. $$

until $\{x^L\}^{[k]} = \{x^L\}^{[k-1]}$ and $\{x^U\}^{[k]} = \{x^U\}^{[k-1]}$:
Because of the associated cost, this type of tightening is normally performed only once, at the first step of the algorithm.

### 5.2.4.2 Feasibility-based bounds tightening (step 2)

This procedure is computationally cheaper than the one described above, and as such it can be applied at each and every region considered by the algorithm. Variable bounds are tightened by using the problem constraints to calculate extremal values attainable by the variables. This is done by isolating a variable on the left hand side of a constraint and evaluating the right hand side extremal values by means of interval arithmetic.

Feasibility-based bounds tightening is trivially easy for the case of linear constraints. Given linear constraints in the form $l \le Ax \le b$ where $A = (a_{ij})$, it can be shown that, for all $1 \le j \le n$:

$$x_j \in \left[ \max \left( x_j^L, \min_i \left( \frac{1}{a_{ij}} \left( l_i - \sum_{k \neq j} \max(a_{ik}x_k^L, a_{ik}x_k^U) \right) \right) \right), \min \left( x_j^U, \max_i \left( \frac{1}{a_{ij}} \left( u_i - \sum_{k \neq j} \min(a_{ik}x_k^L, a_{ik}x_k^U) \right) \right) \right] \quad \text{if } a_{ij} > 0$$

$$x_j \in \left[ \max \left( x_j^L, \min_i \left( \frac{1}{a_{ij}} \left( l_i - \sum_{k \neq j} \max(a_{ik}x_k^L, a_{ik}x_k^U) \right) \right) \right), \min \left( x_j^U, \max_i \left( \frac{1}{a_{ij}} \left( u_i - \sum_{k \neq j} \max(a_{ik}x_k^L, a_{ik}x_k^U) \right) \right) \right] \quad \text{if } a_{ij} < 0.$$

As pointed out by Smith ([114], p.202), feasibility-based bounds tightening can also be carried out for certain types of nonlinear constraints.

## 5.3 Improvements to Smith's sBB algorithm

In this section we present some simple improvements to Smith's work based on observations about the theory of sBB. All of these leave the convergence properties of the algorithm intact but reduce its cost.

### 5.3.1 Avoiding the introduction of slack variables

The computational efficiency of optimization codes is adversely affected by the size of the problem in terms of the number of variables. It therefore makes sense to try to reduce this
number, either by dimensionality arguments (see Section 2.2.2) or by reducing the number of
intermediate variables generated by the symbolic manipulation procedures. Here, we use the
latter approach.

One of the prerequisites of the standardization procedure stated by Smith is that the original
problem consists only of equality constraints of the form $g(x) = 0$ (see [114], p.190). All the
inequality constraints should therefore be transformed into equality constraints via the introduc-
tion of slack variables as described in Section 5.2.2.1 (also see section 2.2.1). This produces a
number of new problem variables equal to the number of inequality constraints. For cases where
all or most of the constraints are inequalities, the additional computational overhead resulting
from this step is substantial. If one takes into account the fact that the most generic problem
form 5.1 has two inequalities for each constraint expression (i.e. each constraint has a lower
and an upper bound, as in $-1 \le x + y \le 3$, for example), the actual number of slack variables
is doubled.

Fortunately, it turns out that slack variables are not needed for the standardization process.
More precisely, the standardization process only acts on the expression $g(x)$ within a constraint
of the form $l \le g(x) \le u$; at no point is the fact that $g(x) = 0$ used. Thus, the standardization
can be applied directly to inequality constraints, so that slack variables are not needed.

5.3.2 Avoiding unnecessary local optimizations

The most computationally expensive steps in the sBB algorithms are typically the calls to the
local optimization procedures to find lower and upper bounds to the problem at hand. This
normally involves the numerical solution of a general non-convex NLP, which can be relatively
expensive. If a good lower or upper bound can be found for a region without resorting to the
local optimization procedure, then it should be used without question.

The two methods described below should at least halve the number of upper bounding prob-
lems that are solved during the sBB algorithm. Note that a distinction is made between the
variables that were present in the original NLP (“original variables”) and those that were added
by the standardization procedure (“added variables”, cf. section 5.2.2.1).
### 5.3.2.1 Branching on added variables

Suppose that in the sBB algorithm an added variable $w$ is chosen as the branch variable. The current region is then partitioned into two sub-regions along the $w$ axis, the convex relaxations are modified to take the new variable ranges into account, and lower bounds are found for each sub-region. The upper bounds, however, are found by solving the original problem which is not dependent on the added variables. Thus the same exact original problem is solved at least three times in the course of the algorithm (i.e. once for the original region and once for each of its two sub-regions).

The obvious solution is for the algorithm to record the objective function upper bounds in each region. Whenever the branch variable is an added variable, avoid solving the original (upper bounding) problem and use the stored values instead.

### 5.3.2.2 Branching on original variables

Even when the branching occurs on an original problem variable, there are some considerations that help avoid solving local optimization problems unnecessarily. Suppose that the original variable $x$ is selected for branching in a certain region. Then its range $[x^L, x^U]$ is partitioned into $[x^L, x']$ and $[x', x^U]$. If the solution of the upper bounding problem in $[x^L, x^U]$ is $x^*$, and $x^* \in [x^L, x']$, then it is unnecessary to solve the upper bounding problem again in the sub-region $[x^L, x']$ as an upper bound is already available at $x^*$. Of course, the upper bounding problem still needs to be solved for the other subregion $[x', x^U]$ (see Fig. 5.1).

## 5.4 The *ooOPS* software framework for optimization

Any computer implementation of general-purpose spatial Branch-and-Bound algorithms for global optimization requires a large amount of information on the problem being solved. This includes:

* numerical information of the type required by local optimization solvers, e.g. values of the objective function and the residuals of the constraints for given values of the problem variables;
<figure><img src="image_17.png" /><figcaption>Figure 5.1: If the locally optimal solution in $[x^L, x^U]$ has already been determined to be at $x^*$, solving in $[x^L, x']$ is unnecessary.</figcaption></figure>

* structural information, e.g. regarding the sparsity pattern of the constraints; this is essential not only for improving the code efficiency (a feature that is also shared with local optimization codes), but also in implementing advanced techniques such as the model reformulation algorithm of chapter 3;

* symbolic information on the objective function and constraints, needed for implementing general reformulation and/or convexification techniques.

Most implementations of sBB-type algorithms in existence today have been either stand-alone software codes (e.g. the αBB system [4, 5]) with their own language for defining optimization problems, or have been embedded within existing modelling tools which provide them with the necessary information; for example, Smith's [114] code was embedded in the gPROMS modelling tool [30] while the BARON code [102] has recently been made available within GAMS [22]. Whilst these developments are undeniably useful from the immediate practical point of view, the wider dissemination of global optimization technology requires a different approach which allows the software to be directly embedded within larger software systems such as mathematical modelling tools, domain-specific optimization codes (e.g. for pooling and blending) and so on.

The above considerations provided the motivation for the development of the *ooOPS* (object-oriented Optimization System) system in the context of the work described in this thesis. *ooOPS* is a comprehensive library of callable procedures for the definition, manipulation and
solution of large, sparse nonlinear programming problems<fnref n="2" />.

*ooOPS* is completely coded in C++ [125], [103]. The C++ language is object-oriented but low-level enough to leave memory management to the programmer; C++ compilers are very efficient at optimizing the code and very portable across different architectures.

*ooOPS* is described in detail in Appendix A of this thesis. The rest of this chapter provides an overview of its design and usage.

### 5.4.1 Main features of *ooOPS*

Rather than being a stand-alone code, *ooOPS* is designed to provide a number of high-level services to a client software code (e.g. written in C++, C or FORTRAN) via an Application Programming Interface (API).

A complete description of *ooOPS* is provided in Appendix A of this thesis. Its main features include the following:

1. *ooOPS* allows its client codes to construct and, if necessary, subsequently modify large-scale NLPs involving large sets of variables and linear and nonlinear constraints.

2. The construction of complex problems is facilitated by recognizing that, in most practical applications, variables and constraints can be categorised into relatively small numbers of sets which can be defined generically. Thus, *ooOPS* allows variables and constraints to be defined in a “structured” fashion as multi-dimensional arrays with an arbitrary number of dimensions.

3. The construction of an NLP in *ooOPS* is done in a symbolic manner. Thus, each non-linear expression occurring in the objective function and/or the constraints is built by the client issuing a sequence of calls (i.e. on a term-by-term, factor-by-factor basis etc.). Consequently, *ooOPS* is fully aware at all times of the symbolic form of any NLP within it and can supply this information to its clients.

4. In order to facilitate the operation of numerical optimization solvers within the *ooOPS* framework, *ooOPS* automatically derives and makes available to its clients a “flat” form

<footnote n="2">²In fact, *ooOPS* has been designed and implemented to deal with mixed integer linear and nonlinear optimization problems. However, for the purposes of this chapter, we will refer only to its NLP capabilities.</footnote>
of any NLP constructed in terms of structured variables and constraints. In this flat form,
all variables and constraints are collected in two one-dimensional vectors (arrays).

5. The standard form (5.3) of an NLP is required by some sBB algorithms, such as the one by Smith which forms the basis of our work. It may also be useful in other contexts as it allows any NLP involving arbitrarily complex objective functions and/or constraints to be represented in terms of simple data structures, namely (cf. Section 5.2.2.1):

* the index *obj* of the objective function in the vector of the problem variables;

* the linear constraint matrix *A*, and the lower and upper bounds of the linear con-
straints, *l* and *u* respectively;

• the triplets *M*, *D*, *P* and *U*;

• the values of the problem variables *x* and their lower and upper bounds *x*^L and *x*^U.

For these reasons, and as has already been mentioned (cf. Section 5.4.1), *ooOPS* au-
tomatically derives the standard form for any NLP represented within it and makes it
available to its clients.

6. *ooOPS* allows a client to manipulate any number of NLPs simultaneously; this is impor-
tant for supporting applications which require iterating between two or more optimization
problems, with information derived from the solution of one of these NLPS being used to
define or modify one or more of the others.

7. *ooOPS* allows its clients to evaluate the objective function and constraints of any NLP held within it. Moreover, it automatically derives, and makes available to its clients, structural (e.g. sparsity pattern) and symbolic (e.g. exact partial derivatives<fnref n="3" />) information on these NLPs. An algorithm for fast evaluation of symbolic expressions has been devised and implemented [71].

8. *ooOPS* provides its clients a uniform interface to diverse LP/NLP/MILP/MINLP solvers from a variety of sources and coded in a variety of programming languages. These solvers operate on NLPs defined within *ooOPS*.

<footnote n="3">³*ooOPS* derives partial derivatives in closed analytic form using symbolic differentiation.</footnote>
### 5.4.2 Object classes in ooOPS

In order to deliver the above functionality, *ooOPS* recognizes four major classes of objects, each with its own client interface.

1. The ops object.

An ops object is a software representation of an NLP problem. The corresponding interface:

* allows NLP objects to be constructed and modified in a structured manner (cf. Section 5.4.1);

* provides access to all numerical and symbolic information pertaining to the NLP in structured, flat (unstructured) and standard forms.

2. The opssystem object.

This represents the combination of an NLP ops object with a specific solver code (e.g. SNOPT [43]). The corresponding client interface:

* allows the behaviour of the solver to be configured via the specification of any algorithmic parameters that the solver may support.

* permits the solution of the NLP.

3. The opssolvermanager object.

This corresponds to a particular NLP solver (e.g. SNOPT [43]). The primary function of the corresponding client interface is to receive an ops object representing a particular NLP and to return an opssystem (see above) that represents the combination of this NLP with the solver code.

4. The convexifiermanager object.

This embeds a code which produces a convex relaxation of a given non-convex NLP. More specifically, given an ops object representing a particular NLP, it creates another ops object describing a convex relaxation of the NLP. The corresponding client interface also allows the “on-the-fly” updating of the convex relaxation whenever the ranges of the variables change.
### 5.4.3 Typical usage scenario for ooOPS

A typical client application of *ooOPS* makes use of the object classes described above to formulate and solve an optimization problem. This involves a number of steps:

1. Construct an `ops` object describing the NLP to be solved. This is done by creating one or more structured variables and then introducing an objective function and constraints defined in terms of these variables.

2. Create an `opssolvermanager` for the particular NLP solver code that is to be used.

3. Configure the solver's behaviour by setting appropriate values for its algorithmic parameters (e.g. convergence tolerances, maximum number of iterations etc.); this is done by calling appropriate methods provided by the `opssolvermanager`'s interface.

4. Create an `opssystem` by passing the `ops` object created at step 1 to the `opssolvermanager` created at step 2.

5. Solve the problem by invoking the `opssystem's Solve()` method. This will involve the solver code interacting directly with the `ops` object in a (usually large) number of steps. For example, a local NLP solver may typically issue the following requests to an `ops` object:

(a) Obtain the numbers of variables and constraints in the NLP to be solved, as well as other structural information such as the nature of each constraint (e.g. linear/non-linear, constraint bounds etc.), the sparsity pattern and so on.

(b) Obtain the initial values of all the NLP problem variables.

(c) In an iterative loop,

i. evaluate the objective function and the constraints at the current values of the problem variables;

ii. (possibly) evaluate the partial derivatives of the objective function and the constraints at the current values of the problem variables;

iii. modify the values of the problem variables;

until convergence is obtained or some other termination criterion is satisfied (e.g. the maximum number of allowable iterations is reached).

6. Obtain the NLP's solution by invoking the `ops's` method for querying variable values.
### 5.4.4 Solver components for use within ooOPS

The interactions at steps 2-5 of the typical usage scenario presented in Section 5.4.3 above impose certain requirements on every numerical solver designed for use in the context of *ooOPS*. More specifically:

* each such solver must be implemented as a software component that exposes an `ops-solvermanager` interface (cf. step 2 of the interaction);

* the solver's `opssolvermanager` interface must provide a set of methods for accessing and modifying the algorithmic parameters associated with this solver (cf. step 3 of the interaction);

* the solver must obtain all information regarding the NLP to be solved by calling appropriate methods in the NLP's `ops` object (cf. step 5 of the interaction);

* at the end of the numerical solution, the solver must place the final (converged) values of the solution variables back in the `ops` object describing the original NLP, from where they can be recovered at any later stage by the client (cf. step 6 of the interaction).

Albeit apparently burdensome, the above requirements are, in fact, relatively easy to satisfy. Some solver software components can be designed and implemented specifically for *ooOPS* while others may be pre-existing pieces of software which are “wrapped” in an *ooOPS*-compliant interface. In either case, all solver modules consist of the actual solver code, an `opssystem` interface and an `opssolvermanager` interface. Template files are provided with *ooOPS* in order to facilitate the construction of these interfaces.

In practice, solver components are implemented as dynamic link libraries which expose a single function called `NewMINLPSolverManager`. Application clients typically apply dynamic linking to these solver components, and then invoke `NewMINLPSolverManager` to create a new solver manager object and obtain an interface to it.

As an illustration of the implementation of solver components within the *ooOPS* framework, we have wrapped the `SNOPT` code [43] for local NLP optimization. However, of more interest to this thesis is the implementation of a global optimization code based on a variation of Smith's `sBB` algorithm; this is described in Section 5.5.
## 5.5 An sBB solver for the *ooOPS* framework

The sBB algorithm of Smith [114, 116] for global optimization (cf. Section 5.2), with the minor improvements described in Section 5.3, has been implemented for use within the *ooOPS* framework.

### 5.5.1 Overview of the sBB code

The sBB implementation makes use of two sub-solvers: a local NLP solver for obtaining upper bounds by solving the original NLP in each region; and an optimization solver for obtaining lower bounds by solving the convex relaxation of the original NLP in each region. Each of these sub-solvers is itself implemented as an *ooOPS*-compliant optimization solver. In addition, the sBB code makes use of a convexifier, a software component which, given an *ops* object, constructs another *ops* object that represents a convex relaxation of the former. This is described in more detail in Section 5.5.2.

More specifically, given an *ops* object describing a non-convex NLP, our sBB solver executes the following sequence of operations in the context of step 5 of the generic algorithm outlined in Section 5.4.3:

1. Create an `opssolvermanager` for the local solver which will be used to solve the upper bounding problem.

2. Pass the original *ops* object to the above local `opssolvermanager` to create an upper bounding `opssystem`.

3. Create a `convexifiermanager`.

4. Create a new *ops* object representing a convex relaxation of the original *ops* object by passing the latter to the above `convexifiermanager`.

5. Create an `opssolvermanager` for the optimization solver to be used for the solution of the lower bounding problem.

6. Create a lower bounding `opssystem` by passing the *ops* object constructed at step 4 to the `opssolvermanager` constructed at step 5.

7. During the branch-and-bound search:
(a) repeatedly call the `Solve` methods of the `opssystems` constructed at steps 2 and 6 to solve the upper and lower bounding problems respectively.

(b) On changing the variable ranges during branching, update the lower bounding problem by invoking the `UpdateConvexVarBounds()` method in the `convexifiermanager`.

8. De-allocate all objects created by the global solver code.

As can be seen, the above procedure takes advantage of *ooOPS's* capabilities to simultaneously manipulate two *ops* objects respectively describing the original NLP problem and its convex relaxation.

Our current sBB implementation uses SNOPT [43] for solving the upper bounding problem, and the CPLEX [60] linear programming code as the solver for the convex relaxation<fnref n="4" />. It is worth noting, however, that, in principle, *any* *ooOPS*-compliant local NLP solver can be used as a sub-solver within our sBB code.

### 5.5.2 The convexifier

In addition to generic numerical optimization solvers, the *ooOPS* framework recognizes another generic type of software component, that of convexifiers. These simply take one *ops* object representing a non-convex NLP, and return another *ops* object representing a convex relaxation of the original NLP. *ooOPS* does not prescribe how this relaxation is to be formed or indeed how tight it should be; all it does is to define a standard software interface for convexifiers or, more precisely, for *convexifiermanager* objects (cf. Section 5.4.2). This allows convexifiers based on different approaches and/or originating from different sources to be used within *ooOPS*.

For our purposes, we have implemented a convexifier based on the approach described in Section 5.2.2. This makes use of the standard form of the NLP which is automatically constructed and made available by the *ops* object (cf. Section 5.4.1). In our current implementation, we use only linear relaxations (cf. Section 5.2.2.2), and consequently, the *ops* object constructed by the *convexifiermanager* is actually a cut-down version of the full *ops*

<footnote n="4">⁴The use of CPLEX in this context is possible because the convexifier implemented and used in the current code constructs a *linear* convex relaxation of the non-convex NLP (see Section 5.5.2).</footnote>
class which only offers methods for manipulating the linear problem in flat (unstructured) form.

As has been seen in Section 5.2.2.2, the convex relaxation of an NLP involves the bounds $x^L$ and $x^U$ of the problem variables $x$ within the current region. For the efficient operation of the sBB algorithm, it is important to be able to efficiently update the convex relaxation by taking account of changes in these bounds and not to have to regenerate it from the beginning. To achieve this, our convexifier implementation creates dependency links between the constraints in the relaxed problems and the variable ranges. This facilitates the “on-the-fly” updating of the convex relaxation whenever the ranges of any variable(s) change (i.e. as the sBB algorithm moves from considering one region to another).

### 5.5.3 Storing the list of regions

In abstract terms, a region to be considered by the sBB algorithm is a hypercube in the Euclidean space characterized by a list of $n$ variable ranges where $n$ is the total number of variables in the NLP. Thus, the memory requirements for storing each region would appear to be $2n$. Furthermore, during branching, we have to copy $2n$ memory units from the original region to each of the two new ones. However, this is wasteful since branching always reduces the range of just one variable while the ranges of all other variables remain unchanged.

In view of the above, we prefer to store regions in a tree structure, each node of which contains:

* the branch variable which led to the region's creation and its range;

* a pointer to the parent region;

* the objective function lower and upper bounds for this region;

* a flag that signals whether an upper bound is already available for the region prior to calculation (cf. Section 5.3.2).

The top region of the tree does not have any of the above information.

Starting from any node in the tree, we can derive the complete set of variable bounds for the corresponding region by ascending the tree via the node's parent. More specifically, given a particular node in the tree,
<figure><img src="image_18.png" /><figcaption>Figure 5.2: The region tree.</figcaption></figure>

1. We label all problem variables as “unmarked” and initialize their ranges to be those in the original NLP.

2. If the branch variable in the current node is still unmarked, we:

(a) modify its range to that indicated by the current node;

(b) label this variable as “marked”.

3. If the current node is not the top node, we apply the above procedure to the parent of the current node; otherwise we terminate.

As an example, consider the region tree shown in Fig. 5.2 constructed at some stage during the solution of an NLP involving three variables, namely $x \in [-2, 2]$, $y \in [-1, 1.5]$ and $z \in [-1, 1]$. For ease of reference, the nodes of the tree are labeled as *a...g*; the branch variable which led to the node's creation, and its range within this node, are also shown. Now suppose we wish to establish the ranges of all variables for node *g*. This can be achieved as follows:

1. We label all three variables *x*, *y*, *z* as unmarked and set their ranges to those in the original NLP, i.e. *x* ∈ [-2, 2], *y* ∈ [-1, 1.5] and *z* ∈ [-1, 1].

2. Starting from node *g*, since the branch variable *x* is unmarked, we modify its range to [1, 2] and label it as marked. The variable ranges are now *x* ∈ [1, 2], *y* ∈ [-1, 1.5] and *z* ∈ [-1, 1].
3. We now move to $d$ which is the parent node of $g$. Since the branch variable $y$ is unmarked, we modify its range to $[-1, 1]$ and label it as marked. The variable ranges are now $x \in [1, 2]$, $y \in [-1, 1]$ and $z \in [-1, 1]$.

4. We now move to $c$ which is the parent node of $d$. Since the branch variable $x$ is already marked, we do not make any modifications to the variable ranges at this node.

5. We now move to $a$ which is the parent node of $c$. Since this is the top node, we terminate.

Overall, the above sequence of steps has determined that the variable ranges for the region corresponding to node $g$ are $x \in [1, 2]$, $y \in [-1, 1]$ and $z \in [-1, 1]$.

## 5.6 Concluding remarks

In this chapter, we presented an outline of the symbolic reformulation spatial Branch-and-Bound (sBB) algorithm by Smith [114, 116] and proposed some minor improvements to it. We also considered the software implementation of general sBB algorithms, and the requirements that this imposes in terms of numeric, structural and symbolic information on the NLP being solved. Our analysis led us to the development of *ooOPS*, a general software framework for optimization that can support both local and global optimization solvers.

A key concept in the design of *ooOPS* is the separation of the NLP problem being solved from the optimization solver itself; the former is described by a software object *ops* while the latter is implemented as a software component exposing an *opssolvermanager* object interface. The combination of a solver manager with *ops* object leads to the creation of an *opssystem* object which can be solved by the invocation of an appropriate method. We borrowed all of these ideas from the design of standardized software components for the solution of sets of nonlinear algebraic and mixed differential-algebraic equations in the CAPE-OPEN project, an international initiative for the standardization of process engineering software<fnref n="5" />. Having extended these concepts to the solution of nonlinear optimization problems, we have contributed some of them back to the CAPE-OPEN initiative to form the basis of a new standard<fnref n="6" /> for optimization solvers [88].

In order to test the generality and applicability of the *ooOPS* framework, we successfully

<footnote n="5">⁵See http://www.colan.org.</footnote>

<footnote n="6">⁶Note, however, that this standard does not yet support *global* optimization solvers of the type considered here.</footnote>
implemented an sBB algorithm as an *ooOPS*-compliant solver code, together with all its asso-
ciated sub-solvers as well as a convexifier. It is worth pointing out, however, that our current
sBB implementation is rather basic without many of the sophisticated implementation details
that accelerate the performance of such algorithms (e.g. good range-reduction techniques, im-
proved branching procedures etc.). Nevertheless, *ooOPS* provides an open architecture within
which more sophisticated implementations may be embedded in the future.
# Chapter 6

## Concluding remarks

This thesis has considered several topics related to the global solution of nonconvex nonlinear programming (NLP) problems. A major theme throughout our research has been the importance of the mathematical formulation of a given engineering optimization problem. The work presented in Chapter 3 was initially motivated by an observation by Smith [114], page 270 that the addition of a relatively small number of constraints to the material balances of a distillation column model could result in hugely improved computational performance of his spatial branch-and-bound algorithm. Smith derived these constraints by multiplying linear mole fraction normalization constraints by total flowrates; albeit redundant with respect to the original column equations, they were not redundant with respect to the convex relaxation of these equations, and in fact produced a tightening of the latter.

Based on the above observation, we sought to generalize the approach to produce such constraints for general NLPs involving bilinear terms. In the event, we discovered that these constraints were not only a means of tightening the convex relaxation, but in fact allowed the exact reformulation of the *original* NLP to replace a number of bilinear terms by linear constraints. Thus, the resulting formulation is less nonlinear than the original, as well as having a tighter convex relaxation.

Another important aspect of the work presented in Chapter 3 is the use of graph theoretical algorithms for limiting the number of redundant constraints generated to those that are guaranteed to produce an improved mathematical formulation. Smith's empirical observation (mentioned above) was that it was beneficial to multiply a linear constraint by a problem variable if this did not introduce any new bilinear term. In this thesis, we showed that even multiplications
which do introduce some new bilinear terms may be beneficial provided the number of such
terms is smaller than the number of constraints involved in these multiplications; and that graph
theoretical algorithms for the identification of dilations in bipartite graphs are ideally suited
for locating such situations even for very large problems. Overall, the proposed reformulation
techniques are much more selective in generating new constraints and variables than earlier
techniques such as RLT [111], which makes them more applicable to NLPs of non-trivial size.

A second major focus of the thesis has been the derivation of convex relaxations for monomial terms of odd degree when the variable range includes zero. Whereas the idea of deriving the convex/concave envelopes of piecewise convex and concave functions is geometrically quite obvious and already present in the literature [80, 126], its mention was sporadic and its theoretical analysis superficial. In Chapter 4, we have given an in-depth analysis of these envelopes, derived tight linear relaxations, and compared these with other existing techniques. The results of the latter comparison have been quite favourable. Overall, monomial terms of odd degree do appear in many practical applications (albeit certainly not as frequently as other kinds of terms such as bilinear products); we believe that the work presented in this thesis fills an important gap in the handling of these terms by spatial branch-and-bound methods.

Finally, our work has considered the software implications and requirements of implement-
ing spatial branch-and-bound algorithms. Although these are often thought of and referred to
as “numerical” solution codes, in fact they pose many more demands in terms of the type and
amount of information that they need than, say, conventional local optimization codes. In partic-
ular, automatic reformulation techniques of the type discussed in this thesis require substantial
symbolic information, and so does the construction of convex relaxations. Some of these issues
were addressed by earlier workers such as Smith [114] and Adjiman et al. [4] who designed
stand-alone software systems for global optimization based on spatial branch-and-bound algo-
rithms. The *ooOPS* system described in Chapter 5 takes a different approach where the aim
is to develop a generic software libraries comprising callable functions that can be embedded
within larger software systems in order to provide a global optimization capability.

The *ooOPS* system developed as part of the work leading to this thesis contains advanced
mechanisms for formulation of complex models (e.g. in terms of multidimensional variables
and constraints), as well as implementations of automatic reformulation and convexification
procedures. However, it includes only a rudimentary implementation of the actual spatial
branch-and-bound algorithm, without many of the sophisticated implementation details that
accelerate the performance of such algorithms. In view of this, it is interesting to note that the
numerical results reported in Section 3.5 indicate that, at least for the class of pooling and blend-
ing problems considered there, the algorithm's performance was better than that of most of the algorithms reported in the literature; in fact, it was comparable to (albeit not quite as good as) that of the best code, namely BARON [102] which employs good range-reduction techniques, improved branching procedures and other advanced features. We believe that this is another illustration of the importance of good mathematical formulation. Of course, automatic reformulation techniques and advanced implementation features are largely complementary, and it is to be expected that even better performance could be obtained by combining them in a single code.
Bibliography

[1] N. Adhya, M. Tawarmalani, and N. Sahinidis. A Lagrangian approach to the pooling problem. *Industrial and Engineering Chemistry Research*, 38:1956–1972, 1999.

[2] C. Adjiman. *Global Optimization Techniques for Process Systems Engineering*. PhD thesis, Princeton University, June 1998.

[3] C. Adjiman, I. Androulakis, and C. Floudas. Global optimization of MINLP problems in process synthesis and design. *Computers & Chemical Engineering*, 21:S445–S450, 1997.

[4] C. Adjiman, S. Dallwig, C. Floudas, and A. Neumaier. A global optimization method, $\alpha$BB, for general twice-differentiable constrained NLPs: I. Theoretical advances. *Computers & Chemical Engineering*, 22:1137–1158, 1998.

[5] C. Adjiman, I. Androulakis, and C. Floudas. A global optimization method, $\alpha$BB, for general twice-differentiable constrained NLPs: II. Implementation and computational results. *Computers & Chemical Engineering*, 22:1159–1179, 1998.

[6] C. Adjiman, I. Androulakis, C. Maranas, and C. Floudas. A global optimization method, $\alpha$BB, for process design. *Computers & Chemical Engineering*, 20:S419–S424, 1996.

[7] C. Adjiman and C. Floudas. Rigorous convex underestimators for general twice-differentiable problems. *Journal of Global Optimization*, 9:23–40, 1996.

[8] C. Adjiman, C. Schweiger, and C. Floudas. Mixed-integer nonlinear optimization in process synthesis. In D. Du and P. (Eds.) Pardalos, editors, *Handbook of Combinatorial Optimization*, vol. I, volume 1, pages 1–76, Dordrecht, 1998. Kluwer Academic Publishers.
[9] A. Aho, J. Hopcroft, and J. Ullman. *Data Structures and Algorithms*. Addison-Wesley, Reading, MA, 1983.

[10] F. Al-Khayyal and J. Falk. Jointly constrained biconvex programming. *Mathematics of Operations Research*, 8:273–286, 1983.

[11] F. Al-Khayyal and H. Sherali. On finitely terminating branch-and-bound algorithms for some global optimization problems. *SIAM Journal of Optimization*, 10:1049–1057, 2000.

[12] R. Amarger, L. Biegler, and I. Grossmann. An automated modeling and reformulation system for design optimization. *Computers & Chemical Engineering*, 16:623–636, 1992.

[13] I. Androulakis, C. Maranas, and C. Floudas. αBB: A global optimization method for general constrained nonconvex problems. *Journal of Global Optimization*, 7:337–363, 1995.

[14] M. Bazaraa, H. Sherali, and C. Shetty. *Nonlinear Programming: Theory and Algorithms*. Wiley, Chichester, second edition, 1993.

[15] E. Beale and J. Tomlin. Special facilities in a general mathematical programming system for nonconvex problems using ordered sets of variables. In J. Laurence, editor, *Proceedings of the Fifth International Conference on Operational Research*, pages 447–454, London, 1970. Tavistock Publications.

[16] J. Beasley. Heuristic algorithms for the unconstrained binary quadratic programming problem. http://mscmga.ms.ic.ac.uk/jeb/bqp.pdf, 1998.

[17] A. Ben-Tal, G. Eiger, and V. Gershovitz. Global minimization by reducing the duality gap. *Mathematical Programming*, 63:193–212, 1994.

[18] H. Benson. Concave minimization: Theory, applications and algorithms. In Horst and Pardalos [57], pages 43–148.

[19] J. Bjorkqvist and T. Westerlund. Automated reformulation of disjunctive constraints in MINLP optimization. *Computers and Chemical Engineering*, 23:S11–S14, 1999.

[20] I. Bomze. On standard quadratic optimization problems. *Journal of Global Optimization*, 13:369–387, 1998.

[21] I. Bomze, M. Budinich, P. Pardalos, and M. Pelillo. The maximum clique problem. In Du and Pardalos [28], pages 1–74.
[22] A. Brook, D. Kendrick, and A. Meeraus. Gams, a user's guide. *ACM SIGNUM Newsletter*, 23:10–11, 1988.

[23] R. Chelouah and P. Siarry. Tabu search applied to global optimization. *European Journal of Operational Research*, 123:256–270, 2000.

[24] K. Ciesielski. *Set Theory for the Working Mathematician*. Cambridge University Press, Cambridge, 1997.

[25] A. Colorni, M. Dorigo, and V. Maniezzo. Distributed optimization by ant colonies. In F. Varela and P. Bourgine, editors, *Proceedings of the European Conference on Artificial Life*, pages 134–142, Amsterdam, 1991. ECAL, Paris, France, Elsevier.

[26] D. Cox, J. Little, and D. O’Shea. *Ideals, Varieties and Algorithms*. Springer-Verlag, Berlin, second edition, 1997.

[27] G. Dantzig. *Linear Programming and Extensions*. Princeton University Press, Princeton, NJ, 1963.

[28] D. Du and P. Pardalos, editors. *Handbook of Combinatorial Optimization*, volume supp. A. Kluwer Academic Publishers, Dordrecht, 1998.

[29] I. Duff. On algorithms for obtaining a maximum transversal. *ACM Trans. Math. Software*, 7:315–330, 1981.

[30] Process Systems Enterprise. *gPROMS v2.2 Introductory User Guide*. Process Systems Enterprise, Ltd., London, UK, 2003.

[31] T. Epperly. *Global Optimization of Nonconvex Nonlinear Programs using Parallel Branch and Bound*. PhD thesis, University of Wisconsin – Madison, 1995.

[32] T. Epperly and E. Pistikopoulos. A reduced space branch and bound algorithm for global optimization. *Journal of Global Optimization*, 11:287:311, 1997.

[33] E. Eskow and R. Schnabel. Mathematical modeling of a parallel global optimization algorithm. *Parallel Computing*, 12:315–325, 1989.

[34] J. Falk and R. Soland. An algorithm for separable nonconvex programming problems. *Management Science*, 15:550–569, 1969.

[35] A. Fiacco and G. McCormick. *Nonlinear Programming: Sequential Unconstrained Minimization Techniques*. Wiley, New York, 1968.
[36] A. Fischer. New constrained optimization reformulation of complementarity problems. *Journal of Optimization Theory and Applications*, 99:481–507, 1998.

[37] R. Fischer. A new algorithm for generating space-filling curves. *Software Practice and Experience*, 16:5–12, 1986.

[38] R. Fletcher. *Practical Methods of Optimization*. Wiley, Chichester, second edition, 1991.

[39] C. Floudas. *Deterministic Global Optimization*. Kluwer Academic Publishers, Dordrecht, 2000.

[40] L. Foulds, D. Haughland, and K. Jornsten. A bilinear approach to the pooling problem. *Optimization*, 24:165–180, 1992.

[41] A. Frangioni. On a new class of bilevel programming problems and its use for reformulating mixed-integer problems. *European Journal of Operations Research*, 82:615–646, 1995.

[42] R. Ge. A parallel global optimization algorithm for rational separable-factorable functions. *Applied Mathematics and Computation*, 32:61–72, 1989.

[43] P. Gill. *User's Guide for SNOPT 5.3*. Systems Optimization Laboratory, Department of EESOR, Stanford University, California, 1999.

[44] B. Goertzel. Global optimisation with space-filling curves. *Applied Mathematics Letters*, 12:133–135, 1999.

[45] E. Goodaire and M. Parmenter. *Discrete Mathematics with Graph Theory*. Prentice-Hall, London, 1998.

[46] I.E. Grossmann, editor. *Global Optimization in Engineering Design*. Kluwer Academic Publishers, Dordrecht, 1996.

[47] K. Hägglöf, P. Lindberg, and L. Svensson. Computing global minima to polynomial optimization problems using gröbner bases. *Journal of Global Optimization*, 7:115:125, 1995.

[48] E. Hansen. Global constrained optimization using interval analysis. In K. Nickel, editor, *Interval Mathematics 1980*, pages 25–47, New York, 1980. Proceedings of the International Symposium, Freiburg, Academic Press.
[49] E. Hansen. *Global Optimization Using Interval Analysis*. Marcel Dekker, Inc., New York, 1992.

[50] P. Hansen, B. Jaumard, and S. Lu. Analytical approach to global optimization. *Comptes Rendus de L Academie Des Sciences Serie I-mathematique*, 306:29-32, 1988.

[51] F. Harary. *Graph Theory*. Addison-Wesley, Reading, MA, second edition, 1971.

[52] M. Hirafuji and S. Hagan. A global optimization algorithm based on the process of evolution in complex biological systems. *Computers and Electronics in Agriculture*, 29:125-134, 2000.

[53] R. Horst. A general-class of branch-and-bound methods in global optimization with some new approaches for concave minimization. *Journal of Optimization Theory and Applications*, 51:271-291, 1986.

[54] R. Horst. Deterministic global optimization with partition sets whose feasibility is not known: Application to concave minimization, reverse convex constraints, d.c. programming and lipschitzian optimization. *Journal of Optimization Theory and Applications*, 58:11-37, 1988.

[55] R. Horst. On consistency of bounding operations in deterministic global optimization. *Journal of Optimization Theory and Applications*, 61:143-146, 1989.

[56] R. Horst, J. Devries, and N. Thoai. On finding new vertices and redundant constraints in cutting plane algorithms for global optimization. *Operations Research Letters*, 7:85-90, 1988.

[57] R. Horst and P. Pardalos, editors. *Handbook of Global Optimization*, volume 1. Kluwer Academic Publishers, Dordrecht, 1995.

[58] R. Horst and H. Tuy. *Global Optimization: Deterministic Approaches*. Springer-Verlag, Berlin, first edition, 1990.

[59] R. Horst and H. Tuy. *Global Optimization: Deterministic Approaches*. Springer-Verlag, Berlin, third edition, 1996.

[60] ILOG. *ILOG CPLEX 8.0 User's Manual*. ILOG S.A., Gentilly, France, 2002.

[61] P. Kesavan and P. Barton. Generalized branch-and-cut framework for mixed-integer non-linear optimization problems. *Computers and Chemical Engineering*, 24:1361-1366, 2000.
[62] M. Kline. *Mathematical Thought from Ancient to Modern Times*. Oxford University Press, Oxford, 1972.

[63] G. Kocis and I. Grossmann. Global optimization of nonconvex mixed-integer nonlinear-programming (MINLP) problems in process synthesis. *Industrial & Engineering Chemistry Research, 27:1407–1421, 1988.*

[64] B. Korte and J. Vygen. *Combinatorial Optimization, Theory and Algorithms*. Springer-Verlag, Berlin, 2000.

[65] K. Kunen. *Set Theory*. North Holland, Amsterdam, 1980.

[66] J. Lagrange. *Théorie des fonctions analytiques*. Impr. de la République, Paris, 1797.

[67] B. Lamar. A method for converting a class of univariate functions into d.c. functions. *Journal of Global Optimization*, 15:55:71, 1999.

[68] Y. Lee and B. Berne. Global optimization: Quantum thermal annealing with path integral monte carlo. *Journal of Physical Chemistry A*, 104:86–95, 2000.

[69] D. Li and X. Sun. Local convexification of the lagrangian function in nonconvex optimization. *Journal of Optimization Theory and Applications*, 104:109–120, 2000.

[70] D. Li and X. Sun. Convexification and existence of a saddle point in a pth-power reformulation for nonconvex constrained optimization. *Nonlinear Analysis*, 47:5611–5622, 2001.

[71] L. Liberti. Performance comparison of function evaluation methods. *Progress in Computer Science Research*, accepted.

[72] L. Liberti and C. Pantelides. Convex envelopes of monomials of odd degree. *Journal of Global Optimization*, 25:157–168, 2003.

[73] L. Liberti, P. Tsiakis, B. Keeping, and C. Pantelides. *ooOPS*. Centre for Process Systems Engineering, Chemical Engineering Department, Imperial College, London, UK, 1.24 edition, 2001.

[74] R. Luus and T. Jaakola. Optimization by direct search and systematic reduction of the size of the search region. *AIChE Journal*, 19:760–766, 1973.

[75] C. Maranas and C. Floudas. Finding all solutions to nonlinearly constrained systems of equations. *Journal of Global Optimization*, 7:143–182, 1995.
[76] H. Margenau and G. Murphy. *The Mathematics of Physics and Chemistry*. Van Nostrand, Princeton, NJ, second edition, 1956.

[77] S. Masri, G. Bekey, and F. Safford. A global optimization algorithm using adaptive random search. *Applied Mathematics and Computation*, 7:353–375, 1980.

[78] M. Mathur, S. Karale, S. Priye, V.K. Jayaraman, and B. Kulkarni. Ant colony approach to continuous function optimization. *Industrial and Engineering Chemistry Research*, 39:3814–3822, 2000.

[79] G. McCormick. Converting general nonlinear programming problems to separable non-linear programming problems. Technical Paper T-267, Program in Logistics, The George Washington University, Washington D.C., 1972.

[80] G. McCormick. Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems. Mathematical Programming, 10:146–175, 1976.

[81] C. Meewella and D. Mayne. An algorithm for global optimization of lipschitz continuous functions. Journal of Optimization Theory and Applications, 57:307–322, 1988.

[82] C. Meewella and D. Mayne. Efficient domain partitioning algorithms for global optimization of rational and lipschitz continuous functions. Journal of Optimization Theory and Applications, 61:247–270, 1989.

[83] W. Murray and K. Ng. Algorithms for global optimization and discrete problems based on methods for local optimization. In Pardalos and Romeijn [91], pages 87–113.

[84] A. O'Grady, I. Bogle, and E. Fraga. Interval analysis in automated design for bounded solutions. Chemicke Zvesti, 55:376–381, 2001.

[85] J.M. Ortega and W.C. Rheinboldt. *Iterative Solution of Nonlinear Equations in Several Variables*. Academic Press, New York, 1970.

[86] J. Pang. Complementarity problems. In Horst and Pardalos [57], pages 271–338.

[87] C. Pantelides. The consistent initialization of differential-algebraic systems. SIAM J. Sci. Stat. Comput., 9:213–231, 1988.

[88] C. Pantelides, L. Liberti, P. Tsiakis, and T. Crombie. Mixed integer linear/nonlinear programming interface specification. Global Cape-Open Deliverable WP2.3-04, 2002.
[89] P. Pardalos. Enumerative techniques for solving some nonconvex global optimization problems. *Or Spektrum*, 10:29–35, 1988.

[90] P. Pardalos. Parallel search algorithms in global optimization. *Applied Mathematics and Computation*, 29:219–229, 1989.

[91] P. Pardalos and H. Romeijn, editors. *Handbook of Global Optimization*, volume 2. Kluwer Academic Publishers, Dordrecht, 2002.

[92] P. Pardalos and J. Rosen. *Constrained Global Optimization: Algorithms and Applications*. Springer-Verlag, Berlin, 1987.

[93] P. Pardalos and G. Schnitger. Checking local optimality in constrained quadratic programming is np-hard. *Operations Research Letters*, 7:33–35, 1988.

[94] J. Pinter. Global optimization on convex sets. *Or Spektrum*, 8:197–202, 1986.

[95] R. Pörn, I. Harjunkoski, and T. Westerlund. Convexification of different classes of non-convex MINLP problems. *Computers and Chemical Engineering*, 23:439–448, 1999.

[96] S. Rajasekaran. On simulated annealing and nested annealing. *Journal of Global Optimization*, 16:43–56, 2000.

[97] H. Ratschek and J. Rokne. Efficiency of a global optimization algorithm. *Siam Journal On Numerical Analysis*, 24:1191–1201, 1987.

[98] R. Rockafellar. *Convex Analysis*. Princeton University Press, Princeton, NJ, 1970.

[99] H. Ryoo and N. Sahinidis. Global optimization of nonconvex NLPs and MINLPs with applications in process design. *Computers & Chemical Engineering*, 19:551–566, 1995.

[100] H. Ryoo and N. Sahinidis. A branch-and-reduce approach to global optimization. *Journal of Global Optimization*, 8:107–138, 1996.

[101] H. Ryoo and N. Sahinidis. Global optimization of multiplicative programs. *Journal of Global Optimization*, 26:387–418, 2003.

[102] N. Sahinidis. Baron: Branch and reduce optimization navigator: User's manual, version 4.0. http://archimedes.scs.uiuc.edu/baron/manuse.pdf, 1999.

[103] P. Salus, editor. *Object-Oriented Programming Languages*. MacMillan, Indianapolis, 1998.
[104] F. Schoen. Two-phase methods for global optimization. In Pardalos and Romeijn [91], pages 151–177.

[105] G. Schrimpf, J. Schneider, H. Stamm-Wilbrandt, and G. Dueck. Record breaking optimization results using the ruin and recreate principle. *Journal of Computational Physics*, 159:139–171, 2000.

[106] J. Shectman and N. Sahinidis. A finite algorithm for global minimization of separable concave programs. *Journal of Global Optimization*, 12:1–36, 1998.

[107] H. Sherali. Global optimization of nonconvex polynomial programming problems having rational exponents. *Journal of Global Optimization*, 12:267–283, 1998.

[108] H. Sherali. Tight relaxations for nonconvex optimization problems using the reformulation-linearization/convexification technique (RLT). In Pardalos and Romeijn [91], pages 1–63.

[109] H. Sherali and W. Adams. A tight linearization and an algorithm for 0-1 quadratic programming problems. *Management Science*, 32:1274–1290, 1986.

[110] H. Sherali and W. Adams. *A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems*. Kluwer Academic Publishers, Dodrecht, 1999.

[111] H. Sherali and A. Alameddine. A new reformulation-linearization technique for bilinear programming problems. *Journal of Global Optimization*, 2:379–410, 1992.

[112] H. Sherali, J. Smith, and W. Adams. Reduced first-level representations via the reformulation-linearization technique: Results, counterexamples, and computations. *Discrete Applied Mathematics*, 101:247–267, 2000.

[113] H. Sherali and H. Wang. Global optimization of nonconvex factorable programming problems. *Mathematical Programming*, A89:459–478, 2001.

[114] E. Smith. *On the Optimal Design of Continuous Processes*. PhD thesis, Imperial College of Science, Technology and Medicine, University of London, October 1996.

[115] E. Smith and C. Pantelides. Global optimisation of nonconvex MINLPs. *Computers and Chemical Engineering*, 21:S791–S796, 1997.

[116] E. Smith and C. Pantelides. A symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex MINLPs. *Computers and Chemical Engineering*, 23:457–478, 1999.
[117] R. Soland. An algorithm for separable nonconvex programming problems ii: Nonconvex constraints. *Management Science*, 17:759–773, 1971.

[118] I. Stewart. *Galois Theory*. Chapman & Hall, London, second edition, 1989.

[119] R. Storn and K. Price. Differential evolution – a simple and efficient heuristic for global optimization over continuous spaces. *Journal of Global Optimization*, 11:341–359, 1997.

[120] A. Strekalovsky. On global optimality conditions for d.c. programming problems. *Technical Paper, Irkutsk State University*, 1997.

[121] A. Strekalovsky. Extremal problems with d.c. constraints. *Computational Mathematics and Mathematical Physics*, 41:1742–1751, 2001.

[122] R. Strongin. On the convergence of an algorithm for finding a global extremum. *Engineering Cybernetics*, 11:549–555, 1973.

[123] R. Strongin. Algorithms for multi-extremal mathematical programming problems employing the set of joint space-filling curves. *Journal of Global Optimization*, 2:357–378, 1992.

[124] R. Strongin. *Global Optimization with Non-Convex Constraints*. Kluwer Academic Publishers, Dodrecht, 2000.

[125] B. Stroustrup. *The C++ Programming Language*. Addison-Wesley, Reading, MA, third edition, 1999.

[126] M. Tawarmalani and N. Sahinidis. Global optimization of mixed integer nonlinear programs: A theoretical and computational study. *Mathematical Programming (to appear)*, http://archimedes.scs.uiuc.edu/papers/comp.pdf, 1999.

[127] M. Tawarmalani and N. Sahinidis. Semidefinite relaxations of fractional programming via novel techniques for constructing convex envelopes of nonlinear functions. *Journal of Global Optimization*, 20:137–158, 2001.

[128] M. Tawarmalani and N. Sahinidis. Convex extensions and envelopes of semi-continuous functions. *Mathematical Programming*, 93:247–263, 2002.

[129] M. Tawarmalani and N. Sahinidis. Convexification and global optimization of the pooling problem. *Mathematical Programming (submitted)*, 2002.
[130] M. Tawarmalani and N. Sahinidis. Exact algorithms for global optimization of mixed-integer nonlinear programs. In Pardalos and Romeijn [91], pages 1–63.

[131] A. Törn and A. Žilinskas. *Global Optimization*. Springer-Verlag, Berlin, 1989.

[132] H. Tuy. D.c. optimization: Theory, methods and algorithms. In Horst and Pardalos [57], pages 149–216.

[133] H. Tuy. *Convex Analysis and Global Optimization*. Kluwer Academic Publishers, Do-drecht, 1998.

[134] H. Tuy and R. Horst. Convergence and restart in branch-and-bound algorithms for global optimization: Application to concave minimization and d.c. optimization problems. *Mathematical Programming*, 41:161–183, 1988.

[135] A. Žilinskas. Axiomatic characterization of a global optimization algorithm and investigation of its search strategy. *Operations Research Letters*, 4:35–39, 1985.

[136] J. Žilinskas and I. Bogle. Evaluation ranges of functions using balanced random interval arithmetic. *Informatica*, 14:403–416, 2003.

[137] R. Vaidyanathan and M. El-Halwagi. Global optimization of nonconvex MINLPs by interval analysis. In Grossmann [46], pages 175–193.

[138] V. Visweswaran and C. Floudas. New properties and computational improvement of the gop algorithm for problems with quadratic objective functions and constraints. *Journal of Global Optimization*, 3:439–462, 1993.

[139] V. Visweswaran and C. Floudas. New formulations and branching strategies for the gop algorithm. In Grossmann [46].

[140] B. Wah and T. Wang. Efficient and adaptive lagrange-multiplier methods for nonlinear continuous global optimization. *Journal of Global Optimization*, 14:1:25, 1999.

[141] X. Wang and T. Change. A multivariate global optimization using linear bounding functions. *Journal of Global Optimization*, 12:383–404, 1998.

[142] T. Westerlund and R. Pörn. Solving pseudo-convex mixed integer optimization problems by cutting plane techniques. *Optimization and Engineering*, 3:235–280, 2002.
[143] T. Westerlund, H. Skrifvars, I. Harjunkoski, and R. Pörn. An extended cutting plane method for a class of non-convex MINLP problems. *Computers & Chemical Engineering*, 22:357–365, 1998.

[144] L. Wolsey. *Integer Programming*. Wiley, New York, 1998.

[145] Y. Yao. Dynamic tunnelling algorithm for global optimization. *IEEE Transactions On Systems Man and Cybernetics*, 19:1222–1230, 1989.

[146] J. Zamora and I. Grossmann. A branch and contract algorithm for problems with concave univariate, bilinear and linear fractional terms. *Journal of Global Optimization*, 14:217:249, 1999.
# Appendix A

## ooOPS Reference Manual

### A.1 Introduction

ooOPS is a library of C++ callable procedures for the definition, manipulation and solution of large, sparse mixed integer linear and nonlinear programming (MINLP) problems. In particular, ooOPS:

* facilitates the definition of complex sets of constraints, reducing the required programming effort to a minimum;

* allows its client programs to create and manipulate simultaneously more than one MINLP;

* provides a common interface to diverse MINLP solvers to be used without any changes to client programs.

MINLPs are optimization problems whose objective function and constraints can, in general, contain nonlinear terms. The variables appearing in the objective function and constraints are generally restricted to lie between specified lower and upper bounds. Furthermore, some of these variables may be restricted to integer values only. The aim of the optimization is to determine values of the variables that minimize or maximize the objective function while satisfying the constraints and all other restrictions imposed on them.

A simple mathematical description of an MINLP can be written as:

[Flat MINLP]:

$$ \min_{x} \phi(x) + c^{T}x \qquad (A.1) $$

$$ a \le f(x) + Ax \le b \qquad (A.2) $$

$$ x^l \le x \le x^u \qquad (A.3) $$

$$ x_i \in \mathbb{Z} \quad \forall i \in I \subseteq \{1, \dots, n\} \qquad (A.4) $$

where $x, x^l, x^u, c \in \mathbb{R}^n$, $b \in \mathbb{R}^m$, $A: \mathbb{R}^n \to \mathbb{R}^m$, $\phi: \mathbb{R}^n \to \mathbb{R}$ and $f: \mathbb{R}^n \to \mathbb{R}^m$. Thus, the variables $x$ are characterised by an index $i = 1, \dots, n$; all constraints are expressed as inequalities of the form $\le 0$ and are indexed over the discrete domain $1, \dots, m$.

The above general formulation also embeds three special cases:

* *Mixed Integer Linear Programming (MILP) Problems.*
  In this case, $\phi(x) = 0$ and $f(x) = 0$.

* *Nonlinear Programming (NLP) Problems.*
  In this case, $I = \emptyset$.

* *Linear Programming (LP) Problems.*
  In this case, $\phi(x) = 0$, $f(x) = 0$ and $I = \emptyset$.
The ooOPS software design aims to support the definition and solution of all these special cases, with minimal overhead being incurred because of the generality of the overall software.

Albeit quite general, the above MINLP form is not necessarily easy to construct and/or manipulate. A major reason for this is that the variables and constraints are maintained as unstructured “flat” lists or sets which may contain thousands of elements. On the other hand, most mathematical formulations of practical problems in terms of MINLPs are expressed in terms of a relatively small number of distinct sets of variables and constraints.

For example, in a typical network flow problem, a commonly occurring set of variables would be the flow of material from one node in the network to another, while a typical set of constraints would be the conservation of material arriving at, and leaving any node *i* in the network.

Of course, each such set of variables (or constraints) may have multiple elements, each corresponding to an individual variable (or constraint). An indexed set representation is usually employed for notational purposes. For instance, $F_{ij}$ could represent the flow from node *i* to node *j*, while $C_k$ could represent the set of conservation constraints:

$$ \sum_{i \neq k} F_{ik} = \sum_{j \neq k} F_{kj}, \quad \forall \text{ node } k $$

In view of the above discussion, ooOPS allows types of variables and constraints to be defined in a structured fashion as sets of an arbitrary number of dimensions.

## A.2 Fundamental concepts

### A.2.1 Object classes

ooOPS is designed as object-orientated software recognising two major classes of objects, each with its own interface:

1. The ops object

An ops object is a software representation of a MINLP problem. The corresponding interface, discussed in detail in section A.4, provides the following functionality:

* It allows MINLP objects to be constructed and modified in a structured manner.

* It allows access to all information pertaining to the MINLP.

* It provides the equivalent simple [Flat MINLP] form of the structured MINLP (see section A.1).

2. The opssystem object

This is formed by the combination of an MINLP object (see above) with a code (“solver”) for the numerical solution of MINLP problems. The corresponding interface, discussed in detail in section A.5, provides the following functionality:

* It allows the behaviour of the solver to be configured via the specification of any algorithmic parameters that the solver may support.

* It permits the solution of the MINLP.

### A.2.2 Multidimensional sets in ooOPS

As detailed later in the document, an MINLP is characterised by a number of distinct multidimensional sets of variables and constraints. We note that:

* A multidimensional set is an ordered set whose elements can be accessed through a list of indices.

* The dimensionality of a multidimensional set is given by the length of the index lists (i.e. the number of dimensions) and the range of each index in the list.
* The dimensionality size of a multidimensional set is the list of its dimension sizes. More precisely, a multidimensional set having *n* dimensions, with index *i*<sub>*j*</sub> ranging from *i*<sub>*j*</sub><sup>*L*</sup> to *i*<sub>*j*</sub><sup>*U*</sup> for each *j* between 1 and *n*, has dimensionality size:

$$ (i_1^U - i_1^L + 1, \dots, i_n^U - i_n^L + 1). $$

* A scalar has dimensionality size (1).

For instance, consider a 3-dimensional variable set $X(i, j, k)$, with the first dimension varying from $i = 0$ to $i = 10$, the second dimension from $j = 1$ to $j = 5$, and the third dimension from $k = -1$ to $k = +1$. We can view this as a multidimensional set, the dimensionality of which is characterised by the number of dimensions (3, in this case) and the ranges of each dimension (0: 10, 1: 5, -1: 1). The dimensionality size is the list $(11, 5, 3)$ ($= 10 - 0 + 1, 5 - 1 + 1, 1 - (-1) + 1$). The total number of elements of this set is $165$ ($= 11 \times 5 \times 3$).

*ooOPS* makes extensive use of the concept of *slices* as a convenient way of referring to subsets of multidimensional sets. In general:

* A slice $[s^L : s^U]$ of an $N$-dimensional set is defined by a pair of $N$-dimensional integer vectors $s_i^L, i = 1, \dots, N$ and $s_i^U, i = 1, \dots, N$ where $s_i^L \le s_i^U$.

* The element at position $(k_1, k_2, \dots, k_N)$ of the set belongs to the slice $[s^L : s^U]$ if and only if:

$$ s_i^L \le k_i \le s_i^U, \quad \forall i = 1, \dots, N \qquad (A.5) $$

Here are some examples:

* The slice $[(2) : (5)]$ of a 1-dimensional set $X$ denotes the elements $X_i, i = 2, 3, 4, 5$.

* The slice $[(2, 3) : (5, 4)]$ of a 2-dimensional set $X$ denotes the elements $X_{ij}, i = 2, 3, 4, 5, j = 3, 4$.

* The slice $[(2, 3, 3) : (5, 3, 4)]$ of a 3-dimensional set $X$ denotes the elements $X_{i3k}, i = 2, 3, 4, 5, k = 3, 4$.

* The slice $[(2, 3, 3, 4) : (2, 3, 3, 4)]$ of a 4-dimensional set $X$ denotes the single element $X_{2334}$.

### A.2.3 Constants, variables, constraints and objective function

Most optimization problems involve arithmetic constants. In *ooOPS*, these can be organized in one or more multidimensional sets. A *constant set* is characterised by the following information:

* its name;

* the dimensionality of the set;

* the current value of each element of the set;

The variables to be determined by the optimization are also organized in one or more multidimensional sets. A *variable set* is characterised by the following information:

* its name;

* the type of all variables in this set (continuous or integer);

* the dimensionality of the set;

* the current value of each element of the set;

* the upper and lower bounds of the value of each element of the set.
Similarly, the constraints in the optimization problem are also organized in one or more multidimensional sets.

A *constraint set* is characterised by the following information:

* its name;

* the lower and upper bound of the constraint;

* the dimensionality of the set;

* the variables occurring in the linear parts of these constraints and the corresponding coefficients (see note 1 in section A.2.5 below);

* the expression (see below) defining the nonlinear part of these constraints.

Most of the information characterising a set of constants, variables or constraints is common to *all* elements of the set. The *only* exceptions to this rule are:

* the values of elements of constant sets may differ from element to element;

* the values and bounds of elements of variable sets may differ from element to element;

* the constraint bounds of the constraint sets may differ from element to element.

Each MINLP object has a unique *objective function*. This is characterised by:

* the name of the objective function

* the type of the problem (minimization or maximization)

* the variables occurring in the linear part of the objective function and the corresponding coefficients (see note 1 in section A.2.5 below);

* the expression defining the nonlinear part of the objective function.

### A.2.4 Nonlinear expressions and constants

A nonlinear *expression* is, in general, built hierarchically from the algebraic combination of variables, constants (see below) and other expressions by using operators and functions. Expressions are characterised by the following information:

* their name;

* their dimensionality size;

* whether they represent variables, constants or operators.

An expression represents a valid algebraic expression. The operators and functions that can be used to combine variables, constants and other expressions are given in the following table:
<table><thead><tr><th>Name</th><th>Meaning</th></tr></thead><tbody><tr><td colspan="2"><strong>Binary Arithmetic Operators</strong></td></tr><tr><td>sum</td><td>addition</td></tr><tr><td>difference</td><td>subtraction</td></tr><tr><td>product</td><td>multiplication</td></tr><tr><td>ratio</td><td>division</td></tr><tr><td>power</td><td>exponentiation</td></tr><tr><td colspan="2"><strong>Unary Arithmetic Operators</strong></td></tr><tr><td>minus</td><td>unary minus</td></tr><tr><td colspan="2"><strong>Unary Transcendental Functions</strong></td></tr><tr><td>log</td><td>natural logarithm</td></tr><tr><td>exp</td><td>exponential</td></tr><tr><td>sin</td><td>sine</td></tr><tr><td>cos</td><td>cosine</td></tr><tr><td>tan</td><td>tangent</td></tr><tr><td>cot</td><td>cotangent</td></tr><tr><td>sinh</td><td>hyperbolic sine</td></tr><tr><td>cosh</td><td>hyperbolic cosine</td></tr><tr><td>tanh</td><td>hyperbolic tangent</td></tr><tr><td>coth</td><td>hyperbolic cotangent</td></tr><tr><td>sqrt</td><td>square root</td></tr></tbody></table>

In general, expressions are multidimensional sets with the special property that the range of each dimension starts from 1. The dimensionality size of an expression can be determined from the dimensionality sizes of its variables, constants and subexpressions and the type of its constituent operators, according to the rules given in the following tables:

<table><thead><tr><th colspan="3">Binary Arithmetic Operators</th></tr><tr><th>dimensionality<br>size of 1st operand</th><th>dimensionality<br>size of 2nd operand</th><th>dimensionality<br>size of result</th></tr></thead><tbody><tr><td>(s<sub>1</sub>,...,s<sub>n</sub>)</td><td>(s<sub>1</sub>,...,s<sub>n</sub>)</td><td>(s<sub>1</sub>,...,s<sub>n</sub>)</td></tr><tr><td>(1)</td><td>(s<sub>1</sub>,...,s<sub>n</sub>)</td><td>(s<sub>1</sub>,...,s<sub>n</sub>)</td></tr><tr><td>(s<sub>1</sub>,...,s<sub>n</sub>)</td><td>(1)</td><td>(s<sub>1</sub>,...,s<sub>n</sub>)</td></tr><tr><td>otherwise</td><td></td><td>illegal</td></tr></tbody></table>

<table><thead><tr><th colspan="2">Unary Operators and Functions</th></tr><tr><th>dimensionality<br>size of operand</th><th>dimensionality<br>size of result</th></tr></thead><tbody><tr><td>(s<sub>1</sub>,...,s<sub>n</sub>)</td><td>(s<sub>1</sub>,...,s<sub>n</sub>)</td></tr></tbody></table>

## A.2.5 Notes

1. *Variable occurrences in linear parts of constraints*

An important part of the characterisation of the linear part of a constraint is the information on which variables actually occur in it, and the coefficients that multiply each such variable.

In *ooOPS*, such occurrences are specified as a variable slice occurring in a constraint slice with a given coefficient. This simply means that:

*Every element of the variable slice occurs in each element of the constraint slice, always with the same coefficient.*

Of course, the client constructing an MINLP object using the facilities provided by *ooOPS* can add any number of such occurrences. Moreover, if any such specification involves an element of a variable vector that already appears<fnref n="1" /> in one or more of the specified constraints, the later specification overrides the earlier one.

<footnote n="1">¹as a result of earlier specifications</footnote>
2. *Variable occurrences in linear part of objective function*

An important part of the characterisation of the linear part of the objective function is the information on
which variables actually occur in it, and the coefficients that multiply each such variable.

In *ooOPS*, such occurrences are specified as a variable slice occurring in the objective function with a given coefficient. This simply means that:

*Every element of the variable slice occurs in the objective function always with the same coefficient.*

Of course, the client constructing an MINLP object using the facilities provided by *ooOPS* can add any number of such occurrences. Moreover, if any such specification involves an element of a variable vector that already appears<fnref n="2" /> in the objective function, the later specification overrides all earlier ones.

3. *Nonlinear expression occurrences in constraints*

An important part of the characterisation of a constraint is its nonlinear part. In *ooOPS*, this can be specified by assigning one or more expressions to different slices of the constraint. Each expression must either be a scalar or its dimensionality size must match that of the constraint slice to which it is assigned, in which case each element of the slice is set the corresponding the corresponding element of the expression.

Note that, unlike linear variable occurrences, expression elements do not accumulate. If a new expression is assigned to a constraint element which has already been assigned an expression, the later assignment overrides the earlier one.

4. *Nonlinear expression occurrences in objective function*

An important part of the characterisation of the objective function is its nonlinear part. In *ooOPS*, this is specified as a (scalar) expression occurring in the objective function.

Note that, unlike linear variable occurrences, expression elements do not accumulate. If a new expression is assigned to an objective function which has already been assigned an expression, the later assignment overrides the earlier one.

## A.3 General software issues

### A.3.1 Software constants

*ooOPS* defines two constants which should primarily be used for the specification of lower and upper bounds of variables, as well as constraint right hand side constants. These are:

* `ooOPSPlusInfinity`

Setting the upper bound of a variable to `PlusInfinity` implies that this variable is effectively unbounded from above.

Setting the upper bound of an inequality constraint to `PlusInfinity` is the standard way to represent an inequality of the form $c(x) \geq LB$.

* `ooOPSMinusInfinity`

Setting the lower bound of a variable to `MinusInfinity` implies that this variable is effectively unbounded from below.

Setting the lower bound of an inequality constraint to `MinusInfinity` is the standard way to represent an inequality of the form $c(x) \leq UB$.

### A.3.2 The *si*, *sd* and *li* Argument Types and the *IntSeq* Auxiliary Function

In order to describe the arguments to the various methods of its object classes, *ooOPS* introduces the following C++ type definition:

<footnote n="2">²as a result of earlier specifications</footnote>
* `si`: a sequence of integers

* `sd`: a sequence of doubles

* `li`: a list of integers

The precise implementation of this type is irrelevant as *ooOPS* also provides an auxiliary function for its construction. In particular, the `IntSeq` function takes a list of any number of integers and returns a vector of type `si`.

For example, the C++ code segment:

```cpp
si* SetSize = IntSeq (3,7,4);
```

creates a sequence called `SetSize` of three integers (3, 7 and 4). This may then, for instance, be passed as an input argument to a method to create a new 3-dimensional variable set, with the lengths of the three dimensions being specified in `SetSize`.

## A.4 The MINLP object class

### A.4.1 MINLP instantiation: the NewMINLP function

**Declaration:** `ops* NewMINLP()`

**Function:** Creates a new empty MINLP.

**Arguments to be specified by the client:** None

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>return value</td><td>ops*</td><td>the MINLP object</td></tr></tbody></table>

**Notes:** None

**Example of usage:**

The following creates a new MINLP called `NetOpt`:

```cpp
ops* NetOpt = NewMINLP();
```

### A.4.2 MINLP construction methods

#### A.4.2.1 Method NewContinuousVariable

**Declaration:** `void NewContinuousVariable(string vname, si* dimLB, si* dimUB, double LB, double UB, double value)`

**Function:** Creates a new set of continuous variables with given name, domain, bounds and value.

**Arguments to be specified by the client:**
<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>vname</td><td>string</td><td>name of variable set to be created</td></tr><tr><td>dimLB</td><td>si*</td><td>lower bounds of the variable set dimensions</td></tr><tr><td>dimUB</td><td>si*</td><td>upper bounds of the variable set dimensions</td></tr><tr><td>LB</td><td>double</td><td>lower bound</td></tr><tr><td>UB</td><td>double</td><td>upper bound</td></tr><tr><td>value</td><td>double</td><td>value</td></tr></tbody></table>

Arguments returned to client: None

Notes:

* The specified name must be unique among all variables (continuous or integer) in the MINLP as it will be used to identify the variable in all future communications with the MINLP object.

* In general, a variable is represented by a multidimensional set (cf. section A.2.2). The arguments `dimLB` and `dimUB` are sequences of integers, representing respectively the lower and upper bounds of the domains of the individual dimensions. In the case of the example of set X mentioned in section A.2.2, these two sequences would be (0, 1, -1) and (10, 5, 1) respectively.

* The length of the above integer sequences must be equal to each other and implicitly determine the number of dimensions of the variable.

* Scalar variables should be specified as 1-dimensional sets of size 1.

* The index of the individual elements for each dimension ranges from the corresponding element of `dimLB` to the corresponding element of `dimUB`.

* The specified lower bound, upper bound and value must satisfy:

$$LB \leq value \leq UB$$

* All elements of the variable set being created are given the same lower and upper bounds as well as the same value. However, these quantities may subsequently be changed for individual elements or slices of the set (see sections A.4.3.1 and A.4.3.2).

Example of usage:

The following creates a 2-dimensional continuous variable called `MaterialFlow`, with individual elements `MaterialFlow(i, j)`, `i = 0, .., 4`, `j = 1, .., 6` within an existing `ops` object called `NetOpt`. All elements of the new variable are initialised with a lower bound of 0.0, an upper bound of 100.0 and a current value of 1.0.

```java
NetOpt->NewContinuousVariable("MaterialFlow", IntSeq(0,1),
                             IntSeq(4,6), 0.0, 100.0, 1.0);
```

### A.4.2.2 Method NewIntegerVariable

**Declaration:** `void NewIntegerVariable(string vname, si* dimLB, si* dimUB, int LB, int UB, int value)`

**Function:** Creates a new set of integer variables with given name, size, bounds and value.

Arguments to be specified by the client:

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>vname</td><td>string</td><td>name of variable set to be created</td></tr><tr><td>dimLB</td><td>si*</td><td>lower bounds of the variable set dimensions</td></tr><tr><td>dimUB</td><td>si*</td><td>upper bounds of the variable set dimensions</td></tr><tr><td>LB</td><td>int</td><td>lower bound</td></tr><tr><td>UB</td><td>int</td><td>upper bound</td></tr><tr><td>value</td><td>int</td><td>value</td></tr></tbody></table>
**Arguments returned to client:** None

**Notes:**

* The specified name must be unique among all variables (continuous or integer) in the MINLP as it will be used to identify the variable in all future communications with the MINLP object.

* In general, a variable is represented by a multidimensional set (cf. section A.2.2). The arguments `dimLB` and `dimUB` are sequences of integers, representing respectively the lower and upper bounds of the domains of the individual dimensions. In the case of the example of set X mentioned in section A.2.2, these two sequences would be `(0, 1, -1)` and `(10, 5, 1)` respectively.

* The length of the above integer sequences must be equal to each other and implicitly determine the number of dimensions of the variable.

* Scalar variables should be specified as 1-dimensional sets of size 1.

* The index of the individual elements for each dimension ranges from the corresponding element of `dimLB` to the corresponding element of `dimUB`.

* The specified lower and upper bounds, and value must satisfy:

$$LB \leq value \leq UB$$

* All elements of the variable set being created are given the same lower and upper bounds as well as the same value. However, these quantities may subsequently be changed for individual elements or slices of the set (see sections A.4.3.1 and A.4.3.2).

**Example of usage:**

The following creates a 1-dimensional integer (binary) variable called `PlantExists` of length 3 with individual elements `PlantExists(i)`, `i = 1, .., 3` within an existing `ops` object called `NetOpt`. All elements of the new variable are initialised with a lower bound of 0, an upper bound of 1 and a current value of 0.

```python
NetOpt->NewIntegerVariable("PlantExists", IntSeq(1), IntSeq(3),
                         0, 1, 0);
```

### A.4.2.3 Method NewConstraint

**Declaration:** `void NewConstraint(string cname, si* dimLB, si* dimUB, double LB, double UB)`

**Function:** Creates a new set of constraints with given name, size, type and bounds.

**Arguments to be specified by the client:**

<table><thead><tr><th>Argument</th><th>Type</th><th>Specified On Entry</th></tr></thead><tbody><tr><td>cname</td><td>string</td><td>name of constraint set to be created</td></tr><tr><td>dimLB</td><td>si*</td><td>lower bounds of the constraint set dimensions</td></tr><tr><td>dimUB</td><td>si*</td><td>upper bounds of the constraint set dimensions</td></tr><tr><td>LB</td><td>double</td><td>lower bound</td></tr><tr><td>UB</td><td>double</td><td>upper bound</td></tr></tbody></table>

**Arguments returned to client:** None

**Notes:**

* The specified name must be unique among all constraints in the MINLP as it will be used to identify the constraint in all future communications with the MINLP object.
* In general, a constraint is represented by a multidimensional set (cf. note A.2.2 in section A.2.5). The arguments `dimLB` and `dimUB` are sequences of integers, representing respectively the lower and upper bounds of the domains of the individual dimensions. Their length must be equal and determine the number of dimensions of the constraint set.

* Scalar constraints should be specified as 1-dimensional sets of size 1.

* The index of the individual elements for each dimension ranges from the corresponding element of `dimLB` to the corresponding element of `dimUB`.

* All elements of the constraint set being created are assigned lower and upper bounds. However, these may subsequently be changed (see section A.4.3.3).

* Initially, the constraint does not contain any variables occurring linearly in it. It is also assigned a null nonlinear part.

**Example of usage:**

Creates a new constraint `UniqueAllocation` with bounds fixed at 1.

```c
NetOpt->NewConstraint("UniqueAllocation", IntSeq(1), IntSeq(1),
                     1.0, 1.0);
```

### A.4.2.4 AddLinearVariableSliceToConstraintSlice

**Declaration:**
```c
void AddLinearVariableSliceToConstraintSlice(string vname, si* vdimLB,
                                           si* vdimUB, string cname, si* cdimLB,
                                           si* cdimUB, double coefficient)
```

**Function:** Adds a linear occurrence of every element of a specified variable slice to each element of a specified constraint slice, always with the specified coefficient.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>vname</td><td>string</td><td>variable set, elements of which are to be added</td></tr><tr><td>vdimLB</td><td>si*</td><td>lower bounds of the variable set slice to be added to constraints</td></tr><tr><td>vdimUB</td><td>si*</td><td>upper bounds of the variable set slice to be added to constraints</td></tr><tr><td>cname</td><td>string</td><td>name of constraint set, elements of which are to receive the new variable occurrences</td></tr><tr><td>cdimLB</td><td>si*</td><td>lower bounds of the constraint set slice to receive variable occurrences</td></tr><tr><td>cdimUB</td><td>si*</td><td>upper bounds of the constraint set slice to receive variable occurrences</td></tr><tr><td>coefficient</td><td>double</td><td>coefficient of variables in the constraints</td></tr></tbody></table>

**Arguments returned to client:** None

**Notes:**

* The specified variable set must have already been created using the `NewContinuousVariable` or `NewIntegerVariable` methods (see sections A.4.2.1 and A.4.2.2 respectively).

* The specified constraint set must have already been created using the `NewConstraint` method (see section A.4.2.3).

* If an element of the variable slice has already been declared to occur in an element of constraint slice via an earlier invocation of this method, then the current specification supersedes the earlier one.
* A value of 0.0 for the specified coefficient has the effect of removing an existing occurrence of a variable in a constraint.

### Examples of usage:

The following creates a new inequality constraint called `SourceFlowLimit` within an existing `ops` object called `NetOpt` for each of the 5 source nodes in a network with a right hand side of 450. It then adds to the constraint for each node all the elements of the corresponding row of the variable `MaterialFlow` (cf. example in section A.4.2.1) with a coefficient of 1.

```java
NetOpt->NewConstraint("SourceFlowLimit",
                     IntSeq(0), IntSeq(4), '<', 450.0);
for (int i=0; i<=4; i++)
    NetOpt->AddLinearVariableSliceToConstraintSlice(
        "MaterialFlow", IntSeq(i,1), IntSeq(i,6),
        "SourceFlowLimit", IntSeq(i), IntSeq(i), 1.0);
```

The following adds an occurrence of all elements of the variable `PlantExists` (cf. example in section A.4.2.2) to the scalar constraint `UniqueAllocation` (cf. example in section A.4.2.3) within an existing `ops` object called `NetOpt`.

```java
NetOpt->AddLinearVariableSliceToConstraintSlice
    ("PlantExists", IntSeq(1), IntSeq(3),
     "UniqueAllocation", IntSeq(1), IntSeq(3), 1.0);
```

### A.4.2.5 Method NewConstant

**Declaration:** `void NewConstant(string kname, si* kdimLB, si* kdimUB, double value)`

**Function:** Creates a new constant set of specified dimensionality, each element of which is initialized to the specified value.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>kname</td><td>string</td><td>name of the constant set/slice being created</td></tr><tr><td>kdimLB</td><td>si*</td><td>lower bounds of constant set/slice</td></tr><tr><td>kdimUB</td><td>si*</td><td>upper bounds of constant set/slice</td></tr><tr><td>value</td><td>value</td><td>initial value</td></tr></tbody></table>

**Arguments returned to client:** None

**Notes:**

* None

### Examples of usage:

The following code creates a constant called `Const1` within an existing `ops` object called `NetOpt`, consisting of a three-dimensional vector whose components are all 1.

```java
NetOpt->NewConstant("Const1", IntSeq(1), IntSeq(3), 1);
```
### A.4.2.6 Method NewConstantExpression

**Declaration:** `void NewConstantExpression(string ename, string kname, si* kdimLB, si* kdimUB)`

**Function:** Creates a new expression consisting of a constant set or constant slice.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>ename</td><td>string</td><td>name of the expression being created</td></tr><tr><td>kname</td><td>string</td><td>name of the constant set/slice</td></tr><tr><td>kdimLB</td><td>si*</td><td>lower bounds of constant set/slice</td></tr><tr><td>kdimUB</td><td>si*</td><td>upper bounds of constant set/slice</td></tr></tbody></table>

**Arguments returned to client:** None

**Notes:**

* If an expression called `ename` already exists within the `ops` object, the new expression will overwrite it.

**Examples of usage:**

The following code creates an expression called `Expr1` (within an existing `ops` object called `NetOpt`) from the constant set `Const1`.

```java
NetOpt->NewConstant("Const1", IntSeq(1), IntSeq(3), 1);
NetOpt->NewConstantExpression("Expr1", "Const1",
                             IntSeq(1), IntSeq(3));
```

### A.4.2.7 Method NewVariableExpression

**Declaration:** `void NewVariableExpression(string ename, string vname, si* vdimLB, si* vdimUB*)`

**Function:** Creates a new expression consisting of a variable set or a variable slice.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>ename</td><td>string</td><td>name of the expression</td></tr><tr><td>vname</td><td>string</td><td>name of the variable set/slice</td></tr><tr><td>vdimLB</td><td>si*</td><td>lower bounds of the variable set/slice</td></tr><tr><td>vdimUB</td><td>si*</td><td>upper bounds of the variable set/slice</td></tr></tbody></table>

**Arguments returned to client:** None

**Notes:**

* If an expression called `ename` already exists within the `ops` object, the new expression will overwrite it.

**Examples of usage:**

The following code creates a variable expression called `Expr2` (within an existing `ops` object called `NetOpt`) consisting of the vector $(x_1, x_2, x_3)$.
NetOpt->NewContinuousVariable("x", IntSeq(1), IntSeq(3), -1, 1, 0);
NetOpt->NewVariableExpression("Expr2", "x", IntSeq(1), IntSeq(3));

### A.4.2.8 Method BinaryExpression

**Declaration:** void BinaryExpression(string ename, string enamel, si* edimLB1, si* edimUB1, string ename2, si* edimLB2, si* edimUB2, string binaryoperator)

**Function:** Creates a new expression representing a binary operation between the expressions specified in the argument.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>ename</td><td>string</td><td>name of the new expression</td></tr><tr><td>enamel</td><td>string</td><td>name of expression representing the first operand</td></tr><tr><td>edimLB1</td><td>si*</td><td>lower bound of slice to be used from first expression</td></tr><tr><td>edimUB1</td><td>si*</td><td>upper bound of slice to be used from first expression</td></tr><tr><td>ename2</td><td>string</td><td>name of expression representing the second operand</td></tr><tr><td>edimLB2</td><td>si*</td><td>lower bound of slice to be used from second expression</td></tr><tr><td>edimUB2</td><td>si*</td><td>upper bound of slice to be used from second expression</td></tr><tr><td>binaryoperator</td><td>string</td><td>label of the binary operator to be used.</td></tr></tbody></table>

**Arguments returned to client:** None

**Notes:**

* The dimensionality size of the new expression depends on those of its operands (see table in section A.2.4).

* The argument `binaryoperator` describes the type of binary operator in the expression. It can be one of the following strings: `sum`, `difference`, `product`, `ratio`, `power` (cf. section A.2.4).

* If an expression called `ename` already exists within the `ops` object, the new expression will overwrite it.

**Examples of usage:** The following code creates a nonlinear term $x_1x_2$ within an existing `ops` object called `NetOpt`.

NetOpt->NewContinuousVariable("x", IntSeq(1), IntSeq(2), -1, 1, 0);
NetOpt->BinaryExpression("NLT", "x", IntSeq(1), IntSeq(1), "x", IntSeq(2), IntSeq(2), "product");

### A.4.2.9 Method UnaryExpression

**Declaration:** void UnaryExpression(string ename, string enamel, si* edimLB1, si* edimUB1, string unaryoperator)

**Function:** Creates a new expression representing a unary operation on the expression specified in the argument.
Arguments to be specified by the client:

<table><thead><tr><th>Argument</th><th>Type</th><th>Specified On Entry</th></tr></thead><tbody><tr><td>ename</td><td>string</td><td>name of the new expression</td></tr><tr><td>ename1</td><td>string</td><td>name of expression</td></tr><tr><td>edimLB1</td><td>si*</td><td>representing the operand</td></tr><tr><td>edimUB1</td><td>si*</td><td>lower bound of slice to be used from the operand expression</td></tr><tr><td>unaryoperator</td><td>string</td><td>upper bound of slice to be used from the operand expression</td></tr><tr><td></td><td></td><td>label of the unary arithmetic operator or unary transcendental function to be used</td></tr></tbody></table>

Arguments returned to client: None

Notes:

* The dimensionality and dimension sizes of the new expression is the same as that of its operands.

* The argument unaryoperator describes the type of unary operator in the expression. It can be one of the following strings (the meaning is self-explanatory): "minus", "log", "exp", "sin", "cos", "tan", "cot", "sinh", "cosh", "tanh", "coth" (cf. section A.2.4).

* If an expression called ename already exists within the ops object, the new expression will overwrite it.

Examples of usage: The following code creates a nonlinear term log(*x*) within an existing ops object called NetOpt.

NetOpt->NewContinuousVariable("x", IntSeq(1), IntSeq(3), -1, 1, 0);
NetOpt->UnaryExpression("NLT", "x", IntSeq(1), IntSeq(3), "log");

### A.4.2.10 AssignExpressionSliceToConstraintSlice

**Declaration:** void AssignExpressionSliceToConstraintSlice (string ename, si* edimLB, si* edimUB, string cname, si* cdimLB, si* cdimUB)

**Function:** Assigns the specified expression slice to the specified constraint slice.

Arguments to be specified by the client:

<table><thead><tr><th>Argument</th><th>Type</th><th>Specified On Entry</th></tr></thead><tbody><tr><td>ename</td><td>string</td><td>the name of the expression to be set</td></tr><tr><td>edimLB</td><td>si*</td><td>lower bound of expression slice</td></tr><tr><td>edimUB</td><td>si*</td><td>upper bound of expression slice</td></tr><tr><td>cname</td><td>string</td><td>name of constraint set to which the expression must be set</td></tr><tr><td>cdimLB</td><td>si*</td><td>lower bounds of the constraint set slice to be set with the expression elements</td></tr><tr><td>cdimUB</td><td>si*</td><td>upper bounds of the constraint set slice to be set with the expression elements</td></tr></tbody></table>

Arguments returned to client: None

Notes:

* The specified constraint set must have already been created using the NewConstraint method (see section A.4.2.3).
* The specified expression either must be a scalar or its dimensionality size must match exactly that of the constraint slice. In the former case, the same scalar expression will be assigned to each of the constraints in the slice; in the latter, each element in the expression slice will be assigned to the corresponding element in the constraint slice.

**Examples of usage:**

The following code creates the term $\frac{x}{\log(x)}$ within an existing ops object called NetOpt and assigns it to the constraint UniqueAllocation.

```python
NetOpt->NewContinuousVariable("x", IntSeq(1), IntSeq(3), -1, 1, 0);
NetOpt->UnaryExpression("NLT", "x", IntSeq(1), IntSeq(3), "log");
NetOpt->BinaryExpression("NLT", "x",
                         IntSeq(1), IntSeq(3), "NLT",
                         IntSeq(1), IntSeq(3), "ratio");
NetOpt->AssignExpressionSliceToConstraintSlice
    ("NLT",                 IntSeq(1), IntSeq(3),
     "UniqueAllocation", IntSeq(1), IntSeq(3));
```

### A.4.2.11 Method NewObjectiveFunction

**Declaration:** `void NewObjectiveFunction(string oname, string otype)`

**Function:** Specifies the name and the type for the objective function for the MINLP.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>oname</td><td>string</td><td>objective function name</td></tr><tr><td>otype</td><td>string</td><td>objective function type</td></tr></tbody></table>

**Arguments returned to client:** None

**Notes:**

* The objective function created by this method does not contain any variables either linearly or nonlinearly.

* The type of the objective function must be a string of at least 3 characters; any characters beyond the third one are ignored. Valid type specifications are "min" and "max" denoting minimization and maximization respectively. The case of the characters in the type specification is irrelevant.

* If the method is invoked more than once for a given MINLP, then each invocation supersedes all earlier ones and any information associated with the previous objective function (e.g. on the variables occurring in it) is lost.

**Examples of usage:**

The following creates an objective function called TotalProfit within an existing ops object called NetOpt, that is to be maximized by the solution of the MINLP:

```python
NetOpt->NewObjectiveFunction("TotalProfit", "max");
```
### A.4.2.12 Method AddLinearVariableSliceToObjectiveFunction

**Declaration:** `void AddLinearVariableSliceToObjectiveFunction (string vname, si* dimLB, si* dimUB, double coefficient, string oname)`

**Function:** Adds a linear occurrence of every element of a specified variable slice to the specified objective function using the specified coefficient.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>vname</td><td>string</td><td>name of variable set, elements of which are to be added</td></tr><tr><td>dimLB</td><td>si*</td><td>lower bounds of the variable set slice to be added to objective function</td></tr><tr><td>dimUB</td><td>si*</td><td>upper bounds of the variable set slice to be added to objective function</td></tr><tr><td>coefficient</td><td>double</td><td>coefficient of variables in the objective function</td></tr><tr><td>oname</td><td>string</td><td>name of current objective function</td></tr></tbody></table>

**Arguments returned to client:** None

**Notes:**

* The specified variable set must have already been created using the `NewContinuousVariable` or `NewIntegerVariable` methods (see sections A.4.2.1 and A.4.2.2 respectively).

* If an element of the variable slice has already been declared to occur in the objective function via an earlier invocation of this method, then the current specification supersedes the earlier one.

* A value of 0.0 for the specified `coefficient` has the effect of removing an existing occurrence of a variable in a constraint.

* The specified objective function must be the current objective function which must have already been created using the `NewObjectiveFunction` method (see section A.4.2.11).

**Examples of usage:**

The following adds the elements of variables `MaterialFlow` (cf. example in section A.4.2.1) relating to destination node 1 to the objective function `TotalProfit` (cf. example in section A.4.2.11) within the existing `ops` object called `NetOpt`. A coefficient of 100 is used. It then subtracts from the same objective function the sum of the integer variables `PlantExists` (cf. example in section A.4.2.2) multiplied by a coefficient of -0.1:

```
NetOpt->AddLinearVariableSliceToObjectiveFunction
    ("MaterialFlow", IntSeq(0, 1), IntSeq(4,1),
     100.0, "TotalProfit");
NetOpt->AddLinearVariableSliceToObjectiveFunction
    ("PlantExists", IntSeq(1), IntSeq(3),
     -0.1, "TotalProfit");
```

### A.4.2.13 Method AssignExpressionToObjectiveFunction

**Declaration:** `void AssignExpressionToObjectiveFunction (string ename, string oname)`

**Function:** Sets the specified expression to the specified objective function.
Arguments to be specified by the client:

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>ename</td><td>string</td><td>expression to be set</td></tr><tr><td>oname</td><td>string</td><td>name of current objective function</td></tr></tbody></table>

Arguments returned to client: None

Notes:

* The specified objective function must be the current objective function which must have already been created using the `NewObjectiveFunction` method (see section A.4.2.11).

* The expression must be scalar.

Examples of usage:

The following code creates the scalar nonlinear term $x_1x_2$ and assigns it to the objective function `TotalProfit` within an existing `ops` object called `NetOpt`.

```
NewContinuousVariable("x", IntSeq(1), IntSeq(2), -1, 1, 0);
BinaryExpression("NLT", "x", IntSeq(1), IntSeq(1),
                "x", IntSeq(2), IntSeq(2), "product");
AssignExpressionToObjectiveFunction("NLT", "TotalProfit");
```

## A.4.3 MINLP modification methods

### A.4.3.1 Method SetVariableValue

**Declaration:** `void SetVariableValue(string vname, si* dimLB, si* dimUB, double value)`

**Function:** Sets the current value of the elements of a specified slice of a specified variable set, overriding their previous values.

Arguments to be specified by the client:

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>vname</td><td>string</td><td>name of variable set, elements of which are to be modified</td></tr><tr><td>dimLB</td><td>si*</td><td>lower bounds of the variable set slice to be modified</td></tr><tr><td>dimUB</td><td>si*</td><td>upper bounds of the variable set slice to be modified</td></tr><tr><td>value</td><td>double</td><td>new value for elements to be modified</td></tr></tbody></table>

Arguments returned to client: None

Notes:

* The specified variable set must have already been created using the `NewContinuousVariable` or `NewIntegerVariable` methods (see sections A.4.2.1 and A.4.2.2 respectively).

* The specified value must lie between the lower and upper bounds for every element of the specified variable slice.
### Examples of usage:

The following modifies all elements of the variable set `MaterialFlow` (cf. example in section A.4.2.1) pertaining to source 3 to a new value of 150:

SetVariableValue("MaterialFlow", IntSeq(3, 1), IntSeq(3, 6), 150.0);

### A.4.3.2 Method SetVariableBounds

**Declaration:** void SetVariableBounds(string vame, si* dimLB, si* dimUB, double LB, double UB)

**Function:** Sets the current lower and upper bounds of the elements of a specified slice of a specified variable set, overriding their previous values.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>vname</td><td>string</td><td>name of variable set, elements of which are to be modified</td></tr><tr><td>dimLB</td><td>si*</td><td>lower bounds of the variable set slice to be modified</td></tr><tr><td>dimUB</td><td>si*</td><td>upper bounds of the variable set slice to be modified</td></tr><tr><td>LB</td><td>double</td><td>new value of lower bound for elements to be modified</td></tr><tr><td>UB</td><td>double</td><td>new value of upper bound for elements to be modified</td></tr></tbody></table>

**Arguments returned to client:** None

**Notes:**

* The specified variable set must have already been created using the `NewContinuousVariable` or `NewIntegerVariable` methods (see sections A.4.2.1 and A.4.2.2 respectively).

* The specified bounds must satisfy $LB \le UB$.

### Examples of usage:

The following modifies the bounds of all elements of the variable set `MaterialFlow` (cf. example in section A.4.2.1) pertaining to source 3 to new values of 10 and 20 respectively:

SetVariableBounds("MaterialFlow", IntSeq(3, 1), IntSeq(3, 6), 10.0, 20.0);

The following sets both bounds of an element of the variable set `PlantExists` (cf. example in section A.4.2.2) to 1, thereby effectively fixing the value of this variable in any MINLP solution also to 1:

SetVariableBounds("PlantExists", IntSeq(2), IntSeq(2), 1.0, 1.0);
### A.4.3.3 Method SetConstraintBounds

**Declaration:** `void SetConstraintBounds(string cname, si* dimLB, si* dimUB, double LB, double UB)`

**Function:** Sets the lower and upper bounds of a specified slice of a specified constraint set, overriding any previous bounds.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>cname</td><td>string</td><td>name of constraint set, elements of which are to be modified</td></tr><tr><td>dimLB</td><td>si*</td><td>lower bounds of the constraint set slice to be modified</td></tr><tr><td>dimUB</td><td>si*</td><td>upper bounds of the constraint set slice to be modified</td></tr><tr><td>LB</td><td>double</td><td>new lower bound for elements to be modified</td></tr><tr><td>UB</td><td>double</td><td>new upper bound for elements to be modified</td></tr></tbody></table>

**Arguments returned to client:** None

**Notes:**

* The specified constraint set must have already been created using the `NewConstraint` method (see section A.4.2.3).

* The specified bounds must satisfy $LB \le UB$.

**Examples of usage:**

The following modifies the lower and upper bounds of constraint `UniqueAllocation` (cf. example in section A.4.2.3) to infinity:

```
SetConstraintBounds("UniqueAllocation", IntSeq(0), IntSeq(0),
                  MinusInfinity, PlusInfinity);
```

This modification effectively de-activates the `UniqueAllocation` constraint.

### A.4.3.4 Method SetConstantValue

**Declaration:** `void SetConstantValue(string kname, si* indexlist, double value)`

**Function:** Sets the value of the constant element pointed to by the specified index list to the specified value.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>kname</td><td>string</td><td>name of constant set containing the element to be modified</td></tr><tr><td>indexlist</td><td>si*</td><td>list of indices which point to the element to be modified</td></tr><tr><td>value</td><td>double</td><td>new value to be assigned to element</td></tr></tbody></table>

**Arguments returned to client:** None

**Notes:**
* The indices in the index list must lie between the respective index bounds defining the dimensionality of the constant set.

### A.4.3.5 Method SetConstantSliceValue

**Declaration:** `void SetConstantSliceValue(string kname, si* kdimLB, si* kdimUB, double value)`

**Function:** Sets the values of the constant elements in the specified slice to the specified value.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>kname</td><td>string</td><td>name of constant set containing the elements to be modified</td></tr><tr><td>kdimLB</td><td>si*</td><td>lower bounds of the constant set slice to be modified</td></tr><tr><td>kdimUB</td><td>si*</td><td>upper bounds of the constant set slice to be modified</td></tr><tr><td>value</td><td>double</td><td>new value to be assigned to elements</td></tr></tbody></table>

**Arguments returned to client:** None

**Notes:**

* None.

### A.4.3.6 Method SetKeyVariable

**Declaration:** `void SetKeyVariable(string vame, si* dimLB, si* dimUB)`

**Function:** Sets the elements of a specified slice of a specified variable set to be used as key variables for the decomposition algorithm.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>vname</td><td>string</td><td>name of variable set, elements of which are to be modified</td></tr><tr><td>dimLB</td><td>si*</td><td>lower bounds of the variable set slice to be modified</td></tr><tr><td>dimUB</td><td>si*</td><td>upper bounds of the variable set slice to be modified</td></tr></tbody></table>

**Arguments returned to client:** None

**Notes:**

* The specified variable set must have already been created using the `NewContinuousVariable` or `NewIntegerVariable` methods (see sections A.4.2.1 and A.4.2.2 respectively).

**Examples of usage:**

The following sets all elements of the variable set `MaterialFlow` (cf. example in section A.4.2.1) to be key variables:
SetKeyVariable("MaterialFlow", IntSeq(3, 1), IntSeq(3, 6));

The following sets an element of the variable set `PlantExists` (cf. example in section A.4.2.2) to be a key variable:

SetKeyVariable("PlantExists", IntSeq(2), IntSeq(2));

### A.4.4 Structured MINLP Information Access Methods

#### A.4.4.1 Method GetVariableInfo

**Declaration:** `void GetVariableInfo(string vname, si* dimLB, si* dimUB, double* value, double* LB, double* UB)`

**Function:** Returns the current values and lower and upper bounds of all elements of a specified slice of a specified set of variables.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>vname</td><td>string</td><td>name of variable set on which information is required</td></tr><tr><td>dimLB</td><td>si*</td><td>lower bounds of the variable set slice on which information is required</td></tr><tr><td>dimUB</td><td>si*</td><td>upper bounds of the variable set slice on which information is required</td></tr></tbody></table>

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Value on Exit</td></tr></thead><tbody><tr><td>value</td><td>double*</td><td>pointer to set of real numbers containing current values of elements in specified slice</td></tr><tr><td>LB</td><td>double*</td><td>pointer to set of real numbers containing lower bounds of elements in specified slice</td></tr><tr><td>UB</td><td>double*</td><td>pointer to set of real numbers containing upper bounds of elements in specified slice</td></tr></tbody></table>

**Notes:**

* The specified variable set must have already been created using the `NewContinuousVariable` or `NewIntegerVariable` methods (see sections A.4.2.1 and A.4.2.2 respectively).

* In the case of multidimensional variable sets, the information in the sets `value`, `LB` and `UB` is ordered so that the last index varies fastest, followed by the penultimate index, and so on until the first index which varies the most slowly. For example, a 2-dimensional set is ordered by rows.

**Examples of usage:**

The following returns the information on a slice of the variable `MaterialFlow` (cf. example in section A.4.2.1):

double* CurrentFlows;
double* MinimumFlows;
double* MaximumFlows ;

GetVariableInfo ("MaterialFlow", IntSeq(1,1), IntSeq(4,4), CurrentFlows, MinimumFlows, MaximumFlows) ;

### A.4.4.2 Method GetConstraintInfo

**Declaration:** bool GetConstraintInfo(string cname, si* dimLB, si* dimUB, double* LB, double* UB, double* LagMult)

**Function:** Returns the current values, lower and upper bounds and Lagrange multipliers of all elements of a specified slice of a specified constraint set; the return value is true if every element of the constraint slice is linear, or false otherwise.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>cname</td><td>string</td><td>name of constraint set on which information is required</td></tr><tr><td>dimLB</td><td>si*</td><td>lower bounds of the constraint set slice on which information is required</td></tr><tr><td>dimUB</td><td>si*</td><td>upper bounds of the constraint set slice on which information is required</td></tr></tbody></table>

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Value on Exit</td></tr></thead><tbody><tr><td>LB</td><td>double*</td><td>pointer to set of real numbers containing the upper bounds of elements in specified slice</td></tr><tr><td>UB</td><td>double*</td><td>pointer to set of real numbers containing the upper bounds of elements in specified slice</td></tr><tr><td>LagMult</td><td>double*</td><td>pointer to set of real numbers containing the Lagrange multipliers of elements in specified slice</td></tr><tr><td>return value</td><td>bool</td><td>true if constraint is linear</td></tr></tbody></table>

**Notes:**

* The return value is true if every element of the constraint is linear and false otherwise.

* The specified constraint set must have already been created using the NewConstraint method (see section A.4.2.3).

* In the case of multidimensional constraint sets, the information in the sets LB, UB and LagMult is ordered so that the last index varies fastest, followed by the penultimate index, and so on until the first index which varies the most slowly. For example, a 2-dimensional set is ordered by rows.

* If the Lagrange multiplier for a element of the specified slice is not available (e.g. because the MINLP has not yet been solved or because the MINLP solver does not make this information available), the a value of PlusInfinity (cf. section A.3.1) will be returned for the corresponding element of LagMult.

**Examples of usage:**

The following returns information on all elements of the constraint SourceFlowLimit (cf. example in section A.4.2.3):

char* CurrentType ;
double* CurrentUB ;
double* CurrentLM ;
bool isLinear ;

isLinear = GetConstraintInfo("SourceFlowLimit",
                             IntSeq(0), IntSeq(4),
                             CurrentType, CurrentUB, CurrentLM);

### A.4.4.3 Method GetObjectiveFunctionInfo

**Declaration:** `bool GetObjectiveFunctionInfo(string oname, char* otype, double& ovalue)`

**Function:** Returns the current value and type of the objective function specified by name; the "return value" is true if the constraint slice has an expression set to it, false otherwise.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>oname</td><td>string</td><td>name of objective function on which information is required</td></tr></tbody></table>

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Value on Exit</td></tr></thead><tbody><tr><td>otype</td><td>char*</td><td>pointer to set of characters containing the type of the objective function</td></tr><tr><td>ovalue</td><td>double&</td><td>value of the objective function</td></tr><tr><td>return value</td><td>bool</td><td>true if objective function is linear</td></tr></tbody></table>

**Notes:**

* The return value is `false` if the objective function has a nonlinear expression assigned to it and `true` otherwise.

* The specified objective function must have already been created using the `NewObjectiveFunction` method (see section A.4.2.11).

* The returned type of the objective function could be either `"min"` or `"max"`, denoting minimization and maximization respectively.

* The value of the objective function returned is based on the current values of the variables.

**Examples of usage:**

The following returns information on the objective function named `TotalProfit` (cf. example in section A.4.2.11):

char* CurrentObjType ;
double CurrentObjValue ;
bool isLinear;

isLinear = GetObjectiveFunctionInfo("TotalProfit", CurrentObjType, CurrentObjValue);
#### A.4.4.4 Method GetProblemInfo

**Declaration:** GetProblemInfo(string pname, bool& islinear, double& ovalue, bool& isfeasible)

**Function:** Returns the problem name, whether the problem is a MILP or a MINLP, the current recorded value of the objective function (as set by the last solver module that tried to solve the problem), and whether the problem is feasible or not (with respect to the current values of problem variables).

**Arguments to be specified by the client:** None.

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Value on Exit</td></tr></thead><tbody><tr><td>pname</td><td>string</td><td>name of the problem</td></tr><tr><td>islinear</td><td>bool&</td><td>true if problem is a MILP, false if it is a MINLP</td></tr><tr><td>ovalue</td><td>double&</td><td>value of the objective function</td></tr><tr><td>isfeasible</td><td>bool&</td><td>true if problem is feasible, false if it is not</td></tr></tbody></table>

**Notes:**

* The variable *ovalue* is *not* the value of the objective function calculated at the current variable values, but rather the value set by the solver module that last tried to solve this problem.

**Examples of usage:**

The following returns information on the problem.

string ProblemName;
bool MILP;
double ObjFunValue;
bool Feasible;

NetOpt->GetProblemInfo(ProblemName, MILP, ObjFunValue, Feasible);

## A.4.5 Flat MINLP Information Access Methods

Although it is convenient for client programs to construct *ops* objects in a structured manner using the methods of section A.4.2, most existing numerical solvers are designed to operate on the much simpler “flat” form [Flat MINLP] described in section A.1.

In view of the above, the *ops* interface provides a set of methods that allows access to the information characterising this flat representation. The latter is constructed automatically and efficiently by *ooOPS* in a manner that is transparent to the client.

### A.4.5.1 General Properties of the Flat MINLP

The flat MINLP generated by *ooOPS* has the following characteristics:

* The constraints in the flat MINLP comprise those elements of the constraint sets in the *ops* object that fulfill both of the following criteria:
- they have at least one variable occurring linearly with a non-zero coefficient, or a nonlinear part occurrence;

- at least one of the bounds is different from the respective infinity constant.

* The variables in the flat MINLP comprise those elements of the variable sets in the ops object that appear with a non-zero coefficient in at least one of the constraints and/or in the objective function in the flat MINLP (see above), or in the nonlinear parts of at least one constraint and/or the objective function.

### A.4.5.2 Method GetFlatMINLPSize

**Declaration:**
`void GetFlatMINLPSize(int& nv, int& niv, int& nlv, int& nliv, int& nc, int& nlc, int& nlz, int& nnz, int& nlzof, int& nnzof)`

**Function:** Returns information on the size of the flat MINLP.

**Arguments to be specified by the client:** None

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Value on Exit</td></tr></thead><tbody><tr><td><code>nV</code></td><td><code>int</code></td><td>total number of variables in flat MINLP</td></tr><tr><td><code>nIv</code></td><td><code>int</code></td><td>number of integer variables in flat MINLP</td></tr><tr><td><code>nlV</code></td><td><code>int</code></td><td>number of variables in flat MINLP which only appear linearly</td></tr><tr><td><code>nlIv</code></td><td><code>int</code></td><td>number of integer variables in flat MINLP which only appear linearly</td></tr><tr><td><code>nc</code></td><td><code>int</code></td><td>total number of constraints in flat MINLP</td></tr><tr><td><code>nlc</code></td><td><code>int</code></td><td>number of linear constraints in flat MINLP</td></tr><tr><td><code>nlz</code></td><td><code>int</code></td><td>number of non-zero elements in the matrix of flat MINLP (A in eqn. (A.2))</td></tr><tr><td><code>nnz</code></td><td><code>int</code></td><td>number of non-zero elements in the Jacobian matrix of the nonlinear constraints (f in eqn. (A.2))</td></tr><tr><td><code>nlzof</code></td><td><code>int</code></td><td>number of variables having non-zero coefficients in the linear part of the objective function of flat MINLP</td></tr><tr><td><code>nnzof</code></td><td><code>int</code></td><td>number of non-zero first order derivatives in the objective function of flat MINLP</td></tr></tbody></table>

**Notes:**

* The numbers of variables and constraints in the flat MINLP are determined using the rules detailed in section A.4.5.1.

* The number of variables nv includes both continuous and integer variables.

**Examples of usage:**

The following returns information on the size of a flat MINLP described by an existing ops object called `NetOpt`:

```
int NumberOfVariables                 ;
int NumberOfIntegerVariables          ;
int NumberOfLinearVariables          ;
int NumberOfLinearIntegerVars         ;
int NumberOfConstraints               ;
int NumberOfLinearConstraints         ;
```
```c
int NumberOfNZLinVarsInConstraints;
int NumberOfNZNonLinJacInConstraints;
int NumberOfNZLinVarsInObjFun;
int NumberOfNZNonLinJacInObjFun;
```

```c
NetOpt->GetFlatMINLPSize(&NumberOfVariables,
                          &NumberOfIntegerVariables,
                          &NumberOfLinearVariables,
                          &NumberOfLinearIntegerVariables,
                          &NumberOfConstraints,
                          &NumberOfLinearConstraints,
                          &NumberOfNZLinVarsInConstraints,
                          &NumberOfNZNonLinJacInConstraints,
                          &NumberOfNZLinVarsInObjFun,
                          &NumberOfNZNonLinJacInObjFun);
```

### A.4.5.3 Method GetFlatMINLPStructure

**Declaration:** `void GetFlatMINLPStructure(int* rowindex, int* columnindex, int* objindex, string structuretype)`

**Function:** Returns information on the sparsity structure of the objective function and the constraints. This corresponds to one of the following, depending on the request issued by the client:

1. the linear variable occurrences;

2. the jacobian elements occurrences;

3. the union of the preceding structures.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified on Entry</td></tr></thead><tbody><tr><td>structuretype</td><td>string</td><td>specifies whether returned structure should be of type (1), (2) or (3) (see above)</td></tr></tbody></table>

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Value on Exit</td></tr></thead><tbody><tr><td>rowindex</td><td>int*</td><td>pointer to set of integers containing the numbers of the constraints in the flat MINLP from which the nonzero elements originate</td></tr><tr><td>columnindex</td><td>int*</td><td>pointer to set of integers containing the numbers of the variables in the flat MINLP from which the nonzero elements in constraints originate</td></tr><tr><td>objindex</td><td>int*</td><td>pointer to set of integers containing the numbers of the variables in the flat MINLP from which the nonzero elements in the objective function originate</td></tr></tbody></table>

**Notes:**

* The input parameter `structuretype` must be one of the following strings: `"LINEAR"`, `"NONLINEAR"`, `"BOTH"` depending on whether the client needs the linear structure, the nonlinear structure or a union of both.
* The integer sets pointed at by `rowindex` and `columnindex` are both of length `nlz`, `nnz` or `nlz` + `nnz` (see section A.4.5.2) depending on whether `structuretype` is "LINEAR", "NONLINEAR" or "BOTH".

* The integer set pointed at by `objindex` is of length `nlzof`, `nnzof` or `nlzof` + `nnzof` (see section A.4.5.2) according as to whether `structuretype` is "LINEAR", "NONLINEAR" or "BOTH".

* Constraints and variables in the flat MINLP are numbered starting from 1.

* When calling with "BOTH" the linear and nonlinear vectors may be overlapping (i.e. there may be indices $i < j$ such that `rowindex[i] = rowindex[j]` and `columnindex[i] = columnindex[j]`, but the actual derivatives refer respectively to linear and nonlinear entries). For example, if the first flat problem constraint is $0 \le x_1^2 + 3x_1 \le 0$ then the linear derivatives matrix entry (1, 1) is 3, and the nonlinear derivatives matrix entry (1, 1) is $\frac{\partial x_1^2}{\partial x_1}$ evaluated at the current value of $x_1$. Thus the union of linear and nonlinear problem structure contains two entries for position (1, 1), but the first refers to the linear derivative and the second refers to the nonlinear derivative.

* The same is true for the objective function structure.

**Examples of usage:**

The following returns the linear structure of a flat MINLP described by an existing `ops` object called `NetOpt`:

```c
int* Rows;
int* Columns;
int* ObjFunColumns;
```

```c
NetOpt->GetFlatMINLPStructure(Rows, Columns,
                             ObjFunColumns, "LINEAR");
```

### A.4.5.4 Method GetFlatMINLPVariableInfo

**Declaration:** `void GetFlatMINLPVariableInfo(int vid, string& vname, si* &index, bool& isinteger, bool& islinear, double& value, double& LB, double& UB)`

**Function:** Returns information pertaining to a variable in the flat MINLP.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>vid</td><td>int</td><td>the number of the variable in the flat MINLP structure</td></tr></tbody></table>

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Value on Exit</td></tr></thead><tbody><tr><td>&vname</td><td>string</td><td>the name of the variable set from which this variable originates</td></tr><tr><td>&index</td><td>si*</td><td>the index of the variable in the variable set from which it originates</td></tr><tr><td>&isinteger</td><td>bool</td><td>true if the variable is of type integer false otherwise</td></tr><tr><td>&islinear</td><td>bool</td><td>true if the variable only appears linearly in the problem</td></tr><tr><td>&value</td><td>double</td><td>the current value of the variable</td></tr><tr><td>&LB</td><td>double</td><td>the lower bound of the variable</td></tr><tr><td>&UB</td><td>double</td><td>the upper bound of the variable</td></tr></tbody></table>

**Notes:**
* The variable number `vid` specified must be in the range 1,..., `nv` (see section A.4.5.2).

* Index holds a pointer to a sequence which is part of the MINLP's internal data and must not be altered in any way.

**Examples of usage:**

The following returns information on variable 375 in a flat MINLP described by an existing `ops` object called `NetOpt`:

```
string vname ;
si* index ;
bool isinteger ;
bool islinear ;
double value ;
double LB ;
double UB ;
```

```
NetOpt->GetFlatMINLPVariableInfo(375, vname, index, isinteger, islinear, value, LB, UB);
```

On return from `GetFlatMINLPVariableInfo`, variable `vname` could have the value `MaterialFlow` (cf. example in section A.4.2.1), `index` could be `(2, 4)`, `isinteger` could be `false`, and `value`, `LB` and `UB` could be 1, 0 and 100 respectively. Thus, we can deduce that variable 375 in the flat MINLP originated from the continuous variable `MaterialFlow` (2,4) in the original (structured) MINLP.

### A.4.5.5 Method SetFlatMINLPVariableBounds

**Declaration:** `void SetFlatMINLPVariableBounds(double* LB, double* UB)`

**Function:** Changes the lower and upper problem variable bounds.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified on Entry</td></tr></thead><tbody><tr><td>LB</td><td>double*</td><td>set of double precision numbers which will hold the new lower bounds</td></tr><tr><td>UB</td><td>double*</td><td>set of double precision numbers which will hold the new upper bounds</td></tr></tbody></table>

**Arguments returned to client:** None

**Notes:**

* The sets `LB` and `UB` have size `nv` (see section A.4.5.2).

**Examples of usage:**

The following reads the values of the problem variables described by an existing `ops` object called `NetOpt`:

```
double* vl = new double [nv];
double* vu = new double [nv];
for(int i = 0; i < nv; i++) {
    vl[i] = 0;
    vu[i] = 1;
}
NetOpt->SetFlatMINLPVariableBounds(vl, vu);
```
### A.4.5.6 Method GetFlatMINLPVariableValues

**Declaration:** `void GetFlatMINLPVariableValues(double* values)`

**Function:** Fills the set of double precision numbers passed to the function with the current values of the flat MINLP problem variables.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified on Entry</td></tr></thead><tbody><tr><td>values</td><td>double*</td><td>set of double precision numbers which will hold the variable values</td></tr></tbody></table>

**Arguments returned to client:** None

**Notes:**

* The set `values` has size `nv` (see section A.4.5.2).

**Examples of usage:**

The following sets the bounds of the problem variables described by an existing `ops` object called `NetOpt`:

```cpp
double* v = new double[nv];
NetOpt->GetFlatMINLPVariableValues(v);
```

### A.4.5.7 Method SetFlatMINLPVariableValues

**Declaration:** `void SetFlatMINLPVariableValues(double* values)`

**Function:** Sets the values of the flat MINLP variables.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified on Entry</td></tr></thead><tbody><tr><td>values</td><td>double*</td><td>set of double precision numbers holding the variable values to be set</td></tr></tbody></table>

**Arguments returned to client:** None

**Notes:**

* The set `values` has size `nv` (see section A.4.5.2).

**Examples of usage:**

The following sets the values of the problem variables described by an existing `ops` object called `NetOpt`:

```cpp
double* vv = new double[nv];
for (int i = 0; i < nv; i++)
    vv[i] = i / 2;
NetOpt->SetFlatMINLPVariableValues(vv);
```
### A.4.5.8 Method GetFlatMINLPConstraintInfo

**Declaration:** `void GetFlatMINLPConstraintInfo(int cid, string& cname, si* &index, double& LB, double& UB, si* &vlist, sd* &cflist, FlatExpression* &fe)`

**Function:** Returns information pertaining to a constraint in the flat MINLP.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>cid</td><td>int</td><td>the number of the constraint in the flat MINLP structure</td></tr></tbody></table>

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Value on Exit</td></tr></thead><tbody><tr><td>&cname</td><td>string</td><td>the name of the constraint set from which this constraint originates</td></tr><tr><td>&index</td><td>si*</td><td>the index of the constraint in the constraint set from which it originates</td></tr><tr><td>&LB</td><td>double</td><td>the current constraint lower bound</td></tr><tr><td>&UB</td><td>double</td><td>the current constraint upper bound</td></tr><tr><td>&vlist</td><td>si*</td><td>the vector of integers which contains the variable indices occuring in this constraint</td></tr><tr><td>&cflist</td><td>sd*</td><td>the vector of doubles which contains the coefficients of the variables occuring in this constraint</td></tr><tr><td>&fe</td><td>Flat-Expression*</td><td>an object which contains the symbolic information which defines the nonlinear part of the constraint (see section A.6.2)</td></tr></tbody></table>

**Notes:**

* The variable number `cid` specified must be in the range 1,...,nc (see section A.4.5.2).

* Index holds a pointer to a sequence which is part of the MINLP's internal data and must not be altered in any way.

* The argument `FlatExpression* &fe` contains the symbolic information which defines the nonlinear part of the constraint. For its description and usage see section A.6.2.

**Examples of usage:** The following returns information on constraint 532 in a flat MINLP described by an existing ops object called `NetOpt`:

```
string          cname      ;
si*            index      ;
double         LB        ;
double         UB        ;
si*            varList   ;
sd*            coefList   ;
FlatExpression* fe;
```

```
NetOpt->GetFlatMINLPConstraintInfo(532, cname, index, LB, UB, varList, coefList, fe)
```

On return from `GetFlatMINLPConstraintInfo`, variable `cname` could have the value `"SourceFlowLimit"` (cf. example in section A.4.2.4), `index` could be (3), and `UB` could be 450. Thus, we can deduce that constraint 532 in the flat MINLP originated from the constraint `SourceFlowLimit` (3) in the original (structured) MINLP.
### A.4.5.9 Method EvalFlatMINLPNonlinearObjectiveFunction

**Declaration:** double EvalFlatMINLPNonlinearObjectiveFunction(void)

**Function:** Returns the value of the nonlinear part of the objective function.

**Arguments to be specified by the client:** None

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>return value</td><td>double</td><td>the value of the objective function at the current variable values</td></tr></tbody></table>

**Notes:** None

**Examples of usage:**

The following sets the variable values and evaluates the objective function of the problem described by an existing `ops` object called `NetOpt`:

```c
double* vv = new double[nv];
for (int i = 0; i < nv; i++)
    vv[i] = i / 2;
NetOpt->SetFlagMINLPVariableValues(vv);
double vof = NetOpt->EvalFlatMINLPNonlinearObjectiveFunction();
```

### A.4.5.10 Method EvalFlatMINLPNonlinearConstraint

**Declaration:** void EvalFlatMINLPNonlinearConstraint(int lowercid, int uppercid, double* values)

**Function:** Returns the values of a range of nonlinear parts of constraints, starting with constraint `lowercid` up to and including constraint `uppercid` (also see (A.4.5.8)).

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>lowercid</td><td>int</td><td>the number of the first constraint of the range to be evaluated</td></tr><tr><td>uppercid</td><td>int</td><td>the number of the last constraint of the range to be evaluated</td></tr></tbody></table>

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Value on Exit</td></tr></thead><tbody><tr><td>values</td><td>double*</td><td>vector containing the constraint values</td></tr></tbody></table>

**Notes:**

* The vector `values` containing the values of the evaluated constraints, has size `uppercid` - `lowercid` + 1.

**Examples of usage:**

The following evaluates constraints 2-5 in the flat MINLP described by an existing `ops` object called `NetOpt`:
```c
double* cv = new double[4];
NetOpt->EvalFlatMINLPSNonlinearConstraint(cv, 2, 5);
```

### A.4.5.11 Method GetFlatMINLPObjectiveFunctionDerivatives

**Declaration:** `void GetFlatMINLPObjectiveFunctionDerivatives (double* A, string structuretype)`

**Function:** Returns a vector containing one of the following:

1. the values of the nonzero coefficients in the vector *c* defining the linear part of the objective function (cf. equation (A.1));

2. the values of the nonzero first order partial derivatives of the nonlinear part of the objective function evaluated at the current variable values;

3. the union of the preceding vectors.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified on Entry</td></tr></thead><tbody><tr><td>structuretype</td><td>string</td><td>specifies whether returned structure should be of type (1), (2) or (3) (see above)</td></tr></tbody></table>

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Value on Exit</td></tr></thead><tbody><tr><td>values</td><td>double*</td><td>pointer to set of doubles containing the nonzero elements of *c*, of the derivatives of the obj. fun., or both</td></tr></tbody></table>

**Notes:**

* The input parameter *structuretype* must be one of the following strings: `"LINEAR"`, `"NONLINEAR"`, `"BOTH"` depending on whether the client needs information about the linear part of the objective function, or the nonlinear part, or both.

* The length of this vector follows the rules given in note 3 to section A.4.5.3.

* The indices of the variables to which the elements of this vector correspond can be obtained from method `GetFlatMINLPStructure` as the integer vector `objindex` (see section A.4.5.3).

* When calling with `"BOTH"`, see notes on page 168.

**Examples of usage:**

The following returns the nonzero partial derivatives of the nonlinear part of the objective function of a flat MINLP described by an existing *ops* object called *NetOpt*, evaluated at the current variable values:

```c
int d0, d1, d2, d3, d4, d5, d6, d7, d8;
int nnzof;
NetOpt->GetFlatMINLPSize(&d0, &d1, &d2, &d3, &d4,
                          &d5, &d6, &d7, &8, &d9, &nnzof);
double* A = new double [nnzof];
NetOpt->GetFlatMINLPObjectiveFunctionDerivatives(A, "NONLINEAR");
```

In this case, $c(k)$, $k = 1,...,nnzof$ is the coefficient of variable `objindex(k)` in the objective function.
### A.4.5.12 Method GetFlatMINLPConstraintDerivatives

**Declaration:** `void GetFlatMINLPConstraintDerivatives(string structuretype, int lowercid, int uppercid, sd& values)`

**Function:** Returns a sequence of doubles (see section A.3.2) containing one of the following:

1. the values of the nonzero coefficient in the linear part of the specified constraints;

2. the values of the nonzero partial derivatives, evaluated at the current variable values, of the nonlinear parts of the specified constraints;

3. the union of the preceding vectors.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified on Entry</td></tr></thead><tbody><tr><td>structuretype</td><td>string</td><td>specifies whether returned structure should be of type (1), (2) or (3) (see above)</td></tr><tr><td>lowercid</td><td>int</td><td>specifies the lower end of the constraint range</td></tr><tr><td>uppercid</td><td>int</td><td>specifies the upper end of the constraint range</td></tr></tbody></table>

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Value on Exit</td></tr></thead><tbody><tr><td>values</td><td>sd&</td><td>sequence of doubles containing the nonzero elements of A, of the Jacobian of f, or both</td></tr></tbody></table>

**Notes:**

* The input parameter `structuretype` must be one of the following strings: `"LINEAR"`, `"NONLINEAR"`, `"BOTH"` according as to whether the client needs the linear part of the constraints, the derivatives, or a union of both.

* The length of this vector is given by `values.size()`.

* If `lowercid` and `uppercid` are both set to zero, then this function returns the nonzero coefficients of the entire matrix A (see equation (A.2)), or the nonzero coefficients of the entire Jacobian of f (see equation (A.2)) evaluated at the current variable values, or both, depending on `structuretype`. In this case this method effectively acts as though the whole range of problem constraints had been specified.

* The row and column indices of the elements of the vector can be obtained from method `GetFlatMINLP-Structure` as integer vectors `rowindex` and `columnindex` respectively (see section A.4.5.3).

* Nonlinear derivatives which are identically zero are not recorded. Thus, for example, if you have a linear constraint and you request its nonlinear derivatives, the vector `values` might be empty. Referring to elements of an empty vector results in runtime segmentation fault errors, so it is advisable to check `values.size()` before using the vector.

* When calling with `"BOTH"`, see notes on page 168.

**Examples of usage:**

The following returns the matrix A of a flat MINLP described by an existing ops object called `NetOpt`:

```
sd A;
NetOpt->GetFlatMINLPConstraintDerivatives(A, 0, 0, "LINEAR");
```

In this case, $A(k)$, $k=1,...,nlz$ is the coefficient of variable `columnindex(k)` in constraint `rowindex(k)` in the left hand side matrix A (cf. equation (A.2)).
### A.4.5.13 Method GetFlatMINLPNoPartitions

**Declaration:** `void GetFlatMINLPNoPartitions(int& np)`

**Function:** Returns the number of partitions of the flat MINLP.

**Arguments to be specified by the client:** None

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Value on Exit</td></tr></thead><tbody><tr><td>np</td><td>int</td><td>total number of partitions of flat MINLP</td></tr></tbody></table>

**Notes:**

* The number of partitions are determined based on the properties of key variables.

**Examples of usage:**

The following returns the number of partitions occurring in a flat MINLP described by an existing `ops` object called `NetOpt`:

`int np;`

`NetOpt->GetFlatMINLPNoPartitions(np);`

### A.4.5.14 Method GetFlatMINLPPartition

**Declaration:** `void GetFlatMINLPPartition(int& np, li* &varlist, li* &conlist)`

**Function:** Returns information on the partitions of the flat MINLP specified by its number.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>np</td><td>int</td><td>the number of the partition of the flat MINLP</td></tr></tbody></table>

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Value on Exit</td></tr></thead><tbody><tr><td>varlist</td><td>li</td><td>list of variable indices occurring in the partition</td></tr><tr><td>conlist</td><td>li</td><td>list of constraint indices occurring in the partition</td></tr></tbody></table>

**Notes:**

* The number `np` must be less or equal to the maximum number of partitions.

**Examples of usage:**

The following returns the variable and constraint lists of the partition 2 occurring in a flat MINLP described by an existing `ops` object called `NetOpt`:

`int np;`
li* variableList;
li* constraintList;

NetOpt->GetFlatMINLPPartition(np, variableList, constraintList);

### A.4.6 Standard Form MINLP Information Access Methods

A MINLP is in *standard form* when its nonlinear parts are reduced to their basic building blocks and all its linear parts are gathered together in a matrix. This is explained in more details in [116]. Suffice it here to recall the basics with an example. The constraint

$$-1 \le 4x_1 + 3x_2 - x_3 + \frac{x_1x_2}{\log(x_3)} \le 10$$

in standard form becomes

$$\begin{aligned}
-1 \le w_1 & \le 10 \\
w_1 &= 4x_1 + 3x_2 - x_3 + w_2 \\
w_2 &= \frac{w_3}{w_4} \\
w_3 &= x_1x_2 \\
w_4 &= \log(x_3)
\end{aligned}$$

The standard form of a MINLP is as follows:

$$\begin{array}{lll}
\min_{x} & x_i & \\
\qquad l \le & Ax & \le u \\
\qquad & y = & w \otimes z \\
\qquad x^L \le & x & \le x^U
\end{array}
\qquad (A.6)$$

where $y, w, z$ are subsets of $x \cup \mathbb{R}$ and $\otimes$ is any unary or binary operator.

In view of the above, the *ops* interface provides a set of methods that allows access to the information characterising this standard form representation. The latter is constructed automatically and efficiently by *ooOPS* in a manner that is transparent to the client.

#### A.4.6.1 Method GetSFNumberOfVariables

**Declaration:** void GetSFNumberOfVariables(int& nv, int& nzlv)

**Function:** It returns the total number of variables of the problem in standard form and the number of linearly appearing variables with nonzero coefficients in the linear part of the problem.

**Arguments to be specified by the client:** None

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Value On Exit</td></tr></thead><tbody><tr><td><code>nv</code></td><td><code>int&</code></td><td>the number of total problem variables</td></tr><tr><td><code>nzlv</code></td><td><code>int&</code></td><td>number of nonzero coeff. linear variables</td></tr></tbody></table>

**Notes:**

* The total number of problem variables includes the original problem variables and the variables which have been added by the standard form process.
**Examples of usage:**

```c
int nv;
int nzlv;
NetOpt->GetSFNumberOfVariables(nv, nzlv);
```

### A.4.6.2 Method GetSFVariableInfo

**Declaration:** `void GetSFVariableInfo(int vid, double value, double& LB, double& UB)`

**Function:** It returns the current variable value and the lower and upper bounds of variable vid in the problem in standard form.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified on Entry</td></tr></thead><tbody><tr><td>vid</td><td>int</td><td>variable id in the standard form problem</td></tr></tbody></table>

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Value On Exit</td></tr></thead><tbody><tr><td>value</td><td>double&</td><td>current variable value</td></tr><tr><td>LB</td><td>double&</td><td>variable lower bound</td></tr><tr><td>UB</td><td>double&</td><td>variable upper bound</td></tr></tbody></table>

**Notes:** None

**Examples of usage:**

```c
double value, LB, UB;
NetOpt->GetSFVariableInfo(1, value, LB, UB);
```

### A.4.6.3 Method GetSFObjFunVarIndex

**Declaration:** `void GetSFObjFunVarIndex(int& vid)`

**Function:** It returns the variable index (variable id) corresponding to the objective function.

**Arguments to be specified by the client:** None

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Value on Exit</td></tr></thead><tbody><tr><td>vid</td><td>int&</td><td>variable index corresponding to the objective function</td></tr></tbody></table>

**Notes:**

* As well as the constraints, the objective function of the MINLP is transformed by the standard form reduction, so that, for example, $\min x_1x_2$ would become $\min w_1$ s.t. $w_1 = x_1x_2$. In this case, the variable index of $w_1$ would be returned.

**Examples of usage:**
```c
int vid;
NetOpt->GetSFObjFunVarIndex(vid);
```

### A.4.6.4 Method GetSFNumberOfLinearConstraints

**Declaration:** `void GetSFNumberOfLinearConstraints(int& nlc)`

**Function:** This returns the number of linear constraints in the standard form of the problem.

**Arguments to be specified by the client:** None

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Value on Exit</td></tr></thead><tbody><tr><td>nlc</td><td>int&</td><td>number of linear constraints</td></tr></tbody></table>

**Notes:** None

* The number of linear constraints is equal to the number of rows in the matrix A in the general formulation of the standard form (see eqn. A.6 above).

**Examples of usage:**

```c
int nlc;
NetOpt->GetSFNumberOfLinearConstraints(nlc);
```

### A.4.6.5 Method GetSFLinearBounds

**Declaration:** `void GetSFLinearBounds(double* lb, double* ub)`

**Function:** It returns the vector of lower and upper bounds in the linear constraints of the standard form problem (l and u in the formulation A.6).

**Arguments to be specified by the client:** None

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Value on Exit</td></tr></thead><tbody><tr><td>lb</td><td>double*</td><td>vector of lower bounds</td></tr><tr><td>ub</td><td>double*</td><td>vector of upper bounds</td></tr></tbody></table>

**Notes:**

* The arrays lb and ub must be created by the client with the correct length nlc (use method GetSF-NumberOfLinearConstraints above).

**Examples of usage:**

```c
int nlc;
NetOpt->GetSFNumberOfLinearConstraints(nlc);
double* lb = new double[nlc];
double* ub = new double[nlc];
NetOpt->GetSFLinearBounds.lb, ub);
```
### A.4.6.6 Method GetSFLinearStructure

**Declaration:** `void GetSFLinearStructure(int* rowindex, int* columnindex)`

**Function:** Returns the sparsity structure of the linear part of the problem in standard form.

**Arguments to be specified by the client:** None

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Value on Exit</td></tr></thead><tbody><tr><td>rowindex</td><td>int*</td><td>vector of row indices</td></tr><tr><td>columnindex</td><td>int*</td><td>vector of column indices</td></tr></tbody></table>

**Notes:**

* The arrays `rowindex` and `columnindex` must be created by the client with the correct length `nzlv` (use method `GetSFNumberOfVariables` above).

**Examples of usage:**

```c
int nv;
int nzlv;
NetOpt->GetSFNumberOfVariables(nv, nzlv);
int* rowindex = new int[nzlv];
int* columnindex = new int[nzlv];
NetOpt->GetSFLinearStructure(rowindex, columnindex);
```

### A.4.6.7 Method GetSFMatrix

**Declaration:** `void GetSFMatrix(double* A)`

**Function:** Returns the linear part of the standard form problem in sparse format.

**Arguments to be specified by the client:** None

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Value on Exit</td></tr></thead><tbody><tr><td>A</td><td>double*</td><td>matrix A in sparse form</td></tr></tbody></table>

**Notes:**

* The array A must be created by the client with the correct length `nlzv` (use method `GetSFNumberOfVariables` above).

* The sparsity structure can be found with the method `GetSFLinearStructure` (A.4.6.6).

**Examples of usage:**

```c
int nv;
int nzlv;
NetOpt->GetSFNumberOfVariables(nv, nzlv);
double* A = new double[nzlv];
NetOpt->GetSFMatrix(A);
```
### A.4.6.8 Method GetSFNumberOfNonlinearConstraints

**Declaration:** `void GetSFNumberOfNonlinearConstraints(int& nnlc)`

**Function:** This returns the number of nonlinear constraints in the standard form of the problem.

**Arguments to be specified by the client:** None

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Value on Exit</td></tr></thead><tbody><tr><td>nnlc</td><td>int&</td><td>number of nonlinear constraints</td></tr></tbody></table>

**Notes:** None

* The number of nonlinear constraints is equal to the number of “constraint definitions” of the form $y = w \otimes z$ in the general formulation of the standard form (see eqn. A.6 above).

**Examples of usage:**

```cpp
int nnlc;
NetOpt->GetSFNumberOfNonlinearConstraints(nnlc);
```

### A.4.6.9 Method GetSFNonlinearConstraint

**Declaration:** `void GetSFNonlinearConstraint(int cid, int& vid, int& vid1, int& vid2, string& operator, double& constant1, double& constant2)`

**Function:** This function returns the elements of nonlinear standardized constraint number `cid` in the standard form of the problem.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified on Entry</td></tr></thead><tbody><tr><td>cid</td><td>int</td><td>standardized nonlinear constraint id</td></tr></tbody></table>

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Value on Exit</td></tr></thead><tbody><tr><td>vid</td><td>int&</td><td>left hand side variable id</td></tr><tr><td>vid1</td><td>int&</td><td>first right hand side variable id</td></tr><tr><td>vid2</td><td>int&</td><td>second right hand side variable id</td></tr><tr><td>operator</td><td>string&</td><td>operator type</td></tr><tr><td>constant1</td><td>double&</td><td>first left hand side constant</td></tr><tr><td>constant2</td><td>double&</td><td>second left hand side constant</td></tr></tbody></table>

**Notes:**

* The standard nonlinear constraint ID (`cid`) always starts from 1.

* In this discussion, we assume that each standard form nonlinear constraint has the form

$$variable = operand1 \otimes operand2$$

where *variable* is the “added variable” that is defined by the right hand side and the operator $\otimes$ is either unary or binary (if it is unary, then *operand2* is a dummy placeholder).
* `vid` is the variable id of *variable*.

* `vid1` is the variable id of `operand1` if the latter is a variable (e.g. $w_1 = x_1x_2$). If `operand1` is a constant then `vid1` is set to -1 (e.g. $w_2 = \frac{2}{x_3}$).

* `vid2` is the variable id of `operand2` if the latter is a variable and if $\otimes$ is a binary operator. If `operand2` is a constant (e.g. $w_3 = x_4^2$) or if $\otimes$ is unary then `vid2` is set to -1.

* `operator` represents the type of operator. It can be one of the following strings (the meaning is self-explanatory): `"sum", "difference", "product", "ratio", "power", "minus", "log", "exp", "sin", "cos", "tan", "cot", "sinh", "cosh", "tanh", "coth"` (cf. section A.2.4).

* `constant1` is meaningful only when `vid1` is set to -1.

* `constant2` is meaningful only when `vid2` is set to -1 and $\otimes$ is a binary operator.

* Note that in a problem in standard form the constraint id `cid` only applies to nonlinear standardized constraints and does not take into account linear constraints.

**Examples of usage:**

```c
int      cid = 1;
int      vid;
int      vid1;
int      vid2;
string   operat;
double   constant1;
double   constant2;
NetOpt->GetSFNonlinearConstraint, vid, vid1, vid2,
        operat, constant1, constant2);
```

### A.4.6.10 Method UpdateSolution

**Declaration:** `void UpdateSolution(double* sol)`

**Function:** This method is specifically designed to make it easy to insert the solution of the MINLP into both the structured and the flat form. In short, this method updates the variable values in both the structured and flat MINLP forms.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified on Entry</td></tr></thead><tbody><tr><td>sol</td><td>double</td><td>array of (flat) variable values</td></tr></tbody></table>

**Arguments returned to client:** None

**Notes:**

* The length of the array `sol` has to be at least `nv`, the number of variables in flat form (see section A.4.5.2).

* This method has been specifically designed to make it easy to update the solution in the MINLP at the end of a MINLP solver module, and is therefore targeted towards those programmers who wish to write their own solver module.

**Examples of usage:**

```c
double sol[nv];
NetOpt->UpdateSolution(&sol[0]);
```
# A.5 MINLP solvers and systems

## A.5.1 Introduction

Section A.4 of this document described in detail how ops objects can be constructed and modified, and how information in them can be accessed in both a structured and a flat form. This section is concerned with the solution of the mathematical problem described by an already existing ops object.

### A.5.1.1 MINLP solver managers and MINLP systems

The solution of an MINLP is normally effected by a numerical solver. There are commercial solvers (e.g. SNOPT) as well as non-commercial ones (e.g. DONLP2). A major objective for the *ooOPS* software is to provide application programs with a *uniform* interface to all such solvers. This is achieved by embedding each solver within a *opssolvermanager* object.

The main function of the Manager for a given MINLP Solver is the creation of *opssystem* objects (cf. section A.2.1) by combining an existing *ops* object with the numerical solver embedded within the Manager. It is this combination that ultimately permits the solution of the MINLP to take place.

### A.5.1.2 Algorithmic parameters for MINLP solvers

MINLP solvers of the kind of interest to *ooOPS* are sophisticated pieces of software. Although the basic algorithms implemented by different solvers are often very similar, the specific implementations may be significantly different. Moreover, the users of these solvers are normally provided with substantial flexibility in configuring the details of the behaviour of the implementation. This is typically achieved by setting the values of one or more *algorithmic parameters*. These are usually quantities of logical, integer, real or string type. Different MINLP solvers may recognise different sets of parameters; some typical examples include:

* The branching strategy to be used by branch-and-bound algorithms (e.g. depth-first, breadth-first, etc.).

* The maximum number of nodes to be examined during the branch-and-bound search.

* The maximum CPU time to be spent by the solution.

* The infeasibility tolerance within which constraints need to be satisfied.

Usually, MINLP solvers also incorporate a default value for each parameter. Although these values may lead to reasonably good performance for a wide range of applications, sophisticated users may wish to change them to suit the specific characteristics of particular applications.

*ooOPS* provides general mechanisms for handling algorithmic parameters that allows the client program (a) to determine the parameters a particular MINLP solver recognises, and their current values, and (b) to specify new values for one or more of these parameters. Parameter specification can operate at two levels:

* *At the Solver Manager level:* Specifying the value of a parameter in a *MINLPSolverManager* object ensures that any *opssystem* objects *subsequently* created from this *MINLPSolverManager* will, at least initially, have this value of the parameter.

* *At the MINLP System level:* Specifying the value of a parameter in a *opssystem* object affects this particular object only.

## A.5.2 The *ssolpar* and *sstat* argument types

In order to handle the passing of these different kinds of parameters, *ooOPS* introduces the following C++ type definitions:
* `variant`: a union containing a value which may be one of several different types

* `ssolpar`: a sequence of solver parameters

* `sstat`: a sequence of solution statistics

The following C++ type definitions, which are included in the `ops.h` header file supplied to the user describe these types fully:

```cpp
enum vtype {logical, integer, real, expression};
```

```cpp
struct variant {
    vtype thetype;
    union val {
        int    ival;
        double dval;
        string* sval;
        bool   bval;
    };
};
```

```cpp
struct solparameter {
    variant theval;
    string name;
    string description;
    double lowerbound;
    string upperbound;
};
```

```cpp
typedef vector<solparameter> ssolpar;
```

```cpp
struct statistic {
    variant theval;
    string description;
    string unit;
};
```

```cpp
typedef vector<statistic> sstat;
```

### A.5.3 MINLP Solver Manager Instantiation: The NewMINLPSolver-Manager Function

**Declaration:** `opssolvermanager* (*NewMINLPSolverManager)(void)`

**Function:** Creates a new `MINLPSolverManager` object incorporating a specified numerical code.

**Arguments to be specified by the client:** None

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>return value</td><td>opssolvermanager*</td><td>the ops solver manager incorporating the MINLP</td></tr></tbody></table>

**Notes:**

* This function is not available at compile time (hence it is only a pointer to a function). It is loaded from a shared object library at run time using the `dlopen()` / `dlsym()` mechanism. See example below for details.
* When using run time linking, keep in mind that search paths for shared object files vary from operating system to operating system and do not usually include the current working directory.

* Please be warned that shared object files produced from C++ source code have "mangled" symbol named which usually `dlopen` and `dlsym` cannot read properly. There are two solutions: first, write wrapper functions to `dlopen` and `dlsym` which take care of this problem; and second, use non-demangled symbol names (as in the example below).

* When writing a new solver manager for a particular solver code, the new solver manager has to expose the following function in the global namespace:

```c
opssolvermanager* NewMINLPSolverManager(void) {
    // ... code
    return new opssolvermanager_i();
}
```

Please use the provided template source files for the creation of new solver managers.

**Examples of usage:**

The following creates a new MINLP solver manager called `MySNOPTSolverManager` incorporating the SNOPT numerical MINLP solver:

```c
#include <dcfn.h>
opssolvermanager* (*NewMINLPSolverManager)(void);
opssolvermanager* MySNOPTSolverManager;
void* handle = dlopen("libopssnopt.so", RTLD_LAZY);
if (!handle) {
    cerr << "MAIN: shared object error: \n\t" << dlerror() << endl;
    exit(-1);
} else {
    // have to use "non-demangled" C++ symbol names
    void *tmp = dlsym(handle, "NewMINLPSolverManager__Fv");
    char* error;
    if ((error = dlerror()) != NULL) {
        cerr << "MAIN: shared object error: \n\t" << error << endl;
        exit(-1);
    }
    NewMINLPSolverManager = (opssolvermanager* (*)()) (tmp);
}
opssolvermanager* MySNOPTSolverManager = (*NewMINLPSolverManager)();
// ... code
dlclose(handle);
```

This manager can now be used to create one or more MINLP systems, each incorporating a separate `ops` object (see section A.5.4.3 below).

## A.5.4 MINLP solver managers

### A.5.4.1 Method GetParameterList

**Declaration:** `ssolpar* GetParameterList()`

**Function:** Gets the list of parameters with which a MINLPSystem can be configured. It returns a sequence of structures holding the current values of the parameters, their (single word) names and short descriptions, and valid
upper and lower bounds where applicable (the values `MinusInfinity` and `PlusInfinity` will be used to indicate unconstrained parameters).

The section A.5.2 for the detailed description of this type.

**Arguments to be specified by the client:** None

**Arguments returned to client:** None

**Examples of usage:**

The following retrieves the list of parameters for a solver:

```
ssolpar* params = SnoptManager->GetParameterList();
```

### A.5.4.2 Method SetParameter

**Declaration:** `void SetParameter(string ParamName, variant ParamValue)`

**Function:** Sets a specific parameter to configure a Solver Manager. Subsequent calls to `GetParameterList` will return the value supplied, and all `MINLPSystems` subsequently created will use the value supplied.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>ParamName</td><td>string</td><td>parameter name</td></tr><tr><td>ParamValue</td><td>variant</td><td>assigns a value to the parameter</td></tr></tbody></table>

**Arguments returned to client:** None

**Examples of usage:**

The following sets a parameter named `MaxRelaxations` to 100 in the Solver Manager `SnoptManager`:

```
variant var100;
var100.vtype=integer;
var100.val.ival=100;
SnoptManager->SetParameter("MaxRelaxations",var100);
```

### A.5.4.3 Method NewMINLPSystem

**Declaration:** `opssystem* NewMINLPSystem(const ops* theops)`

**Function:** Creates a new `opssystem` object from a given `ops` object.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>theops</td><td>const ops*</td><td>the ops object to be incorporated in the new opssystem</td></tr></tbody></table>

**Arguments returned to client:**
<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>return value</td><td>opssystem*</td><td>the ops system incorporating the MINLP and the numerical code</td></tr></tbody></table>

**Notes:**

* The specified `theops` object must already exist, having been created using the `NewMINLP` function (cf. section A.4.1 and the methods described in sections A.4.2 and A.4.3.

**Examples of usage:**

The following uses the MINLP solver manager object `SnoptManager` created in the example of section A.5.3 to create a new MINLP system, called `NetOptSnopt` incorporating the `ops` object `NetOpt` created in the example of section A.4.1:

`opssystem* NetOptSnopt = SnoptManager->NewMINLPSystem(NetOpt);`

## A.5.5 MINLP systems

### A.5.5.1 Method GetParameterList

**Declaration:** `ssolpar* GetParameterList()`

**Function:** Gets the list of parameters with which a MINLPSystem can be reconfigured after creation. It returns a sequence of structures holding the current values of the parameters, their (single word) names and short descriptions, and valid upper and lower bounds where applicable (the values `MinusInfinity` and `PlusInfinity` will be used to indicate unconstrained parameters).

See section A.5.2 for the detailed description of this type.

**Arguments to be specified by the client:** None

**Arguments returned to client:** None

**Examples of usage:**

The following retrieves the list of parameters for a system:

`ssolpar* params=NetOptSnopt->GetParameterList();`

### A.5.5.2 Method SetParameter

**Declaration:** `void SetParameter(string ParamName, variant ParamValue)`

**Function:** Sets a specific parameter to configure an MINLPSystem.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>ParamName</td><td>string</td><td>parameter name</td></tr><tr><td>ParamValue</td><td>variant</td><td>assigns a value to the parameter</td></tr></tbody></table>

**Arguments returned to client:** None
**Examples of usage:**

The following sets a parameter named `"DiagnosticsOutputFile"` to `"mydiag.out"` in the `MINLPSystem` `NetOptSnopt`:

```c
variant filename;
filename.vtype=string;
filename.val.sval="mydiag.out";
NetOptSnopt->SetParameter("DiagnosticsOutputFile",filename);
```

### A.5.5.3 Method GetStatistics

**Declaration:** `sstat* GetStatistics()`

**Function:** Gets the list of solution statistics which accumulate during the lifetime of the `MINLPSystem`. It returns a sequence of structures holding the current values of the statistics, their short descriptions, and units.

See section A.5.2 for the detailed description of this type.

**Arguments to be specified by the client:** None

**Arguments returned to client:** None

**Examples of usage:**

The following retrieves the statistics for a system and writes them to standard output, assuming the `C++ <<` operator has been suitably configured for the `variant` type.

```c
sstat* stats = NetOptSnopt->GetStatistics();
cout << "Solution statistics:" << endl;
for(sstat::const_iterator it = stats->begin();
    it != stats->end();
    it++)
    cout << "    " << it->description << ";"
    << it->theval << it->unit << endl;
```

The output produced might be:

```
Solution statistics:
CPU time: 233.23 seconds
Number of relaxations: 23
```

### A.5.5.4 Method Solve

**Declaration:** `void Solve()`

**Function:** Attempts to solve the MINLP problem incorporated in the `opssystem` object using the numerical MINLP solver embedded within the `opssystem` object.

**Arguments to be specified by the client:** None

**Arguments returned to client:** None

**Notes:**
* The numerical solution algorithm is applied to the “flat” form of the MINLP. The solver obtains the latter from the `ops` object incorporated within the `opssystem` object using the methods of section A.4.5. This operation is performed automatically and is completely transparent to the client.

* The solution procedure will leave the final values of variables and other information within the `ops` object. The client may subsequently retrieve them from there using the methods of section A.4.4.

### Examples of usage:

The following method invocation applied to the MINLP system `NetOptSnopt` created in the example of section A.5.4.3 will trigger the solution of the MINLP described by the `ops` object `NetOpt` using the SNOPT solver:

```
NetOptSnopt->Solve();
```

### A.5.5.5 Method `GetSolutionStatus`

**Declaration:** `void GetSolutionStatus(int& status)`

**Function:** Returns the exit status of the solver which attempted to solve the MINLP.

**Arguments to be specified by the client:** None

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>status</td><td>int&</td><td>exit status</td></tr></tbody></table>

**Notes:**

* This method only returns meaningful information after the method `Solve()` has been called.

### Examples of usage:

The following returns the exit status of the numerical solver (SNOPT) which just tried to solve the `NetOpt` problem

```c
int status;
NetOptSnopt->GetSolutionStatus(status);
if (status == 0)
    cout << "Solution OK!" << endl;
```

## A.6 Auxiliary interfaces

### A.6.1 The convexification module

This interface provides functionality for producing a convex relaxation of the MINLP. The `ooOPS` software provides a `convexifiermanager` object which embeds an existing `ops` object and provides only one public method, `Convexify()`, which returns an `ops` containing a convex flat MILP.

The “convexification” algorithm gets its input data from the MINLP in standard form (see section A.4.6) and produces a convex (linear) MILP. The output convex problem is embedded in a slightly modified version of the `ops` class (see section A.4) whose interface only offers flat form data access (see section A.6.1.4).
### A.6.1.1 Convexifier manager instantiation: the function NewConvexifierManager

**Declaration:** `convexifiermanager* (*NewConvexifierManager)(ops* theops)`

**Function:** Creates a new `convexifiermanager` object incorporating the MINLP `theops`.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>theops</td><td>ops*</td><td>the MINLP to be convexified</td></tr></tbody></table>

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>return value</td><td>convexifiermanager*</td><td>the convexifiermanager incorporating the MINLP</td></tr></tbody></table>

**Notes:**

* This function is not available at compile time (hence it is only a pointer to a function). It is loaded from a shared object library at run time using the `dlopen()` / `dlsym()` mechanism. See example below for details.

* When using run time linking, keep in mind that search paths for shared object files vary from operating system to operating system and do not usually include the current working directory.

* Please be warned that shared object files produced from C++ source code have "mangled" symbol named which usually `dlopen` and `dlsym` cannot read properly. There are two solutions: first, write wrapper functions to `dlopen` and `dlsym` which take care of this problem; and second, use non-demangled symbol names (as in the example below).

**Examples of usage:** The following creates a new `convexifiermanager` incorporating the MINLP `NetOpt`.

```c
#include <dcfn.h>
convexifiermanager* (*NewConvexifierManager)(ops*);
convexifiermanager* NetOptCM;
void* handle = dlopen("libopssnopt.so", RTLD_LAZY);
if (!handle) {
    cerr << "MAIN: shared object error: \n\t" << dlerror() << endl;
    exit(-1);
} else {
    // have to use "non-demangled" C++ symbol names
    void *tmp = dlsym(handle, "NewMINLPSolverManager__FP3ops");
    char* error;
    if ((error = dlerror()) != NULL) {
        cerr << "MAIN: shared object error: \n\t" << error << endl;
        exit(-1);
    }
    NetOptCM = (convexifiermanager*) (*)(ops*) (tmp);
}
// ... code
dlclose(handle);
```

### A.6.1.2 Method GetConvexMINLP

**Declaration:** `ops* GetConvexMINLP(void)`
**Function:** Returns a convex linear relaxation of the MINLP embedded in the *convexifiermanager*.

**Arguments to be specified by the client:** None

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>return value</td><td>ops*</td><td>the convex linear relaxation of the MINLP</td></tr></tbody></table>

**Notes:**

* The memory allocated by the returned convex linear problem should not be deallocated before the convexifiermanager object is deleted.

**Examples of usage:** The following returns a new *ops* object containing a convex linear relaxation of the MINLP.

```c
ops* myconvexops = NetOptCM->GetConvexMINLP();
```

### A.6.1.3 Method UpdateConvexVarBounds

**Declaration:** `void UpdateConvexVarBounds(double* lb, double* ub)`

**Function:** Updates the convex problem created with `GetConvexMINLP` (see A.6.1.2) with new variable bounds. Because of the way the convexification is done, this has the effect of changing some of the linear structure of the convex problem.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified On Entry</td></tr></thead><tbody><tr><td>lb</td><td>double*</td><td>new lower bounds of variables in the convex problem</td></tr><tr><td>ub</td><td>double*</td><td>new upper bounds of variables in the convex problem</td></tr></tbody></table>

**Arguments returned to client:** None

**Notes:**

* The convex problem created with `GetConvexMINLP` must not be deallocated prior to the call to this function.

**Examples of usage:** The following updates bounds to the first convex problem variable.

```c
// get convex problem
ops* myconvexops = NetOptCM->GetConvexMINLP();
// get convex problem size
int NumberOfVariables;
int NumberOfIntegerVariables;
int NumberOfLinearVariables;
int NumberOfLinearIntegerVars;
int NumberOfConstraints;
int NumberOfLinearConstraints;
int NumberOfNZLinVarsInConstraints;
int NumberOfNZNonLinJacInConstraints;
```
```c
int NumberOfNZLinVarsInObjFun;
int NumberOfNZNonLinJacInObjFun;
myconvexops->GetFlatMINLPSize(&NumberOfVariables,
                              &NumberOfIntegerVariables,
                              &NumberOfLinearVariables,
                              &NumberOfLinearIntegerVariables,
                              &NumberOfConstraints,
                              &NumberOfLinearConstraints,
                              &NumberOfNZLinVarsInConstraints,
                              &NumberOfNZNonLinJacInConstraints,
                              &NumberOfNZLinVarsInObjFun,
                              &NumberOfNZNonLinJacInObjFun);

// get convex problem variable bounds
double vlb = new double [NumberOfVariables];
double vub = new double [NumberOfVariables];
string strdummy;
si* sidummy;
bool bdummy1, bdummy2;
double ddummy;

for (int i = 1; i <= NumberOfVariables; i++) {
    myconvexops->GetFlatMINLPVariableInfo(i, strdummy, sidummy,
                                          bdummy1, bdummy2, ddummy,
                                          vlb[i - 1], vub[i - 1]);
}

// change first variable bounds
vlb[0] = vlb[0] - 1;
vub[0] = vub[0] + 1;

// update the convex problem
NetOptCM->UpdateConvexVarBounds(vlb, vub);
```

### A.6.1.4 Methods of the convex MILP

This is a cut-down version of the MINLP object interface (the ops class, see section A.4) which only offers functionality for reading/writing (linear) data in the flat form problem. This modified ops class offers no methods for dealing with (nonlinear) information, no multidimensional construction methods and no standard form methods.

The methods provided by this interface are:

* `GetFlatMINLPSize` (see A.4.5.2);

**Notes:** Call is the same as in section A.4.5.2.

* `GetFlatMINLPStructure` (see A.4.5.3);

**Notes:** Call is the same as in section A.4.5.3.

* `GetFlatMINLPVariableInfo` (see A.4.5.4);

**Notes:** The arguments `string vname`, `si* index`, `bool isinteger`, `bool islinear` are meaningless in this context and are only kept for compatibility<fnref n="3" />.

* `GetFlatMINLPConstraintInfo` (see A.4.5.8);

**Notes:** The arguments `string cname`, `si* index`, `si* cilist`, `sd* cflist`, `FlatExpression* fe` are meaningless in this context and are only kept for compatibility<fnref n="4" />.

<footnote n="3">³They can simply be skipped in the call.</footnote>

<footnote n="4">⁴They can simply be skipped in the call.</footnote>
* `GetFlatMINLPVariableValues` (see A.4.5.6);
  **Notes:** Call is the same as in section A.4.5.6.

* `SetFlatMINLPVariableValues` (see A.4.5.7);
  **Notes:** Call is the same as in section A.4.5.7.

* `SetFlatMINLPVariableBounds` (see A.4.5.5);
  **Notes:** Call is the same as in section A.4.5.5.

* `EvalFlatMINLPNonlinearObjectiveFunction` (see A.4.5.9);
  **Notes:** This is for compatibility only; it returns 0.

* `EvalFlatMINLPNonlinearConstraint` (see A.4.5.10);
  **Notes:** This is for compatibility only; it does not do anything.

* `GetFlatMINLPObjectiveFunctionDerivatives` — linear objective function only (see A.4.5.11);
  **Notes:** Call is the same as in section A.4.5.3.

* `GetFlatMINLPConstraintDerivatives` — linear constraints only (see A.4.5.12).
  **Notes:** Call is the same as in section A.4.5.3.

## A.6.2 The FlatExpression interface

This object class has the purpose of conveying symbolic flat expression information to the client. A `Flat-Expression` object is returned by the `GetFlatMINLPC constraintInfo` method (see section A.4.5.8) and is then transformed, according to its type, to any of the derived objects `FlatVariableExpression`, `Flat-ConstantExpression`, `FlatOperatorExpression`. Each of these objects provides a special interface used to access the encapsulated data.

The `FlatExpression` interface has only one method.

### A.6.2.0.1 Method GetKind

**Declaration:** `int GetKind()`

**Function:** Returns the kind of this `FlatExpression`.

**Arguments to be specified by the client:** None

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Value On Exit</td></tr></thead><tbody><tr><td>return value</td><td>int</td><td>kind of FlatExpression</td></tr></tbody></table>

**Notes:**

* The value returned by this method can be one of `FlatConstantType`, `FlatVariableType`, `Flat-OperatorType` according as to whether the current `FlatExpression` is respectively one of `Flat-ConstantExpression`, `FlatVariableExpression`, `FlatOperatorExpression`.

**Examples of usage:**

See below for a comprehensive example of all the methods relative to `FlatExpression`.
### A.6.2.1 The FlatConstantExpression interface

This object class is derived from the `FlatExpression` class and provides flat symbolic information about constant expression objects created with the `NewConstantExpression` method (see section A.4.2.6).

This interface has only one method.

#### A.6.2.1.1 Method GetValue

**Declaration:** `double GetValue()`

**Function:** Returns the value of the flat symbolic constant expression.

**Arguments to be specified by the client:** None

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Value On Exit</td></tr></thead><tbody><tr><td>return value</td><td>double</td><td>value of flat symbolic constant</td></tr></tbody></table>

**Notes:** None

**Examples of usage:**

See below for a comprehensive example of all the methods relative to `FlatExpression`.

### A.6.2.2 The FlatVariableExpression interface

This object class is derived from the `FlatExpression` class and provides flat symbolic information about variable expression objects created with the `NewVariableExpression` method (see section A.4.2.7).

This interface has only one method.

#### A.6.2.2.1 Method GetVarIndex

**Declaration:** `double GetVarIndex()`

**Function:** Returns the variable index (or variable id, a.k.a. `vid`) of the flat symbolic variable expression.

**Arguments to be specified by the client:** None

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Value On Exit</td></tr></thead><tbody><tr><td>return value</td><td>double</td><td>value of flat symbolic constant</td></tr></tbody></table>

**Notes:** None

**Examples of usage:**

See below for a comprehensive example of all the methods relative to `FlatExpression`.
### A.6.2.3 The FlatOperatorExpression interface

This object class is derived from the `FlatExpression` class and provides flat symbolic information about expression objects created with the `UnaryExpression` and `BinaryExpression` methods (see sections A.4.2.9 and A.4.2.8).

This interface has two methods.

#### A.6.2.3.1 Method GetOperator

**Declaration:** `int GetOperator()`

**Function:** Returns the operator type of the flat symbolic unary or binary expression.

**Arguments to be specified by the client:** None

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Value On Exit</td></tr></thead><tbody><tr><td>return value</td><td>int</td><td>operator type</td></tr></tbody></table>

**Notes:**

* The return function value describes the type of operator in the expression. It can be one of the following strings (the meaning is self-explanatory): `"sum"`, `"difference"`, `"product"`, `"ratio"`, `"power"`, `"minus"`, `"log"`, `"exp"`, `"sin"`, `"cos"`, `"tan"`, `"cot"`, `"sinh"`, `"cosh"`, `"tanh"`, `"coth"` (cf. section A.2.4).

**Examples of usage:**

See below for a comprehensive example of all the methods relative to `FlatExpression`.

#### A.6.2.3.2 Method GetOperand

**Declaration:** `FlatExpression* GetOperand(int eid)`

**Function:** Returns one of the operands of the flat symbolic unary or binary expression.

**Arguments to be specified by the client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Specified on Entry</td></tr></thead><tbody><tr><td>eid</td><td>int</td><td>the operand expression id</td></tr></tbody></table>

**Arguments returned to client:**

<table><thead><tr><td>Argument</td><td>Type</td><td>Value On Exit</td></tr></thead><tbody><tr><td>return value</td><td>FlatExpression*</td><td>flat symbolic operand expression</td></tr></tbody></table>

**Notes:**

* The operand expression id, `eid`, can only be 1 for unary expressions; it can be 1 or 2 for binary expressions.

* The return value is placed into an object of type `FlatExpression`. This can be analysed with the methods described in section A.6.2.