libMC is written in C++ and comes as a shared library. Given an elementary function, an interval, and a point inside the interval, libMC calculates upper and lower bounds (via natural interval extensions), convex and concave relaxations, and subgradients for these relaxations (via the forward mode) at that point. The operators for addition, subtraction, multiplication, and division are supported, as well as the standard exponential, logarithmic, power, square root, and absolute value intrinsic functions. Also supported as an intrinsic function is
which is convex on [0,+∞) and differentiable on (0,+∞). Note that monomials of odd degree, such as
, are treated as bilinear terms of the form
. Another important limitation of libMC is that it does not allows the user to choose among multiple possible subgradients.
Calculation of a McCormick Relaxation
Suppose we are interested in calculating the value of the McCormick relaxation of the real-valued function
for [-2,1]2, at the point (x,y)=(0,0).
First, the variables x and y are defined as
McCormick X( -2., 1., 0. );
McCormick Y( -2., 1., 0. );
Essentially, the first line means that X is a variable of class McCormick, that it belongs to the interval [-2,1], and that its current value is 0. The same holds for the McCormick variable Y. Once x and y$ have been defined, the McCormick convex and concave relaxations of f(x,y) at (0,0) are simply calculated as
McCormick Z = X*pow(exp(X)-Y,2);
In particular, the value of the McCormick convex underestimator and the McCormick concave overestimator of f(x,y) on [-2,1]2 at (0,0) are obtained as
double Zcvx = Z.cv();
double Zccv = Z.cc();
Likewise, a lower bound and an upper bound for the values of f(x,y) on [-2,1]2 are obtained as
double Zlb = Z.l();
double Zub = Z.u();
Calculation of a Subgradient of a McCormick Relaxation
The calculation of a subgradient of a McCormick relaxation requires that the number of variables be specified. For the previous example, the problem has two variables (x and y), so we shall define
McCormick::np(2);
Then, the variables x and y are declared as before, except that the component index is now specified for the variables. For example, if x and y are considered to be components 0 and 1, respectively, we write
McCormick X( -2., 1., 0., 0 );
McCormick Y( -2., 1., 0., 1 );
The McCormick convex and concave relaxations of f(x,y) at (0,0), as well as a subgradient of these relaxations, are simply calculated as
McCormick Z = X*pow(exp(X)-Y,2);
Finally, a subgradient of the McCormick convex underestimator of f(x,y) on [-2,1]2 at (0,0) is obtained as
const double* dZcvx = Z.dcvdp();
Alternatively, the components of this subgradient can be obtained separately as
double dZcvx_X = Z.dcvdp(0);
double dZcvx_Y = Z.dcvdp(1);
Analogously, a subgradient of the McCormick concave overestimator of f(x,y) on [-2,1]2 at (0,0) is obtained as
const double* dZccv = Z.dccdp();
double dZccv_X = Z.dccdp(0);
double dZccv_Y = Z.dccdp(1);
Note that whenever a McCormick relaxation is differentiable at a point, the components of the subgradient correspond to the partial derivatives of the relaxation at that point.
libMC comes with a set of test problems to illustrate usage and help the user understand how to build his own example problems. This set includes all the test problems reported in the paper [1]. The case studies in [2] are also based on libMC.