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. SSC is an open source project under the GNU General Public License, Version 3
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.6.7</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"
- 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.6.7' - 2.4 Workspace Configuration Options
During the execution of the algorithm for solving linear programming problems, the SSC library uses the file system to create temporary directories. The library employs a flexible mechanism to determine and configure the default workspace directory, adopting a cascading approach to ensure a robust and adaptable configuration. During initialization, the library attempts to allocate the workspace directory in the following priority order:
- System Temporary Directory (java.io.tmpdir):
The library first checks the availability of the system's temporary directory, obtained via System.getProperty("java.io.tmpdir"). This directory is commonly used for temporary files and ensures quick access and security. - User Home Directory (user.home):
If the temporary directory is not usable, due to access restrictions or insufficient permissions, the library attempts to allocate the workspace in the user's home directory, accessible via System.getProperty("user.home"). - Current Directory (user.dir):
If the first two options fail, the library falls back to using the current directory, determined via System.getProperty("user.dir").
If none of these options are valid or accessible, it is possible to manually configure the desired workspace directory using the following instruction, which should be invoked at the start of the Java program:
Where "C:\\path_work_area" should be replaced with the path the user chooses to place the SSC temporary working directories. This flexibility allows users to customize the library's behavior to suit specific scenarios, such as environments with restricted access or where a predefined path for working files is required.Context.getConfig().setPathWorkArea("C:\\path_work_area");
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 Defining an LP Problem
A Linear Programming (LP) problem aims to optimize a linear objective function, subject to a set of linear constraints. The decision variables represent the choices to be made, and the optimal solution is obtained by applying methods such as the simplex algorithm, which ensures efficiency in solving problems with these characteristics. An example of a mathematical formulation of an LP problem is: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 ≥ 0The 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
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 conditionsY, 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.3cm} \text{ max/min } \hspace{0.3cm} c^{\mathrm{T}}x \hspace{0.3cm} \text{is objective function (o.f.) } \)
\( \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.3 Linear, Integer, and Mixed-Integer Programming in SSC
The SSC library offers two main approaches for solving linear programming problems: the Simplex method and the Branch and Bound (B&B) algorithm. The Simplex method is an iterative algorithm that seeks the optimal solution by moving along the vertices of the polyhedron defined by the constraints, making it particularly efficient even for large-scale problems. The B&B algorithm, on the other hand, is used for solving Integer Linear Programming (ILP) and Mixed-Integer Linear Programming (MILP) problems, handling discrete variables and complex constraints through search tree partitioning and the evaluation of lower and upper bounds.
The LP class in the library is dedicated to solving standard Linear Programming (LP) problems, where all decision variables are continuous, meaning they can take real values within a defined range. However, when some variables need to take integer values, we move to Integer Linear Programming (ILP) or Mixed-Integer Linear Programming (MILP), which are handled by the MILP class. This class can solve problems combining both integer and continuous variables, as well as problems with semi-continuous variables. Semi-continuous variables are a special class of optimization problems in which some decision variables can only take values of zero or values within a continuous range. For example, given[l, u]as a continuous interval bounded bylandu, a variablexcan be defined as semicontinuous in an LP problem ifl ≤ x ≤ ux = 0, with0 ∉ [l, u]
Starting from version 2.1.0, both the LP and MILP classes support multithreading, enabling a parallel implementation of the solving algorithms. This functionality allows multiple threads to be leveraged for improved performance, offering significant advantages on architectures with at least four physical cores.
3.4 Special Ordered Sets (SOS)
A Special Ordered Set (SOS) is an ordered set of variables used in optimization models to specify integrality conditions. Unlike branching on individual variables, the algorithm branches on entire sets of variables, exploiting the order among them to improve search efficiency. Even though the variables in the set can be continuous or discrete, using an SOS transforms the problem into a discrete optimization problem, requiring the use of a mixed-integer solver such as Branch and Bound (B&B). The main advantage is an acceleration in the search process. SOS can be solved in SSC through the MILP class.
There are two types of SOS:
• SOS1: This is a set of variables where at most one of them can take a non-zero value, while all others must be zero. This type of set is commonly used when variables are of 0-1 type, i.e., when we need to select at most one option among several possibilities, but they can also be integer or continuous. A typical example is choosing one among different investments; only one or none of the available options can be chosen.
• SOS2: In this case, it is a set of variables where at most two can be non-zero, and if two are non-zero, they must be consecutive in their order. SOS2 are often used to represent non-linear functions within a linear model. They are a natural extension of Separable Programming, but when integrated into a Branch and Bound algorithm, they allow for finding optimal solutions.
In addition to the two specified types, SSC implements two additional types of SOS in the presence of binary variables:
• F-SOS1-B: (Forced SOS1-Binary) is used to indicate Special Ordered Sets of type 1 binary with the condition that one variable must be forced to take a non-zero value. In this case, the constraint is not that only one variable can be non-zero, but that one variable from the set must be non-zero.
• F-SOS2-B: (Forced SOS2-Binary) is used to indicate Special Ordered Sets of type 2 binary with the same characteristic, i.e., two consecutive variables from the set must be non-zero.
3.5 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.6 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.
3.7 Branch and Bound (B&B) Algorithm
The simplex method is an efficient algorithm for solving continuous linear programming problems (i.e., those without integer variables), allowing for the handling of problems with a large number of variables and constraints. When using SSC to run the simplex method, the operational limits are primarily tied to the amount of memory available to the JVM. For example, by specifying a maximum of 4 gigabytes of memory with the-Xmx4goption, it is possible to solve problems involving thousands of variables and constraints.
As for the Branch and Bound method, its complexity is significantly higher since it involves solving a series of problems using the simplex method. This results in a much higher computational cost in terms of both time and resources, making Mixed-Integer Linear Programming (MILP) problems considerably more limited in size compared to pure LP problems.
3.8 Scalability and Numerical Stability
During the resolution of linear programming problems, the precision of calculations can be compromised when working with very large or very small values together. This effect, known as numerical instability, can arise from rounding errors or the accumulation of small errors in iterative calculations, such as those in the Simplex algorithm. To improve both numerical stability and performance, it is essential to appropriately scale the input data, keeping the coefficients of the constraints and the objective function within similar ranges, ideally close to 1. For example, a constraint like:10000X1 + 20000X2 <= 60000should be scaled to a constraint like:
X1 + 2X2 <= 6A recommended method is to use appropriate units of measurement, such as thousands of euros instead of euros if the amounts are very large, tons instead of kilograms if the weights are significant, etc. A well-scaled model minimizes the impact of these errors and improves the effectiveness of the algorithm in selecting pivot elements, leading to more stable and faster solutions.
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:- Text format
- JSON format
- Coefficient format
- Matrix format
- Sparse format
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 clear that the problem can be formulated using a single string called "lp_problem" (although it can have any other name). In this format, the objective function and each constraint must be written on separate lines (a newline character '\n' must be added at the end of each complete expression). Of course, if Java 15 Text Blocks (""") are used, the newline '\n' characters are unnecessary as long as individual statements are already on separate lines. In summary, the "lp_problem" string contains all the elements needed to formulate the mathematical problem described above: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.
Finally, we recall that the variables are, by default, non-negative (>=0).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 <= 24has variable
X2with a coefficient of3.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 of1, 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 +8X5represents 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 >= 9is an inequality constraint. In a constraint, variables can also appear on the right side of the inequality or equality, such as:
5x1 +2x2 >= 9 -3X4which 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 >= 9Constraint 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", wherelrepresent the limits. If not specified, variables are considered non-negative by default. In the example above, the following statement:anduX1 >= -1indicates a lower bound on the variable
X1. When defining a negative lower bound, as in this case, the variable is no longer constrained to non-negativity and can take values less than zero. It is important to note that this declaration implies that the variableX1can take any value greater than or equal to -1, including negative values. However, if we specify the sign of the variable when defining an upper or lower bound, such as in the following example:+X1 >= -1we are actually just defining a constraint, not a lower bound, without removing the non-negativity constraint. In other words, we are stating that
X1must be greater than or equal to -1, but since the variable is explicitly non-negative by default,X1will be limited to non-negative values that satisfy the conditionX1 >= -1. Therefore, the variable will never be less than zero, even if the bound is set to -1. This means that:
• If we declareX1 >= -1, we are defining a lower bound, and the variable is free to take any value starting from -1, including negative values.
• If we specify the sign (+/-) and declare+X1 >= -1, we are defining a constraint, and the variable remains subject to the non-negativity condition, only assuming values greater than or equal to zero, even though the constraint states that it must be greater than -1.
Starting from our example, let's consider the variableX2, which has a constraint of the form"l <= x <= u", i.e.:-1 <= X2 <= 6This constraint can be equivalently expressed with the inverse notation
"u >= x >= l", i.e.:6 >= X2 >= -1Both notations are completely equivalent and describe the same interval for the variable
X2.
Finally, let us remind that for a single variable, only one upper and one lower bound can be defined. For instance, if two upper bounds are defined for a variable, the more restrictive one will not be considered; instead, the library will report it as an error.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
X4can 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
X1is defined to take values in[-1,+∞](i.e., negative values greater than -1 and positive values), and a variableX3is defined to take only negative values in[-∞,-2]with the following statements:x1 >= -1 x3 <= -2Integer 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, X3specifies that
X2andX3must 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, X3specifies that
X2andX3must 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 bylanduwith"l > 0", then a variablexis semi-continuous in a linear programming problem if"l ≤ x ≤ u"or"x = 0", with0 ∉ [l, u]. To define semi-continuous variables, the variables in question must be preceded by the prefixsec. For example:sec x4, X5Naturally, if we define a semi-continuous variable
xwith the prefix"sec", it must also be constrained by a bound such as:l <= x <= u
Wildcard characters: 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 ALLdeclares 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
Xare integers, while those starting withYare 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.
SOS (Special Ordered Set): In SSC, it is possible to define Special Ordered Sets (SOS), which are ordered sets of variables with additional constraints on their behavior, useful for complex optimization problems. The library supports both type 1 SOS (SOS1) and type 2 SOS (SOS2), including binary, integer, and forced variants.
An SOS1 set limits the set of variables so that only one variable can be non-zero, while all others must be zero. Here is an example of a statement to add to the problem formulation to declare an SOS1 set:sos1 X1,X2,X3This declares that only one of
X1, X2 or X3can be non-zero, while the others must be equal to zero.
If the variables in the SOS1 set must be binary (i.e., 0 or 1), you use:sos1:bin X1,X2,X3In this case, only one of
X1, X2 or X3can be equal to 1, while the others must be 0.
To declare that the variables are integers, you can use:sos1:int X1,X2,X3This restricts variables
X1, X2 and X3to integer values, with the constraint that only one of them can take a non-zero value.
If you want to force one variable in an SOS1 set of binary variables to be non-zero, you can use the following notation:sos1:bin:force X1,X2,X3In this case, one of the variables must necessarily be non-zero, while the others will be zero. The
forceoption can only be used on binary sets of variables.
The library allows the use of a wildcard "*" to include all variables that start with a certain prefix into an SOS1 set. For example:sos1 X*This includes all variables starting with "
X" in the SOS1 set.
An SOS2 set limits the set of variables so that at most two variables can be non-zero, and if both are non-zero, they must be adjacent in their order. The order of the variables is crucial:sos2 X2,X3,X1In this case, at most two of the variables
X2, X3 and X1can be non-zero, and they must be contiguous in the declared order, for example, (X2, X3) or (X3, X1). If we want the variables in an SOS2 set to be binary, integer, or forced binary, we can use the following syntax, similar to SOS1:sos2:bin X2,X3,X1 sos2:int X2,X3,X1 sos2:bin:force X2,X3,X1Unlike SOS1, in SOS2 you cannot use the wildcard *, since the order of the variables must be explicitly declared through the statement "
sos2 Z,X,Y,K...".
It is possible to declare multiple SOS sets in the same linear programming problem by writing the declarations on separate lines. For example, if you want to declare one SOS1 set with binary variables and another SOS1 set with a forced binary variable, you can do it like this:sos1:bin X1,X2,X3 sos1:bin:force X4,X5,X6Now, let's look at an example of using SOS with mixed variables. Suppose we want to declare a series of SOS1 and SOS2 sets in a linear programming problem. The code might look like this:
// Declaration of an SOS1 set with mixed variables sos1 X1,X2,X3,X4,X5 int X1,X2 bin X3,X4 // Declaration of an SOS2 set with binary variables sos2:bin Y1,Y2,Y3 // Declaration of an SOS1 set with a forced binary variable sos1:bin:force Z1,Z2,Z3
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, 2.16, 2.17, 2.18, 2.19, 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 { //This example uses the Text Blocks """, present since java 15. //If you have an older version of java use the standard strings. 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 ofjakarta.jsonto 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 theJsonProblemclass is created by passing it the string containing the JSON (in the case of a JSON file, the correspondingPathobject 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, usingnullfor 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 variableX1can take values in[-1,+∞ ].
2) The variableX2can take values in[-1,6], meaning it can assume negative values greater than -1 or positive values less than 6.
3) The variableX3can only assume negative values in[-∞ ,-2].
4) The variableX4can take values in[-∞ ,+∞ ]or free.
5) The variableX5, 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 bynull. In general, to set variables that can take on negative values or a negative range, you can define an undefined lower bound (as withX4), a negative lower bound (as withX1), or a negative upper bound (as withX3).
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 variablesX2andX3are 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 variableX1takes on the various expressions in the problem. But how do we tell the SSC solver that the first column refers to the variableX1?
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 theInputStringclass to create an instance of this class. On this instance, you can invoke thesetInputFormat()method. The input format definition is done through a string that is passed as an argument to thesetInputFormat()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 variablesX1, X2, X3, X4, X5, all of type double. The values of the relation column are stored in a variable calledTYPE(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 namedRHS.
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 namedTYPEandRHS.
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
X1toX5. 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 theTYPEvariable 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. TheTYPEvariable can only take the following values, which can be written in either lowercase or uppercase:
min, max, eq, le, ge, lower, upper, integer, binary, semicontThe
TYPEvariable 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 theRHSvariable, 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 aTYPEand anRHSvariable 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 themilp_coeffstring 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, 7and8corresponding to variablesX1, 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 9represents 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.≥9Variable 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, whereuandlrepresent the limit values for the first variable declared in the input format, andaandnrepresent 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 forX4) or negative (as forX1) lower bound, or a negative upper bound (as forX3).
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 theTYPEis 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
X2andX3must 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 theTYPEis 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 bylandu, then a variable x can be defined as semi-continuous in an LP problem ifl ≤ x ≤ uor sex = 0, with 0 naturally not included in[l, u](0 ∉ [l, u]) . To define semi-continuous variables, a row must be added where theTYPEis 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
xis defined as semi-continuous, it must also be declared with bounds using a constraint such asl ≤ 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 vectorb[]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 matrixA[][]b[]andc[]are defined, you create aLinearObjectiveFunctionobject that represents the objective function andConstraintobjects that represent the constraints. The latter will populate the list (of typeListContraint) 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 vectorc[], 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 value0must still be included in thec[]vector. The direction of optimization (minimization or maximization) is specified using aGoalTypeparameter, such as"GoalType.MAX"or"GoalType.MIN". TheGoalTypeis specified, along with thec[]vector, as an argument in the constructor of theLinearObjectiveFunctionclass: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 matrixA[][]b[]contains the RHS values associated with the constraints, and the arrayrel[]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 consideri=0, i.e., selecting the values of the matrix and vectors corresponding to indexi=0and 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 ≥ 9in our problem.
SinceConstraintobjects are generally created and added to the list of constraints by iterating over the rows of the matrixA[][]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 matrixA[][]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 haveConsTypevalues such as"UPPER", "LOWER", "INT", "BIN", "SEMICONT". If the developer wishes, they can define inA[][]≤ , ≥, =) 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 therel[]array can assume, we have:LE, GE, EQ, UPPER, LOWER, INT, BIN, SEMICONTConstraints 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
Constraintclass, 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 namedX1, the secondX2, and so on.
Variable bounds: The upper and lower bounds of variables can be specified by using two separate rows in the matrixA[][]ConsTypevalues of"UPPER"and"LOWER"in the rel[] array. For example, for the variableX2, which has a lower bound of -1 and an upper bound of 6, two rows can be added to the matrixA[][]A[][]{ NaN , 6.0 , -2 , NaN , NaN }, //vector upper bound { -1 ,-1.0 , NaN, NaN , 0.0 }, //vector lower boundindicates 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 forX4) or a negative lower bound (as forX1), or a negative upper bound (as forX3).
Integer Variables: Variables that must take integer values are indicated by a row in the matrixA[][]ConsTypein therel[]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 matrixA[][]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 variablexcan be defined as semicontinuousl ≤ x ≤ uor ifx = 0, with0 ∉ [l, u].
Variables that must take semicontinuous values are indicated by a row in the matrixA[][]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 matrixA[][]"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
xas semicontinuous, it must also be bounded by a constraint of the typel ≤ 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 variablesTYPE, 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 theInputStringclass to create an instance of this class. On this instance, the methodsetInputFormat()can be invoked. The input format definition is done by passing a string as an argument to thesetInputFormat()method. In this string, separated by commas, the notations"variable name: type"
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 theTYPEcolumn can take are the following:MAX MIN EQ LE GE UPPER LOWER INTEGER BINARY SEMICONTThese 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 definedTYPEvalue (different from "."), it starts defining a new entity and assigns it a label, which is indicated in theROW_column. More specifically, if the engine detects thatTYPEis set to"MAX"or"MIN", it begins defining the objective function. If theTYPEvalue 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
TYPEandROW_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 theTYPEvalue is"UPPER"or"LOWER", we are defining labels that set the upper and lower bounds for the variables. Finally, if theTYPEvalue 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 definedTYPEis associated with a label (specified in theROW_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 inROW_but has an undefinedTYPE("."), it does not define a new entity but specifies the coefficient that a variable takes for that entity. In this case, the value inCOEFindicates the coefficient that the variable, specified inCOL_, takes for the entity corresponding to the label inROW_. Consider the row from our example:. X1 of_cost 3This row declares that the variable
X1takes the coefficient 3 in the objective function. Now consider another row from the example:. X1 constraint1 5This row declares that the variable
X1takes the coefficient 5 in the constraint identified by the label"constraint1"
3) COL_: The values inCOL_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: TheCOEFFvalues 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 theCOL_column is equal to"RHS".
It should be reiterated that the values in theTYPEandCOL_columns can be expressed in either uppercase or lowercase; in both cases, they will be converted to uppercase. However, for theROW_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 function3X1+X2-4X3+7X4+8X5to 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 8The first record, with the
TYPEvalue 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 constraint5X1+ 2X2+3X4≥ 9, the following records must be defined:GE . constraint1 . . X1 constraint1 5 . X2 constraint1 2 . X4 constraint1 3 . RHS constraint1 9Constraint 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 variableX1, whereX1 ≥ -1, the following records are required:LOWER . lower_bound . . X1 lower_bound -1The first record, with the
TYPEvalue set to"UPPER", indicates that the lower bound marker"lower_bound"is being defined. The second record specifies the lower bound for variableX1.
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 inX4) or negative lower bound (as inX1), or a negative upper bound (as inX3).
Integer Variables: Variables that must take integer values are indicated by the marker defined by the developer,"var_integer", which has aTYPEequal to"INTEGER". The integer variable is then indicated by placing a 1 in theCOEFcolumn, 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 aTYPEset to"BINARY". The binary variable is then specified by placing a 1 in theCOEFcolumn.
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 variablexcan be defined as semicontinuous ifl ≤ x ≤ uor ifx = 0, with0 ∉ [l, u].
Variables that must take semicontinuous values are indicated by a marker defined by the developer, with aTYPEset to"SEMICONT". The semicontinuous variable is then specified by placing a 1 in theCOEFcolumn.
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 thePathclass 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 thePathclass and then interpreted by theJsonProblemclass (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 theInputFileclass (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 theInputFileclass (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 theTYPE, ROW_, COL_ and COEFfields 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 theConnectionobject.Libraryobjects 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 theInputinterface). Below are the different formats and the respective classes to use:
- Text format :
String. - JSON format :
JsonProblem. - Coefficient format :
Input, InputString, InputFile. - Matrix format :
LinearObjectiveFunction e ListConstraints. - Sparse format :
Input, InputString, InputFile.
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
LPclass (for problems without integer variables) or theMILPclass (for mixed integer problems), passing the object containing the problem to the constructor. Once theLPorMILPobject is created, it is possible to invoke theresolve()method on both instances to start the solving process. This method returns a value from theSolutionTypeclass, indicating whether an optimal solution was found. Below is a complete example of solving a linear programming problem using the text format and theLPclass: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
LPclass with theMILPclass.
4.2.2 Configuration, Multithreading and Execution Options
As mentioned, theresolve()method can be invoked on the object belonging to theLPorMILPclass 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 thesetThreadsNumber()method of theLPclass (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.AUTOparameter 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.
MILP problems can also be solved using multiple threads:MILP milp = new MILP(milp_input); milp.setThreadsNumber(MILPThreadsNumber.N_6);Maximum Number of Iterations
The library allows limiting the maximum number of iterations throughsetNumMaxIteration()in theLPclass (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 thesetJustTakeFeasibleSolution(true)method of theLPclass (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 returnSolutionType.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 thesetCEpsilon()method of theLPclass (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 valuezof 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
LPclass (orMILPif there are integer variables) must be instantiated, and theresolve()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 typeSolutionType, which can take the following values (see example 1.10):OPTIMAL FEASIBLE UNLIMITED INFEASIBLE MAX_ITERATIONS MAX_NUM_SIMPLEXLet's examine each of these values in detail:
1) OPTIMAL: If the instance of theLP(orMILP) 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 thesetJustTakeFeasibleSolution(true)method is called on the instance of theLP(orMILP) class, the solver will not search for the optimal solution but will instead determine the first feasible solution found. If theLP(orMILP) 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: TheLPinstance has reached the maximum number of iterations.
6) MAX_NUM_SIMPLEX: TheMILPinstance has reached the maximum number of simplex steps executable.
4.3.1 Solution Interface
After executing theresolve()method and obtaining an optimal or feasible solution, you can access the details of the solution found. To do this, you need to call thegetSolution()method on the instance ofLP(orMILP). 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 theSolutioninterface, from which you can retrieve information about the optimal or feasible solution. Through theSolutionobject, you can access an array ofVariableobjects, which contain the values that the decision variables take in the solution, and also retrieve the optimal value of the objective function with thegetOptimumValue()method.
In addition to the values taken by the decision variables, theVariableobjects allow you to obtain their respective upper and lower bounds by calling thegetUpper()andgetLower()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 thesetJustTakeFeasibleSolution(true)method, instead ofgetOptimumValue(), you will need to use thegetValue()method to obtain the objective function value, as the optimal value will not be calculated (see example 2.14).
TheSolutionobject also provides other useful information. For example, through thegetSolutionConstraint()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 ofSolutionConstraintobjects, 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 thegetRhs()method.
In the context of a linear programming problem of the formAX<=>b, LHS represents the product AX, while RHS representsb. 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 theAXvalues.
The code also shows the constraint name (retrieved viagetName()) 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), theSolutionobject 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 continuous value.
To obtain information about the relaxed solution, you need to call thegetRelaxedSolution()method on theMILPinstance, 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()+"]"); }It is important to specify that the relaxation also applies to semicontinuous variables; this means that if x is a semicontinuous variable that can take values in \( x \in \text{{0}} \cup [l, u] \), the relaxed solution will be calculated for x over a new, broader set of values (relaxed): \( x \in [0, u] \).
4.4 Saving Results in JSON Format
The library allows saving the solution of a Mixed-Integer Linear Programming (MILP) or Linear Programming (LP) problem in JSON format. By using the
resolve(null)method, it is possible to create a chain of method calls to save the results to an external file or directly manipulate the JSON representation of the solution.
Here is an example of how to create a method chain to save the result in a JSON file:new MILP(pl_string).setTitle("Example results in JSON") .resolve(null) .getSolutionAsJson() .saveToFile("c:\\sscResult\\solution.json");In this example, the problem solution is solved and stored in an external JSON file. It is important to note that the value
nullis passed to theresolve()method to enable method chaining, allowing the solution to be obtained without returning a specific result type.
Alternatively, it is possible to store the solution in a JSON string:
If you want the JSON output, whether saved to an external file or as a string, to be formatted with indentation and line breaks, call the methodString json = new MILP(pl_string) .resolve(null) .getSolutionAsJson() .toString();formatted(true), as shown in the following example:String json = new MILP(pl_string) .resolve(null) .getSolutionAsJson() .formatted(true) .toString();If you prefer to work with a JSON object directly, such as
JsonObjectfrom the jakarta.json library, you can do so as follows:JsonObject jsonObject = new MILP(pl_string) .resolve(null) .getSolutionAsJson() .getJsonObject();The generated JSON structure will have several sections, which may include information such as metadata, constraints, and variable bounds (see example 1.18). The JSON structure is as follows:
{ "meta": { ... }, "objectiveType": "min", "status": "optimal", "solution": { ... }, "relaxedSolution": { ... } }The various sections in the JSON can be added or removed by specifying the
SolutionDetailconstants in thegetSolutionAsJson()method. For example, to include the variable bounds and the relaxed solution:MILP milp=new MILP(pl_string); milp.resolve(); String json=milp.getSolutionAsJson(SolutionDetail.INCLUDE_BOUNDS,SolutionDetail.INCLUDE_RELAXED).toString();The values that SolutionDetail can take include:
INCLUDE_BOUNDS: Adds the variable bounds (upper and lower limits) as specified during problem formulation.
INCLUDE_RELAXED: Includes the relaxed solution (see the previous paragraph).
INCLUDE_CONSTRAINT: Adds the LHS (Left-Hand Side) and RHS (Right-Hand Side) values of the problem's constraints (see the previous paragraph).
INCLUDE_META: Provides meta-information about the optimization, such as execution time and the number of threads.
INCLUDE_TYPEVAR: Includes the type of each variable (e.g., integer, binary, continuous).
4.5 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.5.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.0The 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 theSscLoggerclass. 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 thelog()method from theSscLoggerclass, 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.0Let us recall that the logging classes (
SscLogger, SscLevel) are contained in the packageorg.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 ERRORWhen 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 instructionSscLogger.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 totrue.
4.6 API documentation
The API documentation is available at the following link : API
- System Temporary Directory (java.io.tmpdir):