7.1 Linear Optimization

The simplest optimization problem is a purely linear problem. A linear optimization problem (see also Sec. 12.1 (Linear Optimization)) is a problem of the following form:

Minimize or maximize the objective function

j=0n1cjxj+cf

subject to the linear constraints

lkcj=0n1akjxjukc,k=0,,m1,

and the bounds

ljxxjujx,j=0,,n1.

The problem description consists of the following elements:

  • m and n — the number of constraints and variables, respectively,

  • x — the variable vector of length n,

  • c — the coefficient vector of length n

    c=[c0cn1],
  • cf — fixed term in the objective,

  • A — an m×n matrix of coefficients

    A=[a0,0a0,(n1)a(m1),0a(m1),(n1)],
  • lc and uc — the lower and upper bounds on constraints,

  • lx and ux — the lower and upper bounds on variables.

Please note that we are using 0 as the first index: x0 is the first element in variable vector x.

The Fusion user does not need to specify all of the above elements explicitly — they will be assembled from the Fusion model.

7.1.1 Example LO1

The following is an example of a small linear optimization problem:

(7.1)maximize3x0+1x1+5x2+1x3subject to3x0+1x1+2x2=30,2x0+1x1+3x2+1x315,2x1+3x325,

under the bounds

0x0,0x110,0x2,0x3.

We start our implementation in Fusion importing the relevant modules, i.e.

import mosek.fusion.*;

Next we declare an optimization model creating an instance of the Model class:

    try(Model M = new Model("lo1"))

For this simple problem we are going to enter all the linear coefficients directly:

    double[][] A =
    { new double[] { 3.0, 1.0, 2.0, 0.0 },
      new double[] { 2.0, 1.0, 3.0, 1.0 },
      new double[] { 0.0, 2.0, 0.0, 3.0 }
    };
    double[] c = { 3.0, 1.0, 5.0, 1.0  };

The variables appearing in problem (7.1) can be declared as one 4-dimensional variable:

      Variable x = M.variable("x", 4, Domain.greaterThan(0.0));

At this point we already have variables with bounds 0xi, because the domain is applied element-wise to the entries of the variable vector. Next, we impose the upper bound on x1:

      M.constraint(x.index(1), Domain.lessThan(10.0));

The linear constraints can now be entered one by one using the dot product of our variable with a coefficient vector:

      M.constraint("c1", Expr.dot(A[0], x), Domain.equalsTo(30.0));
      M.constraint("c2", Expr.dot(A[1], x), Domain.greaterThan(15.0));
      M.constraint("c3", Expr.dot(A[2], x), Domain.lessThan(25.0));

We end the definition of our optimization model setting the objective function in the same way:

      M.objective("obj", ObjectiveSense.Maximize, Expr.dot(c, x));

Finally, we only need to call the Model.solve method:

      M.solve();

The solution values can be attained with the method Variable.level.

      double[] sol = x.level();
      System.out.printf("[x0,x1,x2,x3] = [%e, %e, %e, %e]\n", sol[0], sol[1], sol[2], sol[3]);
Listing 7.1 Fusion implementation of model (7.1). Click here to download.
package com.mosek.fusion.examples;
import mosek.fusion.*;

public class lo1 {
  public static void main(String[] args)
  throws SolutionError {
    double[][] A =
    { new double[] { 3.0, 1.0, 2.0, 0.0 },
      new double[] { 2.0, 1.0, 3.0, 1.0 },
      new double[] { 0.0, 2.0, 0.0, 3.0 }
    };
    double[] c = { 3.0, 1.0, 5.0, 1.0  };

    // Create a model with the name 'lo1'
    try(Model M = new Model("lo1"))
    {
      // Create variable 'x' of length 4
      Variable x = M.variable("x", 4, Domain.greaterThan(0.0));

      // Create constraints
      M.constraint(x.index(1), Domain.lessThan(10.0));
      M.constraint("c1", Expr.dot(A[0], x), Domain.equalsTo(30.0));
      M.constraint("c2", Expr.dot(A[1], x), Domain.greaterThan(15.0));
      M.constraint("c3", Expr.dot(A[2], x), Domain.lessThan(25.0));

      // Set the objective function to (c^t * x)
      M.objective("obj", ObjectiveSense.Maximize, Expr.dot(c, x));

      // Solve the problem
      M.solve();

      // Get the solution values
      double[] sol = x.level();
      System.out.printf("[x0,x1,x2,x3] = [%e, %e, %e, %e]\n", sol[0], sol[1], sol[2], sol[3]);
    }
  }
}