Constraint types - Logical, general, SOS, quadratic

• Stating logic clauses that resemble SAT-type formulations (BoolVars).
• Formulating some constraints on the minimum and absolute values of linear combinations of variables (GeneralConstraints).
• Using the 'pwl' construct to formulate a piecewise linear cost function (PiecewiseLinear).
• Formulation of a small quadratic programming problem (QuadraticProgramming).
• Approximation of a nonlinear function by a special ordered set of type 2 (SpecialOrderedSets) and of a quadratic function in 2 variables by special ordered sets of type 2 (SpecialOrderedSetsQuadratic).

// (c) 2023-2024 Fair Isaac Corporation

import java.util.Arrays;
import java.util.Locale;

import com.dashoptimization.ColumnType;
import com.dashoptimization.XPRSenumerations;
import com.dashoptimization.objects.Variable;
import com.dashoptimization.objects.XpressProblem;

/** Stating logic clauses that resemble SAT-type formulations */
public class BoolVars {
    public static void main(String[] args) {
        final int R = 5;

        try (XpressProblem prob = new XpressProblem()) {
            // create boolean variables and their negations
            Variable[] x = prob.addVariables(R).withType(ColumnType.Binary).withName("x_%d").withUB(1).toArray();
            Variable[] xNeg = prob.addVariables(R).withType(ColumnType.Binary).withName("xNeg_%d").withUB(1).toArray();

            // add 2 helper variables for stating logical constraints
            Variable trueVar = prob.addVariable(0, 1, ColumnType.Binary, "TRUE");
            Variable falseVar = prob.addVariable(0, 1, ColumnType.Binary, "FALSE");

            // fix these helper variables to TRUE and FALSE, respectively.
            trueVar.fix(1);
            falseVar.fix(0);

            // add the complement relation between each binary variable and its negation.
            prob.addConstraints(R, r -> x[r].plus(xNeg[r]).eq(1));

            // add a direct equation constraint between certain variables.
            prob.addConstraint(x[2].eq(xNeg[3]));

            // express some clauses on the variables
            // require that x(0) and xNeg(4) = true
            // we use trueVar as the resultant of a logical "and" constraint
            prob.addConstraint(trueVar.andOf(new Variable[] { x[0], xNeg[4] }));

            // ! 'x(0) or x(2)' must be true
            prob.addConstraint(trueVar.orOf(new Variable[] { x[0], x[2] }));

            // for more complicated expressions, we need auxiliary variables.
            Variable andResultant1 = prob.addVariable(0, 1, ColumnType.Binary, "andresultant1");
            Variable andResultant2 = prob.addVariable(0, 1, ColumnType.Binary, "andresultant2");

            // both constraints below could be formulated using andResultant[12].AndOf(...)
            // here, however, we highlight the connection to general constraints
            // the first AND is between x[0] .. x[2]
            prob.addConstraint(andResultant1.andOf(Arrays.copyOfRange(x, 0, 3)));
            // the second AND is between xNeg[3] and xNeg[4]
            prob.addConstraint(andResultant2.andOf(Arrays.copyOfRange(xNeg, 3, xNeg.length)));

            // add those two individual AND resultants by requiring at least one to be
            // satisfied
            prob.addConstraint(trueVar.orOf(new Variable[] { andResultant1, andResultant2 }));

            // finally, add a constraint that none of xNeg[0 .. 2] should be true
            prob.addConstraint(falseVar.orOf(Arrays.copyOfRange(xNeg, 0, 3)));

            // write the problem in LP format for manual inspection
            System.out.println("Writing the problem to 'BoolVars.lp'");
            prob.writeProb("BoolVars.lp", "l");

            // Solve the problem
            System.out.println("Solving the problem");
            prob.optimize();

            // check the solution status
            System.out.println("Problem finished with SolStatus " + prob.attributes().getSolStatus());
            if (prob.attributes().getSolStatus() != XPRSenumerations.SolStatus.OPTIMAL) {
                throw new RuntimeException("Problem not solved to optimality");
            }

            // print the solution of the problem to the console
            System.out.printf(Locale.US, "Solution has objective value (profit) of %g%n",
                    prob.attributes().getObjVal());
            System.out.println("");
            System.out.println("*** Solution ***");
            double[] sol = prob.getSolution();

            for (int r = 0; r < R; r++) {
                String delim = r < R - 1 ? ", " : "\n";
                System.out.printf(Locale.US, "x_%d = %g%s", r, x[r].getValue(sol), delim);
            }

            for (int r = 0; r < R; r++) {
                String delim = r < R - 1 ? ", " : "\n";
                System.out.printf(Locale.US, "xNeg_%d = %g%s", r, xNeg[r].getValue(sol), delim);
            }

            System.out.println("");
        }
    }
}

