jdecor-pojo-template

This project is a minimal example that demonstrates how to use the jDecOR framework to solve a mixed-integer program in Java.
It's just two lines of code to your optimal solution 😉:

  Constants constants = new Constants(/*TODO: provide constants*/);

  Solution solution =
    new Solver(SolverEngine.CBC).generateSolution(constants);

You can fork this project if you want to quickstart your own implementation of an executable MIP/LP model.

What is jDecOR ?

jDecOR is a Declarative Java API for Operations Research (OR) software.

jDecOR's original purpose is to get rid of the often hard-to-avoid boilerplate code typically arising in applications that rely on solving OR models using (open-source or commercial) OR software packages. In addition, it follows a more declarative programming paradigm by encouraging you to compose your specific OR model in a structured way.

Long story short, it is designed to help making your code cleaner and less error-prone!

How to install jDecOR ?

• You can download jDecOR from our maven repository
• Add the dependency and our repository to your project's POM (We are working on a maven central release! Need more ☕):

    <dependencies>
        <dependency>
            <groupId>org.optsol.jdecor</groupId>
            <artifactId>jdecor-ortools</artifactId>
            <version>0.8.0</version>
        </dependency>
    </dependencies>

    <repositories>
        <repository>
            <id>optimal-solution</id>
            <url>https://maven.optimal-solution.org/repository/releases/</url>
        </repository>
    </repositories>

What do you find in the template project?

1. Optimization Problem

Slightly leaving the legal way, our idea is to forge EURO coins.

1.1 Problem Definition

Objective

Grabby as we are, we want to optimize our profit, namely the worth of EUROs produced.

Recipe

Fortunately we found an easy DIY-recipe in the shallow parts of the darknet. Now we know the weight (grams) of the metals Copper (Cu), Iron (Fe), Nickel (Ni), Aluminium (Al), Zinc (Zn) and Tin (Sn) needed for each coin type:

	Cu	Fe	Ni	Al	Zn	Sn
1 Cent	0.102	2.198	0	0	0	0
2 Cents	0.118	2.942	0	0	0	0
5 Cents	0.134	3.786	0	0	0	0
10 Cents	3.649	0	0	0.205	0.205	0.041
20 Cents	5.1086	0	0	0.287	0.287	0.0574
50 Cents	6.942	0	0	0.39	0.39	0.078
1 Euro	5.625	0	1.695	0	0.18	0
2 Euros	6.375	0	1.751	0	0.374	0

Restriction

Not limited by our bad conscience, our only restriction is a given amount of the different metals:

• Copper (Cu): 100grams
• Iron (Fe): 80grams
• Nickel (Ni): 10grams
• Aluminium (Al): 4grams
• Zinc (Zn): 10grams
• Tin (Sn): 3grams

1.2 Mathematical Formulation

Sets
set of coins
set of metals

Parameters
quantity available of metal m
profit of coin c
needed quantity of metal m for coin c

Variables
number of coins of type c to be forged

Model

2. Implementation

2.1 Model org.optsol.jdecor_pojo_template.model.Model

jDecOR provides a class for our model definition: AbstractOrtoolsModelFactory
Extending this abstract class requires you to provide:

1. a type parameter defining your available constants (Section 2.2)
2. your selection of solver engine (CBC/SCIP/GLOP/GUROBI) to the super-constructor (Section 2.3)
3. a definition of your variables implementing generateVarManager() method (Section 2.4)
4. your definition of the objective by overriding generateObjective() method (Section 2.5)
5. a list of constraints in generateConstraints() method (Section 2.6)

2.2 Constants org.optsol.jdecor_pojo_template.model.constants.Constants

