FICO Xpress Optimization Examples Repository
 FICO Optimization Community FICO Xpress Optimization Home

Maximizing the area of a polygon using a 'multimapdelta' userfunction

Description
Demonstrates how to solve a nonlinear problem in Java

Further explanation of this example: 'Xpress NonLinear Reference Manual'

Source Files
By clicking on a file name, a preview is opened at the bottom of this page.

PolygonMultiMapDelta.java

import com.dashoptimization.DefaultMessageListener;
import com.dashoptimization.IntHolder;
import com.dashoptimization.XPRSconstants;
import com.dashoptimization.XPRSenumerations.ObjSense;
import com.dashoptimization.XPRSprob;
import com.dashoptimization.XPRSprob.MultiMapDeltaFunction;

import java.util.ArrayList;

/** Code example that uses a user function of type "multimapdelta".
<pre>
Xpress Optimizer Examples
=========================

Maximize the area of polygon of N vertices and diameter of 1
The position of vertices is indicated as (rho,theta) coordinates
where rho denotes the distance to the base point
(vertex with number N) and theta the angle from the x-axis.

(c) 2021 Fair Isaac Corporation
</pre>

Polygon example: maximise the area of an N sided polygon

*** Demonstrating using a multimap (R^2-&gt;R^2) userfunction that computes its own derivatives ***

<pre>
Variables:

rho   : 0..N-1   ! Distance of vertex from the base point
theta : 0..N-1   ! Angle from x-axis

Objective:
(sum (i in 1..N-2) (rho(i)*rho(i-1)*sin(theta(i)-theta(i-1)))) * 0.5

Constraints:
Vertices in increasing degree order:
theta(i) >= theta(i-1) +.0001  : i = 1..N-2
Boundary conditions:
theta(N-1) <= Pi
0.1 <= rho(i) <= 1   : i = 0..N-2
Third side of all triangles <= 1
rho(i)^2 + rho(j)^2 - rho(i)*rho(j)*2*cos(theta(j)-theta(i)) <= 1    : i in 0..N-3, j in i..N-2
</pre>
*
* In this example we create a user function that takes two arguments and computes
* both the sine of the difference of its arguments and the cosine of the difference
* of its arguments. The user function also computes its derivatives.
*/

public final class PolygonMultiMapDelta {

/** User function that maps two doubles to two double.
* Computes <code>sin(x[0] - x[1])</code> and <code>cos(x[0] - x[1])</code>.
* It also fills in the partial derivatives if requested.
*/
private static double[] myTrigonometric(double[] value, double[] deltas, double[] partials) {
int nInput = 2;
// Assuming f:R^k->R^l, there will be a total of k*l derivatives,
// which must be written to the partials argument as:
//   diff(f1(x), x1), diff(f1(x), x2) ... diff(f1(x), xk)
//   diff(f2(x), x1), diff(f2(x), x2) ... diff(f1(x), xk)
//   ...
//   diff(fl(x), x1), diff(fl(x), x2) ... diff(fl(x), xk)

if (deltas != null) // Delta may be used as a suggestion for a finite difference step size
// however it also indicates if a partial is requested, saving on effort in case only an evaluation is needed
{
if (deltas[0] != 0.0)
{
partials[0 + 0] = Math.cos(value[0] - value[1]);
partials[nInput + 0] = -Math.sin(value[0] - value[1]);
}
if (deltas[1] != 0.0)
{
partials[0 + 1] = -Math.cos(value[0] - value[1]);
partials[nInput + 1] = Math.sin(value[0] - value[1]);
}
}

return new double[] {
Math.sin(value[0] - value[1]),
Math.cos(value[0] - value[1])
};
}

public static void main(String[] args) {
try (XPRSprob prob = new XPRSprob(null)) {

// Number of sides of the Polygon
int nSide = 5;

// Theta
int[] theta = prob.varArray('C', nSide - 1, 0.0, Math.PI,
i -> String.format("THETA%d", i + 1));
// Rho
int[] rho = prob.varArray('C', nSide - 1, 0.01, 1.0,
i -> String.format("RHO%d", i + 1));

// Add the user function. It takes 2 input arguments and produces
// two outputs and derivatives. This input/output counts mut be
// specified here.
MultiMapDeltaFunction trig = prob.nlpAddUserFunction("myTrigonometric", 2, 2, 0, PolygonMultiMapDelta::myTrigonometric);

// Objective function. We build the objective function as
// a formula in infix notation. See below for submitting a
// formula as string.
// Tokens are always integers, while values may be integers
// (for example operator or delimiter constants) or double
// values (actual numbers). That is why the val list has
// elements of type Number.
ArrayList<Integer> tok = new ArrayList<Integer>();
ArrayList<Number> val = new ArrayList<Number>();
for (int i = 1; i < nSide - 1; ++i) {
if ( tok.size() > 0 ) {
}
}
// Since nonlinear objectives cannot be directly expressed in Xpress, we maximize a free
// variable objx and constrain this variable to be equal to the nonlinear objective.
int objx = prob.addCol(1.0, XPRSconstants.MINUSINFINITY, XPRSconstants.PLUSINFINITY);
int objeq = prob.addRow(new int[]{objx}, new double[]{-1.0}, 'E', 0.0);
prob.nlpChgFormula(objeq, 0,
tok.stream().mapToInt(i -> i).toArray(),
val.stream().mapToDouble(d -> d.doubleValue()).toArray());
prob.chgObjSense(ObjSense.MAXIMIZE);

// Vertices in increasing degree order
for (int i = 0; i < nSide - 2; ++i)
new double[]{ -1.0, 1.0 },
'G',
0.001);

// Third side of all triangles <= 1
for (int i = 1; i < nSide - 1; i++) {
for (int j = i + 1; j < nSide; j++) {
int row = prob.addRow(new int[0], new double[0], 'L', 1.0);
prob.nlpChgFormulaStr(row,
String.format("RHO%d ^ 2 + RHO%d ^ 2 - RHO%d * RHO%d * 2 * myTrigonometric ( THETA%d , THETA%d : 2 )",
i, j, i, j, j, i));
}
}

IntHolder solvestatus = new IntHolder();
IntHolder solstatus = new IntHolder();
prob.optimize("s", solvestatus, solstatus);
System.out.printf("solvestatus: %s%n", solvestatus);
System.out.printf("solstatus:   %s%n", solstatus);
System.out.printf("Solution value: %f%n", prob.attributes().getObjVal());

double[] x = new double[prob.attributes().getCols()];
prob.getSolution(null, x, 0, x.length - 1);
for (int i = 0; i < rho.length; ++i)
System.out.printf("RHO%d = %f%n", i + 1, x[rho[i]]);
for (int i = 0; i < theta.length; ++i)
System.out.printf("THETA%d = %f%n", i + 1, x[theta[i]]);

}
}
}