// (c) 2023-2024 Fair Isaac Corporation

import static com.dashoptimization.objects.Utils.sum;

import java.util.Locale;

import com.dashoptimization.XPRSenumerations;
import com.dashoptimization.objects.Expression;
import com.dashoptimization.objects.Variable;
import com.dashoptimization.objects.XpressProblem;

/**
 * A simple example that formulates some constraints on the minimum and absolute
 * values of linear combinations of variables.
 */
public class GeneralConstraints {
    public static void main(String[] args) {
        System.out.println("Formulating the general constraint example problem");

        final int R = 3;

        try (XpressProblem prob = new XpressProblem()) {
            Variable[] x = prob.addVariables(R).withName("x_%d").withUB(20).toArray();

            Variable y = prob.addVariable("y");
            Variable z = prob.addVariable("z");

            Expression objective = sum(x);

            // We want to formulate abs(x(0)-2*x(1)) <= 10. We need to introduce
            // two auxiliary variables for the argument of the abs function
            // and then break down the abs expression in multiple steps
            Variable diff1 = prob.addVariable("diff1");
            Variable absOfDiff1 = prob.addVariable("absOfDiff1");

            prob.addConstraint(diff1.eq(x[0].minus(x[1].mul(2))));
            prob.addConstraint(absOfDiff1.absOf(diff1));
            prob.addConstraint(absOfDiff1.leq(10));

            // We link a new variable to the minimum of the x(i) and
            // require this variable to be >= 5
            // Clearly, this bound constraint could also be achieved by simply setting
            // the bounds of each x variable.
            Variable minOfX = prob.addVariable("minOfX");
            prob.addConstraint(minOfX.minOf(x));
            prob.addConstraint(minOfX.geq(5));

            // We link variable y to the maximum of other variables, expressions, and
            // constants
            // y = max(x(2), 20, x(0)-z)
            Variable diff2 = prob.addVariable("diff2");
            prob.addConstraint(diff2.eq(x[0].minus(z)));

            // the below code is equivalent to using the MaxOf function on the resultant y
            // prob.addConstraint(y.MaxOf(new Variable[] {x[2], diff2},
            // 20).setName("max_constraint"));
            prob.addConstraint(y.maxOf(new Variable[] { x[2], diff2 }, new double[] { 20 }, "max_constraint"));

            // set objective function with a maximization sense
            prob.setObjective(objective, XPRSenumerations.ObjSense.MAXIMIZE);

            // write the problem in LP format for manual inspection
            System.out.println("Writing the problem to 'GeneralConstraints.lp'");
            prob.writeProb("GeneralConstraints.lp", "l");

            // Solve the problem
            System.out.println("Solving the problem");
            prob.optimize();

            // check the solution status
            System.out.println("Problem finished with SolStatus " + prob.attributes().getSolStatus());
            if (prob.attributes().getSolStatus() != XPRSenumerations.SolStatus.OPTIMAL) {
                throw new RuntimeException("Problem not solved to optimality");
            }

            // print the optimal solution of the problem to the console
            System.out.printf(Locale.US, "Solution has objective value (profit) of %g%n",
                    prob.attributes().getObjVal());
            System.out.println("");
            System.out.println("*** Solution ***");
            double[] sol = prob.getSolution();

            for (int r = 0; r < R; r++) {
                String delim = r < R - 1 ? ", " : "\n";
                System.out.printf(Locale.US, "x_%d = %g%s", r, x[r].getValue(sol), delim);
            }
            System.out.printf(Locale.US, "y = %g, z = %g%n", y.getValue(sol), z.getValue(sol));
            System.out.printf(Locale.US, "ABS ( x[0] - 2*x[1] ) = %g, minOfX = %g%n", absOfDiff1.getValue(sol),
                    minOfX.getValue(sol));

            System.out.println("");
        }
    }
}