First you have to define an object holding the input parameters of an instance of your optimization problem. We prefer using an immutable object for that purpose. (see Lombok's @Value).

Note: A different approach would be to define an interface for your constants. This is beneficial when you want use different implementations for your constants, for example when having different sources for your instance data.

We use our problem specific Constants to parameterize jDecOR's AbstractOrtoolsModelFactory

public class Model extends AbstractOrtoolsModelFactory<Constants>

2.3 Solver Engine

jDecOR Framework is based on the well-known Google OR-Tools. The following solvers are prepackaged for Windows, Linux and MacOS:

• SolverEngine.CBC: CBC from the CoinOR project (mixed-integer)
• SolverEngine.SCIP: SCIP (mixed-integer)
• SolverEngine.GLOP: GLOP (linear)
• SolverEngine.GUROBI: GUROBI (mixed-integer) | Gurobi is not prepackaged! Gurobi must be installed under standard path on your machine!

Disclaimer: The usage of certain solver packages may be restricted by an appropriate licensing. Please ensure correct licensing in accordance with the solver provider's usage terms.

jDecOR allows you to select a solver by providing the respective SolverEngine enum value to the constructor of AbstractOrtoolsModelFactory

  public Model(SolverEngine solverEngine) {
    super(solverEngine);
  }

2.4 Variables org.optsol.jdecor_pojo_template.model.variables.Variables

jDecOR lazily generates the needed variables based on their names. We recommend listing your variable group names in a dedicated class such as an enum or interface. This avoids misspellings and facilitates refactoring.

  public interface Variables {
    String x = "x";
  }

Using the builder of the OrtoolsVariableManager you can define bounds for groups of variables or restrict them to integer values. Any lazily generated variable not restricted in the OrtoolsVariableManager, will be unbounded and continous by default.

  @Override
  protected AbstractVariableManager<MPSolver, MPVariable, Constants> generateVarManager() {
    return
        new OrtoolsVariableManager.Builder()
            // x : int+
            .addIntVar(Variables.x)
            .addLowerBound(Variables.x, 0.)

            .build();
  }

2.5 Objective org.optsol.jdecor_pojo_template.model.objective.MaximizeProfit

Extending jDecOR's AbstractOrtoolsObjectiveManager you can define the objective function of your optimization model. objective.setMaximization() or objective.setMinimization() sets the direction of enhancement.

  @Override
  protected void configureObjective(
      MPObjective objective,
      Constants constants,
      IVariableProvider<MPVariable>  variables) throws Exception {
    //max sum_c:C[ P_c * x_c ]
    objective.setMaximization();

    for (int c : constants.get_C()) {
      objective.setCoefficient(
          variables.getVar(Variables.x, c),
          constants.get_P(c));
    }
  }

Finally provide an instance of your objective class in the generateObjective() method of your Model.

  @Override
  protected IObjectiveManager<
      ? super Constants, MPVariable, MPSolver> generateObjective() {
    return new MaximizeProfit();
  }

2.6 Constraints org.optsol.jdecor_pojo_template.model.constraints.AvailableMetalQuantity

Implementation of constraint groups should be based on jDecOR's AbstractOrtoolsConstraintManager.

This requires three steps for each constraint group:

• (I) Define constraint index structure
  In accordance with our mathematical model, we define the constraint group scoped index m:

  public AvailableMetalQuantity() {
	  //define constraint index m
    super("m");
  }

Note: By providing multiple index names to the super constructor, you can define indexes of arbitrary dimension. Non-indexed constraint groups consisting of one single constraint do not need to define indexes.

• (II) Generate constraint index keys
  ConstraintKey class represents the constraint index structure. You can define the constraint key values by overriding the createKeys() method.

  @Override
  protected Collection<ConstraintKey> createKeys(Constants constants) {
    //generate all indexes of constraint group:
    HashSet<ConstraintKey> indexes = new HashSet<>();
    for (int m : constants.get_M()) {
      indexes.add(new ConstraintKey(m));
    }
    return indexes;
  }

• (III) Configure constraints
  Implementing the method configureConstraint() is obligatory. With help of constants and variables the bounds and coefficients of the constraint with given index has to be defined.

  @Override
  protected void configureConstraint(
      MPConstraint constraint,
      Constants constants,
      IVariableProvider<MPVariable>  variables,
      ConstraintKey index) throws Exception {
    //configure constraint for index m:
    int m = index.get("m");

    //sum_c N_c_m * x_c <= Q_m
    constraint.setUb(constants.get_Q(m));

    for (int c : constants.get_C()) {
      constraint.setCoefficient(
          variables.getVar(Variables.x, c),
          constants.get_N(c, m));
    }
  }

Finally stitch all defined constraint groups together:

Provide a collection of instances of each constraint group in the generateConstraints() method of your Model:

  @Override
  protected List<
      IConstraintManager<
          ? super Constants,
          MPVariable,
          MPSolver>> generateConstraints() {
    return List.of(
        new AvailableMetalQuantity());
  }

---

3. Solving the Problem

3.1 Solution Definition org.optsol.jdecor_pojo_template.solver.Solution

jDecOR can automatically extract solutions from the solved model. You simply need to define an interface describing the structure of your expected solution. This must be in accordance with the declared variables.

• Basic solution information
  Every solution contains basic information such as SolutionState, ObjectiveValue, BestObjectiveBound and SolutionTime. jDecOR's ISolution interface describes getters for these values. Just extend ISolution in your individual solution definition.

• Values of variables
  To retrieve all values of a variable group, you simply need to define a method in your solution interface whose name starts with "get_" followed by a variable group name (e.g. get_x()). jDecOR offers two options to access solution data. You must choose one of the two options by specifying the return type of your getter method:

  1. Access-by-index
     • specify return type as a single Double/Integer/Boolean according to the type of variable or as a multidimensional array (e.g., 1D: Integer[], 2D: Boolean[][])
     • example:

  public interface Solution extends ISolution {
    Integer[] get_x();
  }
        
  //...  somewhere deep in your code
  Integer[] x = solution.get_x();
  // sum up all x_c values
  int total = 0;
  for (int c : constants.get_C()) {
    total += x[c];
  }

  2. Access-by-name via map
     • return type:
       java.util.Map with
       • key type parameter: String because key objects represent variable names; a variable name is defined as a variable group name (e.g., "x") followed by an underscore-separated list of integer-valued indices (e.g., "_1" or "_1_8_7")
       • value type parameter: depends on the type of variable (Double/Integer/Boolean)
     • example:

  public interface Solution extends ISolution {
    Map<String, Integer> get_x();
  }
           
  //...  somewhere deep in your code
  Map<String, Integer> x = solution.get_x();
  // sum up all x_c values
  int total = 0;
  for (int c : constants.get_C()) {
    String varName = "x_" + c;
    total += x.get(varName);
  }

Note: In case your model has many variables with two or more indices, we recommend the access-by-name option. Otherwise, solution retrieval can become quite slow since jDecOR makes heavily use of Java's reflection API under the hood... 😉

3.2 Solver Definition org.optsol.jdecor_pojo_template.solver.Solver

A convenient way to set up a problem specific solver is to extend jDecOR's OrtoolsSolver parameterized with your Constants and Solution. Additionally the solver needs to know your choice of solver engine and time limit.

  public Solver(
      SolverEngine solverEngine,
      int timelimitSeconds) {
    super(
        timelimitSeconds,
        new Model(solverEngine),
        Solution.class);
  }

3.3 Retrieving Solutions org.optsol.jdecor_pojo_template.tests.SolverTests

Now it is really just two lines of code to retrieve solutions:

  Constants constants = new Constants(/*TODO: provide constants*/);

  Solution solution =
    new Solver(SolverEngine.CBC).generateSolution(constants);