User Guide - Table of Contents
1. Introduction
The SSC library is a versatile tool designed to solve Linear Programming (LP) and Mixed-Integer Linear Programming (MILP) problems. This library allows users to define and solve optimization problems using various intuitive syntaxes, enabling efficient modeling of constraints and objective functions. It can be used for applications in operations research, economics, engineering, and management; additionally, it is easily integrable into Java projects through Maven and Gradle.
2. Installation and Integration
- 2.1 Prerequisites
To use the SSC library, the following requirements must be met:
- Java 10 or higher: The library requires Java 10 or later versions. Ensure you have a JDK compatible with this version of Java installed.
- Java development environment: An integrated development environment (IDE) such as IntelliJ IDEA, Eclipse, or NetBeans is recommended to facilitate project management and library integration.
- Dependency manager: It is recommended to use a dependency manager like Maven or Gradle for integrating the library into your project. If you use Maven or Gradle, include the appropriate dependencies in your configuration file. If you do not want to use a dependency manager, download the library in zip format from this website, extract the jar file, and include it in your project's classpath.
- Linear programming knowledge: To effectively use the library, it is helpful to have a basic understanding of linear programming and its modeling.
- 2.2 Integration with Maven
To integrate the SSC library into a Maven project, add the following dependency to the
pom.xmlfile :<!-- https://mvnrepository.com/artifact/org.ssclab/SSC-LP --> <dependency> <groupId>org.ssclab</groupId> <artifactId>SSC-LP</artifactId> <version>4.4.2</version> </dependency>You can find examples related to dependency management with different managers in the Maven repository at the link: "https://mvnrepository.com/artifact/org.ssclab/SSC-LP/4.4.2"
- 2.3 Integration with Gradle
To integrate the SSC library into a Gradle project, add the following dependency to the
build.gradlefile:// https://mvnrepository.com/artifact/org.ssclab/SSC-LP implementation group: 'org.ssclab', name: 'SSC-LP', version: '4.4.2' - Text format
- JSON format
- Coefficient format
- Matrix format
- Sparse format
- Text format :
String. - JSON format :
JsonProblem. - Coefficient format :
Input, InputString, InputFile. - Matrix format :
LinearObjectiveFunction e ListConstraints. - Sparse format :
Input, InputString, InputFile.
3. Getting Started
3.1 Overview of Linear Programming (LP)
Linear Programming (LP) is a mathematical technique used to solve optimization problems where the goal is to maximize or
minimize a linear objective function, subject to linear constraints expressed through equations or inequalities. This
methodology is widely applied in various fields such as economics, logistics, engineering, and management sciences to
make optimal decisions in complex situations.
In LP, the objective function represents the value to be optimized, which can be profit, cost, or other measures of interest.
The constraints represent the limitations or restrictions of the problem, such as available resources, production requirements,
or other operational conditions. These constraints are formulated as linear expressions of the decision variables.
The solution to an LP problem consists of finding the values of the decision variables that optimize the objective function
while satisfying all the imposed constraints. The solution can be found graphically (in the case of two variables) or through
numerical algorithms, such as the simplex method, which is one of the most well-known and efficient methods for solving large-scale
LP problems.
LP is a fundamental basis for other optimization techniques, such as Integer Linear Programming (ILP) and Mixed-Integer Linear Programming
(MILP), which extend LP concepts to include integer variables and more complex constraints.
3.2 Linear Programming in SSC
The SSC library uses two main methods to solve linear programming problems: the simplex method and Branch
and Bound (B&B). The simplex method is an iterative algorithm that seeks the optimal solution by moving along the vertices
of the polyhedron defined by the constraints, ensuring efficiency even for large-scale problems. Branch and Bound, on the
other hand, is used for Integer Linear Programming (ILP) problems and combines branching of the search tree with bounding the
lower and upper limits to find the optimal solution, thus handling discrete variables and more complex constraints.
With the B&B method in SSC, it is also possible to solve Mixed-Integer Linear Programming (MILP) problems, which are a class of
optimization problems where the objective is to maximize or minimize a linear objective function, subject to linear constraints,
with the additional characteristic that some decision variables must take integer values, while others can be continuous
(real numbers).
Starting from version 2.1.0 it is possible to perform a parallel simplex method implementation. This option allows to exploit
multiple threads for the simplex resolution and is advantageous in the case of architectures with at least 4 or more physical
cores.
Finally, with the B&B method in SSC, it is also possible to solve problems that involve semicontinuous variables.
These are a special class of optimization problems where some decision variables can only take values either equal
to zero or within a continuous range;
for example, given [l, u] as a continuous interval bounded by l and u, a
variable x can be defined as semicontinuous in an LP problem if l ≤ x ≤ u
or if x = 0, with 0 ∉ [l, u].
3.3 Defining an LP Problem
A Linear Programming (LP) problem is a type of optimization problem where the goal is to find the optimal value of a linear
objective function, subject to a set of linear constraints. The objective function represents the element to be maximized or minimized,
such as profit or cost. The constraints define the limitations or conditions that must be respected, such as available resources
or production capacities. The decision variables, which can be continuous or integer, represent the choices to be made. The goal
is to determine the values of the variables that optimize the objective function while meeting all the imposed constraints. An LP
problem is characterized by the linearity of its components, making it suitable for solutions via efficient algorithms like the
simplex method. Here is an example of the mathematical formulation of an LP problem:
min 3Y + 2X2 - 4X3 + 7X4 + 8X5
5Y + 2X2 3X4 ≥ 9
3Y + X2 + X3 + 5X5 = 12
6Y + 3X2 + 4X3 5X4 ≤ 24
with Y, X2, X3, X4, X5 ≥ 0
The objective function is the expression to be minimized or maximized, and it must be a linear combination of the decision
variables, in our case, 3Y +2X2 -4X3 +7X4 +8X5, with the goal of
finding the minimum possible value.
The remaining rows are the constraints, which are also linear expressions that limit the value of the decision variables.
They can be in the form of inequalities (less than or equal to, greater than or equal to) or equalities. In the example,
we have inequalities and an equality that define the restrictions on the problem. In general, the variables in an LP problem
are non-negative, as indicated by the conditions
Y, X2, X3, X4, X5 ≥ 0;
this is the default behavior for variables in the SSC library. However, it is possible to handle variables that can take
negative values, making them free or allowing them to take negative values depending on the specific needs of the problem.
In general, a linear programming problem can be fully represented through the use of vectors and matrices. In this case, a
generic linear programming problem can be described using the following syntax:
\( \hspace{0.7cm} Ax\, (\le , = , \ge)\, b \)
\( \hspace{0.7cm} l_{i} \le x_{i} \le u_{i} \)
\( \hspace{0.7cm} x_{i} \in \mathbb{Z} \hspace{1.6cm} \forall i \in \text{I} \)
\( \hspace{0.7cm} x_{i} \in \{0,1\} \hspace{0.8cm} \forall i \in \text{B} \)
\( \hspace{0.7cm} x_{i} \in \mathbb{R} \hspace{1.6cm} \forall i \notin (\text{I} \cup \text{B}) \)
\( \hspace{0.3cm} \) where:
\( \hspace{0.7cm} x\, \in \mathbb{R}^{n} \hspace{5cm} \text{it is the vector of variables}\, x_{i} \)
\( \hspace{0.7cm} A \in \mathbb{Q}^{m \times n} \hspace{4.4cm} \text{it is the coefficient matrix} \)
\( \hspace{0.7cm} c\,\, \in \mathbb{Q}^{n} \hspace{5cm} \text{it is the coefficient vector of the objective function} \)
\( \hspace{0.7cm} b\,\, \in \mathbb{Q}^{m} \hspace{4.9cm} \text{it is the RHS coefficient vector} \)
\( \hspace{0.7cm} l\,\,\, \in \mathbb{Q}^{n} \hspace{5cm} \text{it is the vector of lower bounds }\, l_{i} \)
\( \hspace{0.7cm} u\, \in \mathbb{Q}^{n} \hspace{5cm} \text{it is the vector of upper bounds }\, u_{i} \)
\( \hspace{0.7cm} \text{I}\,\, \subseteq \{1,..,n\} \hspace{3.7cm} \text{it is a subset of indices related to the integer variables} \)
\( \hspace{0.7cm} \text{B} \subseteq \{1,..,n\}\, : \, (\text{I} \cap \text{B}) = \emptyset \hspace{0.9cm} \text{it is a subset of indices related to the binary variables} \)
A formulation like this allows us to apply linear optimization algorithms, such as the simplex method, to find the optimal solution that satisfies all constraints and optimizes the objective function.
3.4 Simplex Algorithm
The simplex method is an iterative algorithm used to solve Linear Programming problems. The algorithm starts with
an initial basic solution, which is generally a feasible solution to the constraints. Through a series of steps, the
method moves the solution along the vertices of the polyhedron defined by the constraints, continuously improving
the value of the objective function until reaching a point where no further improvement is possible.
The general procedure includes selecting the variable to enter the basis and the one to leave, based on an optimality
criterion. The computational complexity of the method is exponential in the worst case, but generally, it has an average
polynomial behavior relative to the number of variables and constraints. In practice, the algorithm performs very well
for most real-world problems.
The simplex method can be implemented using the two-phase method when an initial feasible basic solution is not available.
In this procedure, artificial variables are introduced to find an initial feasible solution, which is then improved in the second phase.
The solutions returned can be of different types: an optimal solution that satisfies all constraints and optimizes the objective
function, an unbounded solution if the objective function can grow indefinitely without violating the constraints, or an empty
(or infeasible) solution if there is no solution that satisfies all the constraints.
3.4 Branch and Bound (B&B) Algorithm
The Branch and Bound (B&B) method is an algorithm used to solve Integer Linear Programming (ILP) and Mixed-Integer Linear
Programming (MILP) problems, where all or some variables must take integer values. This method systematically explores a
decision tree, where each node represents a subproblem obtained by relaxing or fixing some integer variables. The algorithm
starts with a linear relaxation of the original problem, initially solving this relaxation using the simplex method. If the
optimal solution of the relaxation satisfies the integer constraints, then it is an optimal solution for the original problem.
Otherwise, the algorithm splits the problem into two or more subproblems (branching), each with additional constraints on the
integer variables.
Each subproblem is then solved again using the simplex method. If a subproblem yields an optimal integer solution, the best
solution found so far is updated. The nodes of the tree that cannot provide a better solution are discarded (bounding).
The process continues until all subproblems have been explored or eliminated. Although B&B has a high computational complexity,
it can solve many real-world ILP problems in reasonable time.
4. Using the Library
4.1 Problem Formulation
In SSC, an LP (or MILP) problem can be formulated using one of several available formats. The formats that can be
used are the following:
Regardless of the type of format used to model the problem, the processing results can be obtained using the same interfaces. Therefore, no matter the format used, the method for retrieving the results remains the same.
4.1.1 Text Format
Let's consider the following mathematical formulation of a Linear Programming problem:
Objective function:
min 3X1 + X2 - 4X3 + 7X4 + 8X5
Constraints:
5X1 + 2X2 + 3X4 ≥ 9
3X1 + X2 + X3 + 5X5 = 12.5
6X1 +3.1X2 + 4X3 + 5X4 ≤ 24
Upper and lower bound:
X1 ≥ -1
-1 ≤ X2 ≤ +6
X3 ≤ -2
-∞ ≤ X4 ≤ +∞
Conditioned:
X5 ≥ 0
X2, X3 ∈ ℤ
To represent this Linear Programming problem in a format that can be processed by the SSC library, you can use the text (or textual) format. In this format, the problem needs to be provided to the library as a structured string, which will then be parsed by the library. This string must follow a specific syntax, which for the described mathematical example is:
public class Examples {
public static void main(String[] args) throws Exception {
String lp_problem =
" min: 3x1 +X2 -4x3 +7x4 +8X5 \n"+
" 5x1 +2x2 +3X4 >= 9 \n"+
" 3x1 + X2 +X3 +5X5 = 12.5 \n"+
" 6X1+3.1x2 +4X3 +5X4 <= 24 \n"+
" x1 >= -1 \n"+
"-1 <= x2 <= 6 \n"+
" x3 <= -2 \n"+
" . <= x4 <= . \n"+
" int x2, X3 ";
}
}
The above code highlights, in this initial part of the guide, only the representation format of an LP problem;
hence, it is not complete. The full example is available on the Examples page (example 3.1)
of this site.
From the example, it is evident that the problem is formulated through a single string called "lp_problem" (though it can have
any other name). In this format, the objective function and each constraint must be written on separate lines within the
string (you need to insert the newline character '\n' at the end of each complete expression). This string contains all the
necessary elements for formulating the problem:
Variables:
In the text format, variables can have any name (however, they must start with an alphabetic character followed by
alphanumeric characters) and are case-insensitive (meaning that the variables indicated as "x3" and "X3"
represent the same variable).
It is not necessary to list the variables in a specific order within the objective function or constraints. The variables
can appear in any order; for example, "3x1 + X2" is equivalent to "X2 + 3x1".
There should never be a space between a variable and its coefficient, while in all other cases, one or more spaces
can be inserted. For example, "3x1+X2" is equivalent to "3x1 + X2".
Additionally, if a variable appears multiple times in the same expression, either in the objective function or in the
constraints, the coefficients associated with that variable will be automatically added together. For example,
the expressions "4Y + 2X2 + Y >= 9" and "3Y +X2 >= 9 - X2 -2Y" will both be interpreted as
"5Y + 2X2 >= 9". This is done both to provide more flexibility and to avoid redundancy errors in the definition of variables.
Variables and constraints do not need to be vertically or horizontally aligned. Expressions can be written in a disaligned
manner, without the need to format the text to align the terms. This allows expressions to be written more freely, without
being constrained by formatting.
Variable Coefficients: In the text format, variable coefficients can be simple numbers, either integers or decimals. Naturally, the fractional part should only be included if present. In the example provided above, the constraint:
6X1 +3.1x2 +4X3 +5X4 <= 24
has variable X2 with a coefficient of 3.1, which includes a fractional part.
It is important to note that the coefficient of the first variable from the left of a constraint, or the number present
after the equality or inequality sign in a constraint, if positive, does not require the + sign. In all other cases,
the sign of the coefficient must be included. Of course, if a variable has a coefficient of 1, it can be omitted.
Objective function:
The first line of the string specifies the objective function; it is preceded by "min:" or "max:"
to indicate whether you want to minimize or maximize the function. In our example:
min: 3x1 +X2 -4x3 +7x4 +8X5 represents the objective function to minimize.
Constraints::
The subsequent lines specify the constraints of the problem, which must be expressed as inequalities (">="
, "<=") or equalities ("="). Each constraint must be a linear combination of variables. For example:
5x1 +2x2 +3X4 >= 9 is an inequality constraint. In a constraint, variables can also appear on the right side of the inequality or equality, such as:
5x1 +2x2 >= 9 -3X4 which is still a valid constraint formulation.
Constraints can be assigned labels or names. These names do not need to be unique for each constraint; a single label can be used for multiple constraints to identify them as belonging to a specific group. Naming or labeling is only for the purpose of identifying a constraint or a group of constraints; in fact, when retrieving and interpreting results, each constraint can be identified by its label along with its other characteristics. To define a label for a constraint, simply prefix the constraint with the name followed by a colon ":", as in the following example:
constraint1: 5X1 +2X2 +3X4 >= 9 Constraint labels are single words (without spaces) that must start with an alphabetic character followed by alphanumeric characters (letters and numbers).
Variable constraints:
It is possible to specify lower and upper bounds for variables using the syntax "l <= x <= u" or
"x >= l", or "x <= u",
where l represent the limits. If not specified, variables are considered
non-negative by default. In the example above, the following statement:
and u
X1 >= -1
is an example of a lower bound on variable X1. It is important to note that if a negative lower bound is
defined, as in this case, the variable in question is no longer subject to non-negativity constraints (see
the next section on "Free or Negative Variables").
Free or negative variables:
To declare free variables, i.e., variables without a lower bound (where the lower bound is no longer zero but -∞),
you just need to specify an undefined lower bound. If an undefined value is declared on a lower or upper bound, SSC
converts these values to -∞ for the lower bound and +∞ for the upper bound. In the text format, an
undefined value is represented by a period (.). In general, to set free variables, you simply assign an undefined
lower bound; for example, in our case, the variable X4 can take values in the range [-∞,+∞] using
the following statement:
. <= X4 <= .
To set variables that can take values in a negative range, you just need to assign either a negative lower bound or a
negative upper bound. In the example above, a variable X1 is defined to take values in [-1,+∞] (i.e., negative
values greater than -1 and positive values), and a variable X3 is defined to take only negative values in [-∞,-2]
with the following statements:
x1 >= -1
x3 <= -2
Integer variables:
For mixed-integer linear programming (MILP) problems, variables that must take integer values are declared with the
prefix "int". For example, in our case:
int x2, X3
specifies that X2 and X3 must be integers.
Binary variables:
For linear programming problems with binary variables, variables that must take values in {0,1} are declared
with the prefix "bin". So, using the notation:
bin X2, X3
specifies that X2 and X3 must be binary.
Semi-continuous variables:
It is possible to solve linear programming problems with semi-continuous variables. Recall that a semi-continuous
variable can either be zero or must belong to a continuous interval. For example, let [l, u] be a continuous interval
bounded by l and u, then a variable x is semi-continuous in a linear programming problem
if "l ≤ x ≤ u" or "x = 0", with 0 ∉ [l, u]. To define
semi-continuous variables, the variables in question must be preceded by the prefix sec. For example:
sec x4, X5
Naturally, if we define a semi-continuous variable x with the prefix "sec", it must also be
constrained by a bound such as:
l <= x <= u
Wildcard characters or words:
If in a linear programming problem it is necessary to declare all variables as integers, the word "ALL" can be used.
For example, in SSC, using the text format, this syntax:
int ALL
declares that all variables in the problem are integers. This syntax can also be used to declare all variables as binary
("bin ALL") or semi-continuous ("sec ALL"). In the text format, it is possible to use
the wildcard character * to declare that
all variables starting with a certain prefix belong to a specific class of variables. For example, with the notation:
int X*
bin Y*
it declares that all variables starting with X are integers, while those starting with Y are binary, and the remaining
variables are real. Note that each declaration of type "int", "bin" or "sec" must be placed on separate
lines if used simultaneously.
Complete examples of problem modeling using the text format are given in the Examples section of this site, demonstrating how to
represent both standard LP problems (examples 1.1 ,
1.6 ,
1.11) and MILP problems
(examples 2.7,
2.9,
3.1).
The library automatically parses the expressions in the string and translates them into a mathematical model that can be
solved using algorithms such as simplex or branch and bound.
4.1.2 JSON Format
Let's consider the following mathematical formulation of a Linear Programming problem:
Objective function:
min 3X1 + X2 - 4X3 + 7X4 + 8X5
Constraints:
5X1 + 2X2 + 3X4 ≥ 9
3X1 + X2 + X3 + 5X5 = 12.5
6X1 +3.1X2 + 4X3 + 5X4 ≤ 24
Upper and lower bound:
X1 ≥ -1
-1 ≤ X2 ≤ +6
X3 ≤ -2
-∞ ≤ X4 ≤ +∞
Conditioned:
X5 ≥ 0
X2, X3 ∈ ℤ
The library supports the formulation of Linear Programming (LP) problems in JSON format, which allows a structured representation of the objective function, constraints, and limits on the variables. Here is how you can represent a problem with this format:
public class Examples {
public static void main(String[] args) throws Exception {
String stringJson =
"{ "
+ " \"objective\": { "
+ " \"type\": \"min\", "
+ " \"coefficients\": { "
+ " \"X1\": 3, "
+ " \"X2\": 1, "
+ " \"x3\":-4, "
+ " \"X4\": 7, "
+ " \"X5\": 8 "
+ " } "
+ " }, "
+ " \"constraints\": [ "
+ " { "
+ " \"coefficients\": { "
+ " \"X1\": 5, "
+ " \"X2\": 2, "
+ " \"X4\": 3 "
+ " }, "
+ " \"relation\": \"ge\", "
+ " \"rhs\": 9, "
+ " \"name\":\"ConstraintA\" "
+ " }, "
+ " { "
+ " \"coefficients\": { "
+ " \"X1\": 3, "
+ " \"X2\": 1, "
+ " \"X3\": 1, "
+ " \"X5\": 5 "
+ " }, "
+ " \"relation\": \"eq\", "
+ " \"rhs\": 12.5, "
+ " \"name\":\"ConstraintB\" "
+ " }, "
+ " { "
+ " \"coefficients\": { "
+ " \"X1\": 6, "
+ " \"X2\":3.1, "
+ " \"X3\": 4, "
+ " \"X4\": 5 "
+ " }, "
+ " \"relation\": \"le\", "
+ " \"rhs\": 24, "
+ " \"name\":\"ConstraintC\" "
+ " } "
+ " ], "
+ " \"bounds\": { "
+ " \"X1\": { "
+ " \"lower\": -1 "
+ " }, "
+ " \"X2\": { "
+ " \"lower\":-1, "
+ " \"upper\": 6 "
+ " }, "
+ " \"X3\": { "
+ " \"upper\": -2 "
+ " }, "
+ " \"X4\": { "
+ " \"lower\": null,"
+ " \"upper\": null "
+ " } "
+ " }, "
+ " \"variables\": { "
+ " \"x2\": \"integer\", "
+ " \"X3\": \"integer\" "
+ " } "
+ "}";
JsonProblem jsonProb=new JsonProblem(stringJson);
}
}
The code described above is intended to highlight, in this initial part of the guide, only the format for representing an LP
problem, and is therefore not complete. The full example can be found on the Examples page (example 3.5) of this site.
The JSON format used is divided into sections, each represented by a JSON key. For example, to represent the objective
function, the "objective" key must be defined. It should be noted that all keys and string values must be
written in lowercase, except for the names of the LP problem variables and the optional names assigned to the constraints.
The SSC library uses an implementation of jakarta.json to handle the parsing of JSON files. It should be noted that this
implementation does not generate a parsing error when duplicate keys are found within a JSON object. In such cases, only
the last duplicate key is considered valid, and its value will overwrite any previous values associated with the same key.
This behavior may not be immediately apparent, so it is recommended to avoid duplicate keys within JSON definitions to ensure
correct results.
Once the problem is represented, an instance of the JsonProblem class is created by passing it the string containing the JSON
(in the case of a JSON file, the corresponding Path object is passed, see example 1.17). Now, let's examine each element of the JSON format.
Objective Function: In the problem formulation, the objective function is described through the "objective" section.
Here, you can specify the optimization type (type), which can be either "max" or "min", and
define the coefficients (coefficients) of the variables to be optimized, as specified below:
"objective": {
"type": "min",
"coefficients": {
"X1": 3,
"X2": 1,
"x3":-4,
"X4": 7,
"X5": 8
}
}
As we can see, both the key names ("objective","type", "coefficients") and the value "min" must
be written in lowercase. On the other hand, variable names are not case-sensitive, meaning "X3" and "x3"
represent the same variable.
Constraints: The constraints are specified in the "constraints" section, where each constraint is an element
of an array and is described by the coefficients of the involved variables, the relationship (greater than or equal to "ge",
less than or equal to "le", or equal to "eq"), and the value of the right-hand side "rhs".
Optionally, you can assign a name to the constraint using the "name" property. Below is a representation of a constraint
from the problem mentioned above:
"constraints": [
{
"coefficients": {
"Y" : 5,
"X2": 2,
"X4": 3
},
"relation": "ge",
"rhs": 9,
"name": "Constraint1"
},
...
...
]
Variable Bounds: The variable bounds are defined in the "bounds" section. If not specified (i.e.,
if these sections are missing), the variables are considered non-negative by default. You can specify the lower and
upper bounds for each variable, using null for infinite lower or upper bounds:
"bounds": {
"X1": {
"lower": -1
},
"X2": {
"lower":-1,
"upper": 6
},
"X3": {
"upper": -2
},
"X4": {
"lower": null,
"upper": null
}
}
The code indicates the following:
1) The variable X1 can take values in [-1,+∞ ].
2) The variable X2 can take values in [-1,6], meaning it can assume negative
values greater than -1 or positive values less than 6.
3) The variable X3 can only assume negative values in [-∞ ,-2].
4) The variable X4 can take values in [-∞ ,+∞ ]
or free.
5) The variable X5, not having been modified within the limits, can take values in [0,+∞ ] .
Of course, specifying an infinite upper bound (using "upper": null) is actually redundant since variables, being non-negative
by default, already have such a limit. We included this example to clarify what values can be assigned to the "upper" and
"lower" properties and their meaning.
Free or Negative Variables: To declare free variables, meaning variables without a lower bound (the lower bound will no
longer be zero but negative infinity), simply specify an undefined lower bound. If an undefined value is declared on the
"lower" or "upper" properties, SSC transforms these values into negative infinity for the lower bound and
positive infinity for the upper bound. In the JSON format, an undefined value is represented by null. In general, to
set variables that can take on negative values or a negative range, you can define an undefined lower bound (as with X4),
a negative lower bound (as with X1), or a negative upper bound (as with X3).
Variable Types: For Mixed Integer Linear Programming (MILP) problems, it is possible to declare which variables must take
on integer, binary, or semi-continuous values. The nature of the variables (e.g., whether they are continuous, integer, binary)
can be defined in the "variables" section. In this example, the variablesX2 and
X3 are declared as integers:
"variables": {
"x2": "integer",
"X3": "integer"
}
Depending on whether the variables are integer, binary, semi-continuous, or semi-continuous integer, the values "integer",
"binary", "semicont" and "integer-semicont" are used, respectively. Remember that JSON is a format that requires unique
keys in the objects it defines. Therefore, if a variable is both integer and semi-continuous, do not assign the values
"integer" and "semicont" to the same variable by duplicating the key for that variable name. Instead,
use the predefined value "integer-semicont".
4.1.3 Coefficient Format
Consider the following mathematical formulation of a Linear Programming problem:
Objective function:
min 3X1 + X2 - 4X3 + 7X4 + 8X5
Constraints:
5X1 + 2X2 + 3X4 ≥ 9
3X1 + X2 + X3 + 5X5 = 12.5
6X1 +3.1X2 + 4X3 + 5X4 ≤ 24
Upper and lower bound: :
X1 ≥ -1
-1 ≤ X2 ≤ +6
X3 ≤ -2
-∞ ≤ X4 ≤ +∞
Conditioned:
X5 ≥ 0
X2, X3 ∈ ℤ
To represent this Linear Programming problem so that it can be processed by the SSC library, you can use the coefficient format.
In this format, structured data is defined where each row (record) represents either the objective function, a constraint, or
the definition of variable characteristics. To separate the various expressions, they must be placed on different lines, which
is why the newline character '\n' is used at the end of each expression.
In this format, the columns represent the variable coefficients, relations, and right-hand side (RHS) values. This structured
data must follow a syntax defined by the user, as in the example below:
import org.ssclab.ref.InputString;
public class Examples {
public static void main(String[] args) throws Exception {
String milp_coeff = " 3 1 -4 7 8 min . " +'\n'+
" 5 2 0 3 0 ge 9 " +'\n'+
" 3 1 1 0 5 eq 12.5" +'\n'+
" 6 3.1 4 5 0 le 24" +'\n'+
"-1 -1 . . 0 lower . " +'\n'+
" . 6 -2 . . upper . " +'\n'+
" 0 1 1 0 0 integer . " ;
InputString milp_input = new InputString(milp_coeff);
milp_input.setInputFormat("X1:double,X2:double,X3:double,X4:double,X5:double, TYPE:varstring(8), RHS:double");
}
}
The code above is intended to highlight, in this initial part of the guide, only the format for representing an LP problem;
therefore, it is not complete. The full example is provided in the Examples page (example 3.2) on this site.
As mentioned, a column can represent the coefficients that a specific variable takes on the different constraints and the
objective function. In the example above, for instance, the first column represents all the coefficients that the variable
X1 takes on the various expressions in the problem. But how do we tell the SSC solver that the
first column refers to the variable X1 ?
To define what each column represents, you need to specify the input format (or record structure). By input format,
we mean a declaration that describes how to read and interpret the columns in the data structure in which the problem
is formulated. The input format definition is done using these two instructions:
InputString milp_input = new InputString(milp_coeff);
milp_input.setInputFormat("X1:double,X2:double,X3:double,X4:double,X5:double, TYPE:varstring(8), RHS:double");
The string that contains the problem formulation (milp_coeff) is passed to the constructor of the InputString
class to create an instance of this class. On this instance, you can invoke the setInputFormat() method. The input
format definition is done through a string that is passed as an argument to the setInputFormat() method. In this string,
the notations "variable name: variable type" are listed, separated by commas, to define the names of the variables
to be associated with the columns and the type of data present in the columns.
Although we talk about "columns," this is only to simplify understanding: the first piece of data in each row is associated
with the first declared variable, the second data point with the second declared variable, and so on. It is not necessary for the
coefficients to be strictly aligned vertically (i.e., all on the k-th character of each line); what is important is that they are
separated by at least one space and follow the correct sequence. The term "column" has been introduced solely to conceptually identify
the coefficients of a variable on the various constraints and the objective function or the RHS values.
Continuing with our example, the values of the first five columns, which correspond to the variables of the LP problem, are
stored in the variables X1, X2, X3, X4, X5, all of type double. The values of the relation column are stored
in a variable called TYPE (of type string with a length of 8 characters), while the values of the right-hand side (rhs)
column are stored in a double-type variable named RHS.
The names assigned to the variables of the LP problem are chosen by the analyst (though they must begin with an alphabetical
character followed by alphanumeric characters). However, the relation and rhs columns must necessarily be stored in variables
named TYPE and RHS.
Typically, we can also name variables without appending numbers, for example: "PRICE:double, AMOUNT:double, WEIGHT:double", etc.
It is generally preferable to declare the n variables of a problem using a different notation, called interval notation,
which is particularly useful if the problem contains dozens or hundreds of variables. In this case, the declaration
"X1:double, X2:double, X3:double, .... , Xn:double" for n variables can be replaced with the notation "X1-Xn:double".
Let's consider a theoretical example: suppose we have a problem with 7 variables that we want to divide into two groups; in this case,
we can use two distinct prefixes, for example: "PRICE1-PRICE3:double, COST1-COST4:double". Returning to our example,
and using the interval notation, the input format changes to:
milp_input.setInputFormat("X1-X5:double, TYPE:varstring(8), RHS:double");
This second notation, which is certainly more compact, allows us to declare all variables within the interval from
X1 to X5. Furthermore, the declaration of interval variables does not necessarily have to start from 1.
For example, in our case, we can also write "X6-X10:double".
The column associated with the TYPE variable is used to define the 'type' of expression contained in a row, such as a
constraint or objective function. If the value is "min" or "max", the row will be interpreted as an objective function;
while if it takes one of the values in {"eq","le","ge"}, it will be interpreted as a constraint.
The TYPE variable can only take the following values, which can be written in either lowercase or uppercase:
min, max, eq, le, ge, lower, upper, integer, binary, semicont
The TYPE variable is declared as varstring(8) so that it can contain values of up to 8 characters (in fact, the value
"semicont" is the longest, with 8 characters). Finally, we need to declare the RHS variable,
which contains the right-hand side (rhs) values. It is important to note that in the input format definition, it is mandatory
to declare both a TYPE and an RHS variable to associate with their respective values present
in the problem formulation.
Now let's analyze the different expressions (rows) through which a Linear Programming problem is formulated using the coefficient format:
Objective Function:
In the problem formulation shown above, the first line of the milp_coeff string specifies the coefficients of the objective
function and the optimization operation (min or max). That is, the line:
3 1 -4 7 8 min .
indicates the objective function (o.f.) to minimize, with the coefficients 3, 1, -4, 7 and 8 corresponding to
variables X1, X2, X3, X4, X5, respectively. This is followed by the type of objective function, which is "min".
Finally, the rhs column contains a dot (.), representing an undefined value. This is because, in the coefficient format,
every declared variable must have an associated value in each row. In this case, we insert an undefined value associated
with the rhs column, as it is irrelevant to the definition of the objective function.
In the coefficient format, unlike the textual format, every single value read (separated by one or more spaces)
must be completely meaningful. Therefore, when a sign is placed in front of a number, it must be strictly attached to
the number itself without any space separating them. Finally, coefficients do not require a sign if they are positive.
Constraints::
The subsequent lines represent the problem's constraints. Each constraint is specified by the coefficients of the variables,
followed by the type (TYPE) of inequality ("ge" for ≥, "le" for
≤, "eq" for =), and the value of the right-hand side (or constant term).
For example, the line:
5 2 0 3 0 ge 9
represents the constraint 5X1+2X2+3X4 . As mentioned earlier,
every declared variable must have a value in each row, so if a variable is not present in a constraint, its corresponding
coefficient must still be indicated but equal to zero.
≥ 9
Variable Limits:
It is possible to specify upper and lower limits for variables using dedicated rows. The syntax follows the pattern
"u a b c d e upper ." for the upper limit and "l n o p q r lower ."for the lower limit, where u
and l represent the limit values for the first variable declared in the input format,
and a and n represent the limits for the second variable, and so on.
If not specified (if the two lines are not present), variables are considered non-negative by default.
In the example above, the expression:
-1 -1 . . 0 lower .
. 6 -2 . . upper .
indicates the following:
1) The first variable declared in the input format (X1) can take values in [-1,.],
meaning [-1,+∞ ].
2) The second variable declared (X2)) can take values in [-1,6], meaning it can assume negative
values greater than -1 or positive values less than 6.
3) The third variable declared (X3) can take values in [.,-2] , meaning it can only
assume negative values in [-∞ ,-2].
4) The fourth variable declared (X4) can take values in [.,.], meaning [-∞ ,+∞ ]
or free.
5) The fifth variable declared (X5) can take values in [0,.] , meaning [0,+∞ ] .
Free or Negative Variables:
To declare free variables, those without a lower limit (the lower limit will no longer be zero but -∞ ), simply specify an
undefined lower bound. If an undefined value is declared in the row for lower bounds or upper bounds, SSC interprets such values
as -∞ in the first case and +∞ in the second. In the coefficient format, undefined values are represented by a dot (.). In general,
to define free variables or variables that can take negative values, it is sufficient to assign an undefined (as for X4) or negative
(as for X1) lower bound, or a negative upper bound (as for X3).
Integer Variables:
For Mixed Integer Linear Programming (MILP) problems, it is possible to declare which variables must take integer values.
This is done using a row where the TYPE is set to "integer" and specifies, via the values
1 and 0, which variables must be integers and which should not. The declaration shown in the example above:
0 1 1 0 0 integer .
indicates that variables X2 and X3 must be integers.
Binary Variables:
For Mixed Integer Linear Programming (MILP) problems, it is possible to declare which variables must take binary values {0,1}.
This is done using a row where the TYPE is set to "binary" and specifies, via the values 1 and 0, which variables must be binary
and which should not. For example, the declaration:
1 0 0 0 0 binary .
indicates that the first variable declared in the input format must be binary.
Semi-Continuous Variables:
It is possible to solve linear programming problems with semi-continuous variables. Recall that a semi-continuous
variable can either be zero or must belong to a bounded continuous interval. For example, let [l, u] be a continuous
interval bounded by l and u, then a variable x can be defined as semi-continuous in an LP problem
if l ≤ x ≤ u or se x = 0,
with 0 naturally not included in [l, u] (0 ∉ [l, u]) . To define semi-continuous variables,
a row must be added where the TYPE is set to "semicont" and specifies, via the values 1 and 0,
which variables must be semi-continuous and which should not. For example,
using the notation:
1 0 0 1 0 semicont .
we are declaring that the first and fourth variables in the input format are semi-continuous. Naturally, if a variable
x is defined as semi-continuous, it must also be declared with bounds using a constraint such as
l ≤ x ≤ u , and therefore the upper and lower bounds for that variable must also be defined.
Complete examples of modeling problems using the coefficient format are available in the Examples section of this site,
demonstrating how to represent both standard LP problems (examples 1.2 ,
1.4 ,
1.8 ,
1.10
1.14), and MILP problems
(examples 2.1,
2.4 ,
2.10,
3.2).
The library automatically parses the expressions in the string and translates them into a mathematical model
that can be solved using algorithms such as simplex or branch and bound.
4.1.4 Matrix format
Consider the following mathematical formulation of a Linear Programming problem:
Objective function:
min 3X1 + X2 - 4X3 + 7X4 + 8X5
Constraints:
5X1 + 2X2 + 3X4 ≥ 9
3X1 + X2 + X3 + 5X5 = 12.5
6X1 +3.1X2 + 4X3 + 5X4 ≤ 24
Upper and lower bound: :
X1 ≥ -1
-1 ≤ X2 ≤ +6
X3 ≤ -2
-∞ ≤ X4 ≤ +∞
Conditioned:
X5 ≥ 0
X2, X3 ∈ ℤ
To represent this Linear Programming problem so it can be processed by the SSC library, you can use the matrix format.
This format is similar to that of Apache Simplex Solver and is particularly useful for representing linear programming
problems in a structured way. It allows for easy manipulation of the various components of the problem through the use of
vectors and matrices (Java arrays and matrices). You need to define the matrix A[][]c[] for the objective function coefficients, and the vector b[] for the RHS
(right-hand side) values. Of course, the matrix and vectors can be given different names.
The following Java code shows an example of syntax for representing the above LP problem using the matrix format:
import org.ssclab.pl.milp.*;
import static org.ssclab.pl.milp.ConsType.*;
import static org.ssclab.pl.milp.LP.NaN;
public class Examples {
public static void main(String[] args) throws Exception {
double c[] =
{ 3.0, 1.0, -4.0, 7.0, 8.0 }; //array coefficients o.f.
double A[][]={
{ 5.0 , 2.0 , 0.0 , 3.0 , 0.0 },
{ 3.0 , 1.0 , 1.0 , 0.0 , 5.0 },
{ 6.0 , 3.1 , 4.0 , 5.0 , 0.0 },
{ NaN , 6.0 , -2 , NaN , NaN }, //array upper bound
{ -1 ,-1.0 , NaN, NaN , 0.0 }, //array lower bound
{ 0.0 , 1.0 , 1.0 , 0.0 , 0.0 }}; //array integer
double b[]= { 9.0, 12.5 ,24.0, NaN, NaN, NaN}; //array rhs
ConsType rel[]= { GE, EQ, LE, UPPER, LOWER, INT}; //array relations
LinearObjectiveFunction fo = new LinearObjectiveFunction(c, GoalType.MIN);
ListConstraints constraints = new ListConstraints();
for(int i=0; i < A.length; i++) constraints.add(new Constraint(A[i], rel[i], b[i]));
}
}
The code described here is intended to highlight, in this initial part of the guide, only the format for representing an LP
problem, and thus is not complete. The full example is provided on the Examples page (example 3.3) of this site.
Once the Java matrix A[][]b[] and c[] are defined,
you create a LinearObjectiveFunction object that represents the objective function and Constraint
objects that represent the constraints.
The latter will populate the list (of type ListContraint) containing all the constraints. The list of
constraints and the objective function allow for the instantiation of a linear programming problem in SSC.
Here is a detailed description of each component:
Objective function: It is defined by a vector c[], where each element represents the coefficient that each
variable takes in the objective function (o.f.). For example, the vector:
double c[]= { 3.0, 1.0, -4.0, 7.0, 8.0 };
represents the function 3X1+X2-4X3+7X4+8X5.
If a variable has a zero coefficient in the OF, the value 0 must still be included in the c[] vector.
The direction of optimization (minimization or maximization) is specified using a GoalType parameter, such
as "GoalType.MAX" or "GoalType.MIN". The GoalType is specified, along with the c[]
vector, as an argument in the constructor of the LinearObjectiveFunction class:
LinearObjectiveFunction fo = new LinearObjectiveFunction(c, GoalType.MIN);
This creates an object that fully represents the objective function.
Constraints: The constraints of the problem are defined using a matrix A[][]b[] contains the RHS values associated with the constraints, and the array rel[]
specifies the type of constraint or relation, such as "GE" for constraints ≥ , "LE"
for ≤ , "EQ" for =.
Each constraint is created using the constructor "new Constraint(A[i], rel[i], b[i])". If we take the example above and consider
i=0, i.e., selecting the values of the matrix and vectors corresponding to index
i=0 and using them to define the first constraint, we get the following equivalent instruction:
new Constraint( new double[]{ 5.0 , 2.0 , 0.0 , 3.0 , 0.0 }, GE, 9);
Which represents the first constraint 5X1+2X2+3X4 ≥ 9 in our problem.
Since Constraint objects are generally created and added to the list of constraints by iterating over the rows of the matrix
A[][]
for(int i=0; i < A.length; i++) constraints.add(new Constraint(A[i], rel[i], b[i]));
And since, in our example, we have also included rows in the A[][]b[] of RHS values has as many elements
as the rows of matrix A[][]b[] the correct length, "NaN"
(which, in matrix format, means undefined value) is inserted
for those relations that do not require an RHS value, which are the ones that have ConsType values such as
"UPPER", "LOWER", "INT", "BIN", "SEMICONT".
If the developer wishes, they can define in A[][]≤ , ≥, =) and insert the vectors representing the remaining limitations in separate arrays,
as shown in the code in this example (Example 2.8 line 34-35).
Wanting to list all the values that each element of the rel[] array can assume, we have:
LE, GE, EQ, UPPER, LOWER, INT, BIN, SEMICONT
Constraints in the problem can be assigned labels or names. These names do not necessarily have to be unique
for each constraint; in such cases, a single label can be used for multiple constraints to identify them as part
of a specific group. Assigning a name or label is solely for the purpose of identifying a constraint or a group of constraints;
indeed, during the retrieval and interpretation of results, each constraint can be identified using its label along with
other characteristics. To define a label on a constraint, simply add the constraint's name as the last argument in the
constructor of the Constraint class, as shown in the following example:
new Constraint(A[i], rel[i], b[i],"Constraint"+i);
In this case, by iterating over index i, we will assign the following names: "Constraint0",
"Constraint1", "Constraint2", and so on. Naturally, different names can be used and do
not necessarily need to be numbered.
Variables: In the matrix format, the names of the variables in the linear programming problem are automatically assigned
by the system. The first variable will be named X1, the second X2, and so on.
Variable bounds: The upper and lower bounds of variables can be specified by using two separate rows in the matrix
A[][]ConsType values of "UPPER" and
"LOWER" in the rel[] array. For example, for the variable X2, which has a
lower bound of -1 and an upper bound of 6, two rows can be added to the matrix A[][]A[][]
{ NaN , 6.0 , -2 , NaN , NaN }, //vector upper bound
{ -1 ,-1.0 , NaN, NaN , 0.0 }, //vector lower bound
indicates the following:
1) The first variable (X1) can take values in [-1,.], meaning [-1,+∞ ].
2) The second variable (X2)) can take values in [-1,6], meaning it can assume negative
values greater than -1 or positive values less than 6.
3) The third variable (X3) can take values in [.,-2] , meaning it can only
assume negative values in [-∞ ,-2].
4) The fourth variable (X4) can take values in [.,.], meaning [-∞ ,+∞ ]
or free.
5) The fifth variable (X5) can take values in [0,.] , meaning [0,+∞ ] .
Free or Negative Variables: To declare free variables, i.e., variables without a lower bound (where the lower bound is no
longer zero but -infinity), simply specify an undefined lower bound. If an undefined value is declared in the row for
lower bounds or the row for upper bounds, SSC converts such values to -infinity in the first case and +infinity in the second.
In the matrix format, an undefined value is represented by "NaN". In general, to set variables that can take values in a
negative range, simply assign an undefined lower bound (as for X4) or a negative lower bound
(as for X1), or a negative upper bound (as for X3).
Integer Variables: Variables that must take integer values are indicated by a row in the matrix A[][]ConsType in the rel[] array of relations, equal to "INT".
This row must contain 1 for integer variables and 0 for others.
Binary Variables: Variables that must take binary values are indicated by a row in the matrix A[][]rel[] array of relations, equal to "BIN". This row must
contain 1 for binary variables and 0 for others.
Semicontinuous Variables: It is possible to solve linear programming problems with semicontinuous variables.
Recall that a semicontinuous variable can either be zero or belong to a continuous bounded interval. For example,
let [l, u] be a continuous and bounded interval. A variable x can be defined as semicontinuous
l ≤ x ≤ u or if x = 0, with 0 ∉ [l, u].
Variables that must take semicontinuous values are indicated by a row in the matrix A[][]rel[] array of relations, equal to "SEMICONT". This row contains 1 for variables
that must be semicontinuous and 0 for others.
If a row in the matrix A[][]"SEMICONT" and in
that row the values are as follows:
{ 1.0 , 0.0 , 0.0 , 0.0 , 1.0 },
we are declaring that the first and fifth variables are semicontinuous. Naturally, if we define a variable x as
semicontinuous, it must also be bounded by a constraint of the type l ≤ x ≤ u, and therefore it is necessary to
define both the upper and lower bounds for the said variable.
Complete examples of modeling problems using the matrix format can be found in the "Examples" section of this site,
demonstrating how to represent both standard LP problems (examples 1.3 ,
1.5 ,
1.13), and MILP problems
(examples 2.2,
2.5 ,
2.8,
2.11,
2.13,
3.3). . The library automatically parses the expressions present in
the string and translates them into a mathematical model that can be solved using algorithms such
as simplex or branch and bound.
4.1.5 Sparse format
Consider the following mathematical formulation of a Linear Programming problem:
Objective function:
min 3X1 + X2 - 4X3 + 7X4 + 8X5
Constraints:
5X1 + 2X2 + 3X4 ≥ 9
3X1 + X2 + X3 + 5X5 = 12.5
6X1 +3.1X2 + 4X3 + 5X4 ≤ 24
Upper and lower bound: :
X1 ≥ -1
-1 ≤ X2 ≤ +6
X3 ≤ -2
-∞ ≤ X4 ≤ +∞
Conditioned:
X5 ≥ 0
X2, X3 ∈ ℤ
To represent this Linear Programming problem so that it can be processed by the SSC library, the sparse format can be used. This format is similar to the one provided by SAS® (LP procedure) and offers a flexible way to represent linear programming problems using a data structure that describes the relationships between variables, constraints, and the objective function. The following Java code demonstrates a syntax example to represent the above problem using the sparse format:
import org.ssclab.ref.InputString;
public class Example {
public static void main(String[] args) throws Exception {
String lp_sparse =
// TYPE COL_ ROW_ COEF
" MIN . of_cost . \n" +
" GE . constraint1 . \n" +
" EQ . capacity . \n" +
" LE . autonomy . \n" +
" UPPER . upper_bound . \n" +
" LOWER . lower_bound . \n" +
" INTEGER . var_integer . \n" +
" . X1 of_cost 3 \n" +
" . X1 constraint1 5 \n" +
" . X1 capacity 3 \n" +
" . X1 autonomy 6 \n" +
" . X1 lower_bound -1 \n" +
" . X2 of_cost 1 \n" +
" . X2 constraint1 2 \n" +
" . X2 capacity 1 \n" +
" . X2 autonomy 3.1 \n" +
" . X2 upper_bound 6 \n" +
" . X2 lower_bound -1 \n" +
" . X2 var_integer 1 \n" +
" . X3 of_cost -4 \n" +
" . X3 capacity 1 \n" +
" . X3 autonomy 4 \n" +
" . X3 upper_bound -2 \n" +
" . X3 var_integer 1 \n" +
" . X4 of_cost 7 \n" +
" . X4 constraint1 3 \n" +
" . X4 autonomy 5 \n" +
" . X4 upper_bound . \n" +
" . X4 lower_bound . \n" +
" . X5 of_cost 8 \n" +
" . X5 capacity 5 \n" +
" . RHS constraint1 9 \n" +
" . RHS capacity 12.5 \n" +
" . RHS autonomy 24 \n" ;
InputString lp_input = new InputString(lp_sparse);
lp_input.setInputFormat("TYPE:varstring(10), COL_:varstring(3) , ROW_:varstring(14), COEF:double");
}
}
This code is intended to highlight, in this initial part of the guide, only the format used to represent an LP problem.
As such, it is not complete. The full example is available on the Examples page (example
3.4) of this website.
In this format, structured data is defined within a string, where each line represents a declaration that defines a
specific aspect of the linear programming problem, such as the objective function, a constraint, or variable limits.
To separate the different declarations, they must be placed on different lines, which is why the new line character '\n'
is used at the end of each definition.
This format consists exclusively of four columns of values that are associated with the variables TYPE, COL_, ROW_, and COEF,
which are defined in the input format. By input format, we refer to a declaration that describes how the columns in
the data structure should be read and interpreted. The input format is defined through these two statements:
InputString lp_input = new InputString(lp_sparse);
lp_input.setInputFormat("TYPE:varstring(10), COL_:varstring(3) , ROW_:varstring(14), COEF:double");
The string that contains the problem formulation (lp_sparse) is passed to the constructor of the InputString
class to create an instance of this class. On this instance, the method setInputFormat() can be invoked.
The input format definition is done by passing a string as an argument to the setInputFormat() method. In this string,
separated by commas, the notations
Although we refer to 'columns,' this is only to simplify understanding: the first data value in each row is associated with
the first declared variable, the second value with the second declared variable, and so on. It is not necessary for the values
to be strictly aligned vertically (i.e., they do not need to appear at the k-th character of each row); the important thing is
that they are separated by at least one space and follow the correct sequence. It's worth mentioning that in this format, the
period character (".") represents an undefined or missing value (similar to null).
As this format is strictly composed of four columns, regardless of the number of decision variables and
constraints present in the problem, it can also be used to import linear programming problems from a database
table (see example 1.9). A second advantage of the sparse
format is that it allows you to specify only the non-zero coefficients in the description of the linear
programming problem. Let's look in detail at the different components of this format:
1) TYPE : The values that the TYPE column can take are the following:
MAX MIN EQ LE GE UPPER LOWER INTEGER BINARY SEMICONT
These values can be written in either uppercase or lowercase; in both cases, they will be converted to uppercase.
When the processing engine analyzes a row with a defined TYPE value (different from "."), it starts defining a new entity
and assigns it a label, which is indicated in the ROW_ column. More specifically, if the engine detects that TYPE is
set to "MAX" or "MIN", it begins defining the objective function. If the TYPE value is one
of "EQ" (=) , "LE" (≤) o "GE" (≥),
it starts defining a constraint. Let's consider the first row of the example above:
MIN . of_cost .
During the processing of this row, where only the TYPE and ROW_ variables are set, the processing engine starts
creating the definition of the objective function, assigning it the label "of_cost" and setting the optimization
direction to minimization. As we can see, there are periods (".") in the row, representing undefined values. This is
because, in the sparse format, every declared variable must have a value associated with it on each row. In this case,
undefined values are inserted to associate with the relevant columns since they are irrelevant in the creation of the
objective function. Let's consider the second row:
GE . constraint1 .
When this row is interpreted, it begins creating the definition of an inequality constraint (≥)
assigned with the label "constraint1".
This mechanism allows for defining all the characteristics of the problem. Specifically, if the TYPE value is
"UPPER" or "LOWER", we are defining labels that set the upper and lower bounds for the variables. Finally,
if the TYPE value is one of "INTEGER", "BINARY", or "SEMICONT", we are defining the
labels necessary to indicate which variables are integer, binary, or semi-continuous.
2) ROW_ :
Each row with a defined TYPE is associated with a label (specified in the ROW_ column) that uniquely identifies
the name of an entity. The names of these labels are freely chosen by the developer, but it is important to note
that they are case-sensitive.
If a row contains a value in ROW_ but has an undefined TYPE ("."), it does not define a new entity but specifies
the coefficient that a variable takes for that entity. In this case, the value in COEF indicates the coefficient that
the variable, specified in COL_, takes for the entity corresponding to the label in ROW_.
Consider the row from our example:
. X1 of_cost 3
This row declares that the variable X1 takes the coefficient 3 in the objective function.
Now consider another row from the example:
. X1 constraint1 5
This row declares that the variable X1 takes the coefficient 5 in the constraint identified by the label "constraint1"
3) COL_ :
The values in COL_ identify the names of the columns (i.e., the variables). To represent the column of rhs values
(right-hand side or constant terms), the reserved word "RHS" is used, which must not be used for any other purpose.
4) COEFF :
The COEFF values are either the coefficients that the variables take in relation to the different entities (constraint or
objective function), or the values of the constant terms if the value in the COL_ column is equal to "RHS".
It should be reiterated that the values in the TYPE and COL_ columns can be expressed in either uppercase or
lowercase; in both cases, they will be converted to uppercase. However, for the ROW_ column, using a label for the
same entity in both lowercase and uppercase within the same formulation means declaring two distinct labels (and thus
two distinct entities). Based on this, let's see how to define the different components that make up an LP problem:
Objective function :
To define the objective function 3X1+X2-4X3+7X4+8X5 to minimize,
as presented in our initial example, the following records are needed:
MIN . of_cost .
. X1 of_cost 3
. X2 of_cost 1
. X3 of_cost -4
. X4 of_cost 7
. X5 of_cost 8
The first record, with the TYPE value set to "MIN", indicates that we are defining an objective function to minimize,
and that the label used to identify it is "of_cost". The following records declare the coefficients that each variable
has on that label, which represents the objective function.
Constraints : To define the constraint
5X1+ 2X2+3X4≥ 9, the following records must be defined:
GE . constraint1 .
. X1 constraint1 5
. X2 constraint1 2
. X4 constraint1 3
. RHS constraint1 9
Constraint Names:
When a label for a constraint is defined, it also serves as the constraint's name. This allows the constraint
to be identified during result retrieval and interpretation, along with its other characteristics. There are no
specific restrictions on constraint names, but they must be a single word without spaces. Naturally, if particularly
long names are defined, the ROW_ variable in the input format must be set with an appropriate length, longer than the
14 characters declared for this example (ROW_:varstring(14)).
Variable Names:
There are no specific restrictions on variable names either, but they must be a single word without spaces.
Similarly, if particularly long variable names are defined, the COL_ variable in the input format must be set
with an appropriate length, longer than the 3 characters declared for this example (COL_:varstring(3)).
Variable Limits :
To define upper bounds and lower bounds, it is necessary to first define markers with the TYPE set to "UPPER" AND
"LOWER". These allow the limits on the variables to be specified. For example, to set the limit for variable
X1, where X1 ≥ -1,
the following records are required:
LOWER . lower_bound .
. X1 lower_bound -1
The first record, with the TYPE value set to "UPPER", indicates that the lower bound
marker "lower_bound" is being defined.
The second record specifies the lower bound for variable X1 .
Free or Negative Variables:
To declare free variables, i.e., variables without a lower bound (where the lower bound is no longer zero but -infinity),
simply specify an undefined lower bound. If an undefined lower bound or upper bound is declared for a variable,
SSC will convert these values to -infinity in the first case and +infinity in the second. In the sparse format, an
undefined value is represented by a dot ("."). In general, to set variables that can take negative values as well,
you can specify an undefined (as in X4) or negative lower bound (as in X1),
or a negative upper bound (as in X3).
Integer Variables:
Variables that must take integer values are indicated by the marker defined by the developer, "var_integer",
which has a TYPE equal to "INTEGER". The integer variable is then indicated by placing a 1 in the
COEF column, as shown below:
INTEGER . var_integer .
. X2 var_integer 1
Binary Variables:
Variables that must take binary values are indicated by a marker defined by the developer, with a TYPE set to
"BINARY". The binary variable is then specified by placing a 1 in the COEF column.
Semicontinuous Variables:
It is possible to solve linear programming problems with semicontinuous variables. A semicontinuous variable can either
be zero or must belong to a bounded continuous interval. For example, let [l, u] be a bounded continuous interval,
then a variable x can be defined as semicontinuous if l ≤ x ≤ u or if x = 0,
with 0 ∉ [l, u].
Variables that must take semicontinuous values are indicated by a marker defined by the developer,
with a TYPE set to "SEMICONT". The semicontinuous variable is then specified by placing a 1 in the
COEF column.
Complete examples of modeling problems using the sparse format can be found in the Examples section of this site,
demonstrating how to represent both standard LP problems (examples 1.7 ,
1.9 ,
1.12) ,
and MILP problems (examples 2.3 ,
2.6 ,
2.12 ,
3.4).
The library automatically parses the expressions present in the string and translates them into a mathematical
model that can be solved using algorithms such as the simplex or branch and bound.
4.1.6 Problem Formulation in an External File
The SSC library supports the ability to define a linear programming problem in an external file using four of the five
available formats: text format, JSON format, coefficient format, and sparse format. The problem data is stored in
an external file and interpreted by the library, ensuring flexibility and ease of use. Below, we describe how to
handle each format.
Text Format:
In the text format, the problem is described verbally in an external text file, which is referenced using the Path
class and then interpreted by the LP or MILP class (see example 1.11).
JSON Format:
In the JSON format, the problem is described in a JSON object within an external file, which is referenced using the
Path class and then interpreted by the JsonProblem class (see example
1.17).
Coefficient Format:
In the coefficient format, the problem is described in an external text file with a data structure containing the variable
coefficients, constraint types, and right-hand side values. The file is referenced using the InputFile class
(see example 1.8).
Sparse Format:
In the sparse format, the problem is described in an external text file containing a table with the values of the four columns
required to define the problem: TYPE, COL_, ROW_, and COEF.
The file is referenced using the InputFile class (see example 1.12).
4.1.7 Problem Formulation in an External Database
The SSC library supports the ability to define a linear programming problem in an external database (RDBMS) using
the sparse format. The sparse format is used because it is the only format strictly composed of 4 columns, making it
independent of the number of decision variables and constraints present in the problem. This aligns with the requirement
that a database table must have a predetermined number of fields. To perform this operation, the database must therefore
have four fields (columns) in which to store the information contained in the TYPE, ROW_, COL_ and COEF fields
of the sparse format.
To retrieve the problem formulation from a table in a database, it is necessary to download the JDBC driver for
the specific database and instantiate a Connection object. Once a connection to the DB is obtained, SSC can
access the database through the concept of a library using the Connection object. Library objects represent
an interface to the database; from this interface, we can use an SQL query to obtain an Input object that references
the records related to the problem stored in the table (see example 1.9).
4.2 Problem Solving
4.2.1 Optimization Execution
To solve a Linear Programming (LP) or Mixed Integer Linear Programming (MILP) problem, it is first necessary to
define the problem using the desired format, as described in the previous sections. Depending on the chosen format,
the problem formulation is stored in objects of specific classes or in classes that implement specific interfaces
(such as the Input interface). Below are the different formats and the respective classes to use:
These objects allow the problem to be stored in the chosen format; SSC's interpreter converts these various formulations
into a unified structure, making it understandable to the library's solving engine. The conversion into a unified structure
is achieved by creating an object of the LP class (for problems without integer variables) or the MILP class (for mixed
integer problems), passing the object containing the problem to the constructor. Once the LP or MILP object is created,
it is possible to invoke the resolve() method on both instances to start the solving process. This method returns a value
from the SolutionType class, indicating whether an optimal solution was found. Below is a complete example of solving a
linear programming problem using the text format and the LP class:
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
public class Example {
public static void main(String[] args) throws Exception {
String pl_string =
"min: 3Y +2x2 +4x3 +7x4 +8X5 \n"+
" 5Y +2x2 +3X4 >= 9 \n"+
" 3Y + X2 + X3 +5X5 = 12 \n" +
" 6Y+3.0x2 +4X3 +5X4 <= 24 \n";
LP lp = new LP(pl_string);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMAL) {
Solution solution=lp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Variable name :"+var.getName() + " value :"+var.getValue());
}
SscLogger.log("Optimal value:"+solution.getOptimumValue());
}
else SscLogger.log("No optimal :"+solution_type);
}
}
If any integer variables were declared in the example, you simply need to replace the LP
class with the MILP class.
4.2.2 Configuration and Execution Options
As mentioned, the resolve() method can be invoked on the object belonging to the LP or MILP class
to start the solving process. Before running the optimization, the library offers several configuration
options to adapt the problem-solving process to the specific needs of the user. These options allow for
controlling tolerance, using multithreading, obtaining a feasible solution, etc., providing further control
over the solving algorithm.
Parallel Execution with Multithreading
To improve performance, the library allows the use of parallel simplex by specifying the number of threads with the
setThreadsNumber() method of the LP class (see example 1.14).
For example:
LP lp = new LP(lp_input);
lp.setThreadsNumber(LPThreadsNumber.N_4);
In this case, we are specifying 4 threads for the execution. It is also possible to use the LPThreadsNumber.AUTO
parameter to let the system decide the number of threads. Multithreading is mainly recommended for problems with thousands
of variables or constraints and on machines with at least 4 physical cores.
Maximum Number of Iterations
The library allows limiting the maximum number of iterations through setNumMaxIteration() in the LP class
(see example 1.10), with the default value set to 100,000,000:
LP lp = new LP(lp_input);
lp.setNumMaxIteration(500);
In this way, the number of iterations is limited to 500.
Determining a Feasible Solution
It is possible to configure the algorithm to return a feasible solution, even if it's not optimal, by using the
setJustTakeFeasibleSolution(true) method of the LP class (see example 1.10).
This approach, suitable in situations where a quick feasible solution is needed, only executes the first phase of the simplex:
LP lp = new LP(lp_input);
lp.setJustTakeFeasibleSolution(true);
If a feasible solution exists, the resolve() method will return SolutionType.FEASIBLE, allowing you to obtain a basic
solution without proceeding to the optimal search.
Modifying the Tolerance
One of the options involves adjusting the tolerance used to determine the convergence of the 'first phase' of the simplex algorithm.
This option can be configured using the setCEpsilon() method of the LP class
(see example 1.13). For example:
LP lp = new LP(fo,constraints);
lp.setCEpsilon(EPSILON._1E_M5);
The default tolerance is set to 1E-8. However, when dealing with very large numbers, it may be necessary to increase it to a
higher value to ensure that the optimal value of the objective function, in the first phase of the simplex, satisfies the
optimality condition. Remember that a necessary condition for the problem to have a feasible solution is that the optimal
value of the first phase of the simplex equals zero. This might not happen due to the manipulation of very large numbers.
In this specific case, if the epsilon (ε ) tolerance for the optimal value z of the objective function in the first phase is not
adjusted, solving the problem might not yield feasible solutions. In other words, if at the end of the first phase |z| > ε ,
then the problem does not have feasible solutions. To resolve this, in the example above, the tolerance is increased from 1E-8
(default) to 1E-5 to ensure that |z| < ε. Without this adjustment, the problem might appear to lack feasible solutions,
even though they exist. Naturally, different tolerance values can be used: 1E-4, 1E-5, 1E-6, etc.
4.3 Retrieving and Interpreting Results
As discussed in the previous sections, to optimize an LP problem formulation, an object of the LP class
(or MILP if there are integer variables) must be instantiated, and the resolve() method must be invoked,
as shown in the following instructions:
LP lp = new LP(pl_string);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMAL) {
...
...
We can see that the resolve() method returns an object of type SolutionType , which can take
the following values (see example 1.10):
OPTIMAL FEASIBLE UNLIMITED INFEASIBLE MAX_ITERATIONS MAX_NUM_SIMPLEX
Let's examine each of these values in detail:
1) OPTIMAL :
If the instance of the LP (or MILP) class converges to the optimal solution, this value is returned.
You can then retrieve the optimal values of the decision variables and the objective function, along
with many other details regarding the problem resolution.
2) FEASIBLE :
If the setJustTakeFeasibleSolution(true) method is called on the instance of the LP (or MILP) class,
the solver will not search for the optimal solution but will instead determine the first feasible solution found.
If the LP (or MILP) instance converges to a feasible solution, this value is returned. You can then retrieve the
decision variable values and the objective function corresponding to this feasible solution, along with other relevant
information about the problem resolution.
3) UNLIMITED : The problem does not have an optimal solution, but an unlimited optimal value exists.
4) INFEASIBLE : The problem has no feasible solutions.
5) MAX_ITERATIUM : The LP instance has reached the maximum number of iterations.
6) MAX_NUM_SIMPLEX : The MILP instance has reached the maximum number of simplex steps executable.
4.3.1 Solution Interface
After executing the resolve() method and obtaining an optimal or feasible solution, you can access the details of the solution found.
To do this, you need to call the getSolution() method on the instance of LP (or MILP).
Consider the following code snippet:
LP lp = new LP(pl_string);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMAL) {
Solution solution=lp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Variable "+var.getName() +": "+var.getLower() + " <= ["+var.getValue()+"] <= "+var.getUpper());
}
SscLogger.log("Optimal value:"+solution.getOptimumValue());
}
The getSolution() method returns an object that implements the Solution interface, from which you can retrieve information
about the optimal or feasible solution. Through the Solution object, you can access an array of Variable objects, which
contain the values that the decision variables take in the solution, and also retrieve the optimal value of the objective
function with the getOptimumValue() method.
In addition to the values taken by the decision variables, the Variable objects allow you to obtain their respective
upper and lower bounds by calling the getUpper() and getLower() methods. This functionality allows you to easily verify the
lower and upper limits defined during the problem formulation for each variable.
If you have set the search for a feasible but non-optimal solution using the setJustTakeFeasibleSolution(true)
method, instead of getOptimumValue(), you will need to use the getValue() method to obtain the objective function
value, as the optimal value will not be calculated (see example 2.14).
The Solution object also provides other useful information. For example, through the getSolutionConstraint()
method, you can obtain details about the constraints. Here's a practical example:
LP lp = new LP(pl_string);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMAL) {
Solution soluzione=lp.getSolution();
for(SolutionConstraint constraint: soluzione.getSolutionConstraint()) {
SscLogger.log("Constraint :"+constraint.getName()+" : value ="+constraint.getValue()+
"[ "+constraint.getRel()+" "+constraint.getRhs()+" ]" );
}
}
In this code, by calling the getSolutionConstraint() method, we obtain an array of SolutionConstraint objects,
which represent the resolved constraints, i.e., the values of the constraints in the identified solution. These
values, called LHS (Left Hand Side), are compared with their corresponding RHS (Right Hand Side)
values using the getRhs() method.
In the context of a linear programming problem of the form AX<=>b, LHS represents the product AX,
while RHS represents b. It is important to note that variables placed on the right side of the inequality
or equality sign when defining the problem in text format will not be considered part of the RHS but will
be grouped into the AX values.
The code also shows the constraint name (retrieved via getName()) and the constraint type (getRel()),
allowing for a comprehensive view of the characteristics of the resolved constraints.
Finally, in the case of a mixed-integer linear programming problem (MILP), the Solution object can provide
information not only about the optimal mixed-integer solution found but also about its linear relaxation.
Recall that a linear relaxation is a simplified version of an optimization problem obtained by removing or
loosening some constraints, in this case, the integer constraints. Therefore, constraints that require variables
to be integers are removed, allowing the variables to take any real value.
To obtain information about the relaxed solution, you need to call the getRelaxedSolution() method on
the MILP instance, which will always return a Solution object containing the details of the relaxed solution,
as shown in the following example:
MILP milp = new MILP(fo,constraints);
SolutionType solution=milp.resolve();
if(solution==SolutionType.OPTIMAL) {
Solution sol=milp.getSolution();
Solution sol_relax=milp.getRelaxedSolution();
Variable[] var=sol.getVariables();
Variable[] var_relax=sol_relax.getVariables();
for(int _i=0; _i< var.length;_i++) {
SscLogger.log("Variable name :"+var[_i].getName() + " value:"+var[_i].getValue()+
" relaxed value: ["+var_relax[_i].getValue()+"]");
}
SscLogger.log("Optimal value:"+sol.getOptimumValue() +"relaxed value : ["+sol_relax.getOptimumValue()+"]");
}
4.4 Logging
In SSC, a logger is active by default, providing information about the execution process and informing the user through messages on the console. Let's take the log related to the execution of problem 1.1 in the Examples section of this site as an example:
27/09/24 11:07:05 - INFO:
27/09/24 11:07:05 - INFO: ##############################################
27/09/24 11:07:06 - INFO: SSC Version 4.4.2
27/09/24 11:07:06 - INFO: ##############################################
27/09/24 11:07:06 - INFO:
27/09/24 11:07:06 - INFO: Open session with ID: 1570886283
27/09/24 11:07:07 - INFO: Assigned library WORK C:\ssclab\ssc_work\work_1419679965
27/09/24 11:07:08 - INFO: Started procedure using the following Thread number:1
27/09/24 11:07:08 - INFO: ---------------------------------------------
27/09/24 11:07:08 - INFO: Phase One Simplex - Objective function value:8.881784197001252E-16
27/09/24 11:07:08 - TIME: Phase One Simplex - Duration 00:00:00:098 (hh:mm:ss:mmm)
27/09/24 11:07:08 - INFO: Phase One Simplex - Number iterations :2
27/09/24 11:07:08 - TIME: Phase Two Simplex - Duration 00:00:00:054 (hh:mm:ss:mmm)
27/09/24 11:07:08 - INFO: Total number of iterations (Phase One + Phase Two) Simplex:3
27/09/24 11:07:08 - TIME: Total time Simplex 00:00:00:152 (hh:mm:ss:mmm)
27/09/24 11:07:08 - INFO: The simplex has found an optimal solution
27/09/24 11:07:08 - INFO: ---------------------------------------------
27/09/24 11:07:08 - INFO: Solution accuracy x :
27/09/24 11:07:08 - INFO: Ax + s = b -> Ax + s - b = e (errors).
27/09/24 11:07:08 - INFO: x >= 0, b >= 0, s >= 0 slack variables.
27/09/24 11:07:08 - INFO: Average error, Mean(e):2.886579864025407E-14
27/09/24 11:07:08 - INFO: Maximum error, Max(e):1.1368683772161603E-13
27/09/24 11:07:08 - INFO: ---------------------------------------------
27/09/24 11:07:08 - INFO: Closed session with ID: 1570886283
27/09/24 11:07:08 - LOG: Variable name :X2 value :0.0
27/09/24 11:07:08 - LOG: Variable name :X3 value :0.0
27/09/24 11:07:08 - LOG: Variable name :X4 value :0.0
27/09/24 11:07:08 - LOG: Variable name :X5 value :0.0
27/09/24 11:07:08 - LOG: Variable name :Y value :4.0
27/09/24 11:07:08 - LOG: Objective function value:12.0
The logging system in the library provides information about the execution of the solving algorithm. Entries marked as
"INFO" offer a general overview of progress, including the opening and closing of the working session, the number of
threads used, and results from the simplex method, such as the number of iterations and the accuracy of the solution.
"TIME" entries indicate the duration of each phase of the process. On the other hand, "LOG" entries
are generated by the
developer using the SscLogger class. In our example, these allow you to display specific details about the solution found,
such as the values of the variables and the optimal objective function value.
In this case, it is up to the developer to decide whether to write certain results to the log or handle them differently,
for instance, saving them to other locations. To write to the log, which by default prints messages to the standard console
(usually System.out), you just need to invoke the log() method from the SscLogger class, as
shown in the following example:
SscLogger.log("Optimal value:"+soluzione.getOptimumValue());
This instruction will generate the following message on the standard console: :
11/09/24 15:03:58 - LOG: Optimal value:12.0
Let us recall that the logging classes (SscLogger, SscLevel) are contained in the package org.ssclab.log.
If desired, the developer can not only generate "LOG" messages but also other "levels" using the available methods.
For example, to generate an "INFO", a "WARNIG" , and an "ERROR" message,
the following instructions should be used:
SscLogger.info("Starting optimization program.");
SscLogger.warning("The number of variables is very high.");
SscLogger.error("There was an error during processing.");
These instructions will generate the following messages on the standard console:
11/09/24 16:47:26 - INFO: Starting optimization program.
11/09/24 16:47:26 - WARNING: The number of variables is very high.
11/09/24 16:47:26 - ERROR: There was an error during processing.
If the developer does not need logging, it can be disabled by adding the following instruction at the beginning of the code:
SscLogger.setLevel(SscLevel.OFF);
The previously used instruction simply sets the log to a certain level through the setLevel() method. This means that there are
various levels, which the developer can configure. Each level allows the display of messages belonging to the selected level and
those hierarchically higher. The hierarchy, and therefore the selectable levels, are as follows:
ALL FINE CONFIG INFO LOG TIME NOTE WARNING ERROR
When a level is selected, all the remaining levels positioned to the right of the list, along with the chosen level,
will be displayed on the console. For example, if "WARNING" is chosen (with the instruction
SscLogger.setLevel(SscLevel.WARNING)), only "WARNING" and "ERROR" messages will be shown.
If the log needs to be stored in an external file, it is possible to redirect the logging to a file using the following instruction:
SscLogger.setLogToFile("c:\\logs\\simplex.log",true);
This will save the log in a file named simplex.log; the second parameter allows appending to the file if set to true.