// (c) 2023-2024 Fair Isaac Corporation

import java.util.Locale;

import com.dashoptimization.PwlBreakpoint;
import com.dashoptimization.XPRSenumerations;
import com.dashoptimization.objects.Expression;
import com.dashoptimization.objects.Variable;
import com.dashoptimization.objects.XpressProblem;

/**
 * An example that demonstrates how to model a piecewise linear cost function. A
 * piecewise linear cost function f(x) assigns a different linear cost function
 * for different intervals of the domain of its argument x. This situation
 * occurs in real-world problems if there are price discounts available starting
 * from a certain quantity of sold goods.
 *
 * - Example discussed in mipformref whitepaper -
 */
public class PiecewiseLinear {
    public static void main(String[] args) {
        System.out.println("Formulating the piecewise linear example problem");

        try (XpressProblem prob = new XpressProblem()) {
            Variable x = prob.addVariable("x");
            Variable fx = prob.addVariable("fx");
            Expression objective = fx;

            double[] BREAKPOINT_X = // the breakpoints x values
                    { 0, 50, 50, 120, 120, 200 };

            double[] BREAKPOINT_Y = // the breakpoints y values
                    { 0, 50, 75, 180, 240, 400 };

            // Create the break points from the x,y data
            PwlBreakpoint[] breakpoints = new PwlBreakpoint[BREAKPOINT_X.length];
            for (int i = 0; i < breakpoints.length; ++i)
                breakpoints[i] = new PwlBreakpoint(BREAKPOINT_X[i], BREAKPOINT_Y[i]);

            // add the piecewise linear constraints with the breakpoints
            prob.addConstraint(fx.pwlOf(x, breakpoints, "pwl_with_breakpoints"));

            // ! Add a lower bound on x to get a somewhat more meaningful model
            // x >= 150
            x.setLB(150);

            // set objective function with a minimization sense
            prob.setObjective(objective, XPRSenumerations.ObjSense.MINIMIZE);

            // write the problem in LP format for manual inspection
            System.out.println("Writing the problem to 'PiecewiseLinear.lp'");
            prob.writeProb("PiecewiseLinear.lp", "l");

            // Solve the problem
            System.out.println("Solving the problem");
            prob.optimize();

            // check the solution status
            System.out.println("Problem finished with SolStatus " + prob.attributes().getSolStatus());
            if (prob.attributes().getSolStatus() != XPRSenumerations.SolStatus.OPTIMAL) {
                throw new RuntimeException("Problem not solved to optimality");
            }

            // print the optimal solution of the problem to the console
            System.out.printf(Locale.US, "Solution has objective value (profit) of %g%n",
                    prob.attributes().getObjVal());
            System.out.println("");
            System.out.println("*** Solution ***");
            double[] sol = prob.getSolution();

            System.out.printf(Locale.US, "x = %g, fx = %g%n", x.getValue(sol), fx.getValue(sol));

            System.out.println("");
        }
    }
}

// (c) 2023-2024 Fair Isaac Corporation

import static com.dashoptimization.objects.Utils.sum;

import com.dashoptimization.ColumnType;
import com.dashoptimization.DefaultMessageListener;
import com.dashoptimization.XPRSenumerations.LPStatus;
import com.dashoptimization.XPRSenumerations.ObjSense;
import com.dashoptimization.objects.QuadExpression;
import com.dashoptimization.objects.Variable;
import com.dashoptimization.objects.XpressProblem;

/**
 * Small Quadratic Programming example.
 *
 * <pre>
 *   minimize x1 + x1^2 +2x1x2 +2x2^2 +x4^2
 *   s.t.
 *     C1:  x1 +2x2 -4x4 &gt;= 0
 *     C2: 3x1 -2x3 - x4 &lt;= 100
 *     C3: 10 &lt;= x1 +3x2 +3x3 -2x4 &lt;= 30
 *     0 &lt;= x1 &lt;= 20
 *     0 &lt;= x2,x3
 *     x4 free
 * </pre>
 */
public class QuadraticProgramming {
    static final int N = 4;

    public static void main(String[] args) {
        try (XpressProblem prob = new XpressProblem()) {
            QuadExpression obj;
            Variable[] x;

            prob.callbacks.addMessageCallback(DefaultMessageListener::console);

            ///// VARIABLES
            x = new Variable[N];
            x[0] = prob.addVariable(0, 20, ColumnType.Continuous, "x1");
            x[1] = prob.addVariable("x2");
            x[2] = prob.addVariable("x3");
            x[3] = prob.addVariable(Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, ColumnType.Continuous, "x4");

            ///// OBJECTIVE
            obj = QuadExpression.create();
            obj.addTerm(x[0], 1);
            obj.addTerm(x[0].mul(x[0]));
            obj.addTerm(x[0], x[1], 2);
            obj.addTerm(x[1].mul(x[1]).mul(2));
            obj.addTerm(x[3].square());
            prob.setObjective(obj, ObjSense.MINIMIZE);

            ///// CONSTRAINTS
            prob.addConstraint(sum(x[0], x[1].mul(2), x[3].mul(-4)).geq(0).setName("C1"));
            prob.addConstraint(sum(x[0].mul(3), x[2].mul(-2), x[3].mul(-1)).leq(100).setName("C2"));

            prob.addConstraint(sum(x[0], x[1].mul(3), x[2].mul(3), x[3].mul(-2)).in(10, 30).setName("C3"));

            ///// SOLVING + OUTPUT
            prob.writeProb("qp.lp");
            prob.lpOptimize();

            System.out.println("Problem status: " + prob.attributes().getMIPStatus());
            if (prob.attributes().getLPStatus() != LPStatus.OPTIMAL)
                throw new RuntimeException("optimization failed with status " + prob.attributes().getLPStatus());

            System.out.println("Objective function value: " + prob.attributes().getObjVal());
            double[] sol = prob.getSolution();
            for (int i = 0; i < N; i++)
                System.out.print(x[i].getName() + ": " + x[i].getValue(sol) + ", ");
            System.out.println();
        }
    }
}

// (c) 2023-2024 Fair Isaac Corporation

import static com.dashoptimization.objects.SOS.sos2;
import static com.dashoptimization.objects.Utils.scalarProduct;
import static com.dashoptimization.objects.Utils.sum;

import java.util.Locale;

import com.dashoptimization.XPRSenumerations;
import com.dashoptimization.objects.Variable;
import com.dashoptimization.objects.XpressProblem;

/**
 * Approximation of a nonlinear function by a special ordered set (SOS-2). An
 * SOS-2 is a constraint that allows at most 2 of its variables to have a
 * nonzero value. In addition, these variables have to be adjacent.
 *
 * - Example discussed in mipformref whitepaper -
 */
public class SpecialOrderedSets {
    public static void main(String[] args) {

        final int NB = 4; // number of breakpoints
        double[] B_X = // X coordinates of breakpoints
                { 1, 2.5, 4.5, 6.5 };

        double[] B_Y = // Y coordinates of breakpoints
                { 1.5, 6, 3.5, 2.5 };

        System.out.println("Formulating the special ordered sets example problem");
        try (XpressProblem prob = new XpressProblem()) {
            // create one w variable for each breakpoint. We express
            Variable[] w = prob.addVariables(NB).withName("w_%d").withUB(1).toArray();

            Variable x = prob.addVariable("x");
            Variable y = prob.addVariable("y");

            // Define the SOS-2 with weights from B_X. This is necessary
            // to establish the ordering between the w variables.
            prob.addConstraint(sos2(w, B_X, "SOS_2"));

            // We use the w variables to express a convex combination.
            // In combination with the above SOS-2 condition,
            // X and Y are represented as a convex combination of 2 adjacent
            // breakpoints.
            prob.addConstraint(sum(w).eq(1));

            // The below constraints express the actual locations of X and Y
            // in the plane as a convex combination of the breakpoints, subject
            // to the assignment found for the w variables.
            prob.addConstraint(x.eq(scalarProduct(w, B_X)));
            prob.addConstraint(y.eq(scalarProduct(w, B_Y)));

            // set lower and upper bounds on x
            x.setLB(2);
            x.setUB(6);

            // set objective function with a minimization sense
            prob.setObjective(y, XPRSenumerations.ObjSense.MINIMIZE);

            // write the problem in LP format for manual inspection
            System.out.println("Writing the problem to 'SpecialOrderedSets.lp'");
            prob.writeProb("SpecialOrderedSets.lp", "l");

            // Solve the problem
            System.out.println("Solving the problem");
            prob.optimize();

            // check the solution status
            System.out.println("Problem finished with SolStatus " + prob.attributes().getSolStatus());
            if (prob.attributes().getSolStatus() != XPRSenumerations.SolStatus.OPTIMAL) {
                throw new RuntimeException("Problem not solved to optimality");
            }

            // print the optimal solution of the problem to the console
            System.out.printf(Locale.US, "Solution has objective value (profit) of %g%n",
                    prob.attributes().getObjVal());
            System.out.println("*** Solution ***");
            double[] sol = prob.getSolution();

            for (int b = 0; b < NB; b++) {
                String delim = b < NB - 1 ? ", " : System.lineSeparator();
                System.out.printf(Locale.US, "w_%d = %g%s", b, w[b].getValue(sol), delim);
            }

            System.out.printf(Locale.US, "x = %g, y = %g%n", x.getValue(sol), y.getValue(sol));
        }
    }
}

// (c) 2023-2024 Fair Isaac Corporation

import static com.dashoptimization.objects.SOS.sos2;
import static com.dashoptimization.objects.Utils.scalarProduct;
import static com.dashoptimization.objects.Utils.sum;

import java.util.Locale;

import com.dashoptimization.XPRSenumerations;
import com.dashoptimization.objects.Variable;
import com.dashoptimization.objects.XpressProblem;

/**
 * Approximation of a quadratic function in 2 variables by special ordered sets
 * (SOS-2). An SOS-2 is a constraint that allows at most 2 of its variables to
 * have a nonzero value. In addition, these variables have to be adjacent.
 *
 * - Example discussed in mipformref whitepaper -
 */
public class SpecialOrderedSetsQuadratic {
    public static void main(String[] args) {

        final int NX = 10; // number of breakpoints on the X-axis
        final int NY = 10; // number of breakpoints on the Y-axis
        double[] X = // X coordinates of grid points
                new double[NX];

        double[] Y = // Y coordinates of breakpoints
                new double[NY];

        double[][] F_XY = // two dimensional array of function values on the grid points
                new double[NX][NY];

        // assign the toy data
        for (int i = 0; i < NX; i++)
            X[i] = i + 1;
        for (int i = 0; i < NY; i++)
            Y[i] = i + 1;
        for (int i = 0; i < NX; i++)
            for (int j = 0; j < NY; j++)
                F_XY[i][j] = (X[i] - 5) * (Y[j] - 5);

        System.out.println("Formulating the special ordered sets quadratic example problem");
        try (XpressProblem prob = new XpressProblem()) {
            // create one w variable for each X breakpoint. We express
            Variable[] wx = prob.addVariables(NX).withName("wx_%d")
                    // this upper bound i redundant because of the convex combination constraint on
                    // the sum of the wx
                    .withUB(1).toArray();
            // create one w variable for each Y breakpoint. We express
            Variable[] wy = prob.addVariables(NY).withName("wy_%d")
                    // this upper bound i redundant because of the convex combination constraint on
                    // the sum of the wy
                    .withUB(1).toArray();

            // create a two-dimensional array of w variable for each grid point. We express
            Variable[][] wxy = prob.addVariables(NX, NY).withName("wxy_%d_%d")
                    // this upper bound is redundant because of the convex combination constraint on
                    // the sum of the wy
                    .withUB(1).toArray();

            Variable x = prob.addVariable("x");
            Variable y = prob.addVariable("y");
            Variable fxy = prob.addVariable("fxy");

            // make fxy a free variable
            fxy.setLB(Double.NEGATIVE_INFINITY);

            // Define the SOS-2 constraints with weights from X and Y.
            // This is necessary to establish the ordering between
            // variables in wx and in wy.
            prob.addConstraint(sos2(wx, X, "SOS_2_X"));
            prob.addConstraint(sos2(wy, Y, "SOS_2_Y"));
            prob.addConstraint(sum(wx).eq(1));
            prob.addConstraint(sum(wy).eq(1));

            // link the wxy variables to their 1-dimensional colleagues
            prob.addConstraints(NX, i -> (wx[i].eq(sum(NY, j -> wxy[i][j]))));
            prob.addConstraints(NY, j -> (wy[j].eq(sum(NX, i -> wxy[i][j]))));

            // now express the actual x, y, and f(x,y) coordinates
            prob.addConstraint(x.eq(scalarProduct(wx, X)));
            prob.addConstraint(y.eq(scalarProduct(wy, Y)));
            prob.addConstraint(fxy.eq(sum(NX, i -> sum(NY, j -> wxy[i][j].mul(F_XY[i][j])))));

            // set lower and upper bounds on x and y
            x.setLB(2);
            x.setUB(10);
            y.setLB(2);
            y.setUB(10);

            // set objective function with a minimization sense
            prob.setObjective(fxy, XPRSenumerations.ObjSense.MINIMIZE);

            // write the problem in LP format for manual inspection
            System.out.println("Writing the problem to 'SpecialOrderedSetsQuadratic.lp'");
            prob.writeProb("SpecialOrderedSetsQuadratic.lp", "l");

            // Solve the problem
            System.out.println("Solving the problem");
            prob.optimize();

            // check the solution status
            System.out.println("Problem finished with SolStatus " + prob.attributes().getSolStatus());
            if (prob.attributes().getSolStatus() != XPRSenumerations.SolStatus.OPTIMAL) {
                throw new RuntimeException("Problem not solved to optimality");
            }

            // print the optimal solution of the problem to the console
            System.out.printf(Locale.US, "Solution has objective value (profit) of %g%n%n",
                    prob.attributes().getObjVal());
            System.out.println("*** Solution ***");
            double[] sol = prob.getSolution();

            for (int i = 0; i < NX; i++) {
                String delim = i < NX - 1 ? ", " : System.lineSeparator();
                System.out.printf(Locale.US, "wx_%d = %g%s", i, wx[i].getValue(sol), delim);
            }
            for (int j = 0; j < NY; j++) {
                String delim = j < NY - 1 ? ", " : System.lineSeparator();
                System.out.printf(Locale.US, "wy_%d = %g%s", j, wy[j].getValue(sol), delim);
            }

            System.out.printf(Locale.US, "x = %g, y = %g%n", x.getValue(sol), y.getValue(sol));
        }
    }
}