Index
- Linear Programming
- Resolution of an LP problem expressed in text format
- Resolution of an LP problem expressed in coefficient format
- Resolution of an LP problem expressed in matrix format
- Resolution of an LP problem with bounded and free variables expressed in coefficient format
- Resolution of an LP problem with bounded and free variables expressed in matrix format
- Resolution of an LP problem with bounded and free variables expressed in text format
- Resolution of an LP problem expressed in sparse format
- Resolution of an LP problem in coefficient format stored in a external file
- Resolution of an LP problem in sparse format stored in a database
- Resolution of an LP problem to obtain only a feasible solution
- Resolution of an LP problem in text format stored in a external file
- Resolution of an LP problem in sparse format stored in a external file
- Resolution of an LP problem and modifying the tolerance ε relative to the objective function value at the end of phase 1 of the simplex
- Resolution of an LP problem using a parallel implementation of the simplex
- Resolution of an LP problem expressed in text format contained in an ArrayList
- Resolution of an LP problem expressed in JSON format
- Resolution of an LP problem expressed in JSON format stored in an external file
- Resolution of an LP problem and saving the results to an external JSON file
- Resolution of an LP problem and saving the results to an external text file
- Resolution of an LP problem in text format with calculations and mathematical functions
- Resolution of an LP problem in text format with double constraints and upper and lower bound declarations on the same line
- Integer Linear Programming, mixed integer and binary
- Resolution of an MILP problem in coefficient format
- Resolution of an MILP problem in matrix format
- Resolution of an MILP problem in sparse format
- Resolution of an MILP problem in coefficient format with binary variables
- Resolution of an MILP problem in matrix format with binary variables
- Resolution of an MILP problem in sparse format with binary variables
- Resolution of an MILP problem in text format
- Resolution of an MILP problem and comparing the optimal solution with that obtained from its relaxation
- Resolution of an MILP problem and comparing the value taken by the LHS part of each constraint with its corresponding RHS value
- Resolution of an MILP problem that presents semi-continuous variables
- Resolution of an MILP problem in matrix format that presents semi-continuous variables
- Resolution of an MILP problem in sparse format that presents semi-continuous variables
- Resolution of an MILP problem using multiple threads (parallel B&B)
- Resolution of an MILP problem to obtain a feasible solution
- Resolution of an MILP problem in JSON format
- Resolution of an MILP problem and saving the results to an external JSON file
- Resolution of a problem with SOS1 variables
- Resolution of a problem with SOS2 variables
- Resolution of a problem with Mixed-Type SOS Variables
- Examples in the "User's Guide"
Example 1.1
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
public class Example {
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 pl_problem = """
min: 3Y +2x2 +4x3 +7x4 +8X5
5Y +2x2 >= 9 -3X4
3Y + X2 + X3 +5X5 = 12
6Y +3x2 +4X3 <= 124 -5X4
y + 3x2 +6X5 <= 854 -3X4 """;
LP lp = new LP(pl_problem);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMAL) {
Solution soluzione=lp.getSolution();
for(Variable var:soluzione.getVariables()) {
SscLogger.log("Variable name :"+var.getName() + " value :"+var.getValue());
}
SscLogger.log("Objective function value:"+soluzione.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 1.2
Consider the following LP problem:
We want to solve this problem using a second representation format. In this second case, we can utilize structured data where each row represents either the objective function or a constraint, while the columns represent the coefficients of the variables, the relationships, and the rhs values [lines 12-16 of the code below]. This representation is referred to as the coefficient format.
Once the problem is formulated, it is necessary to specify its record layout (or input format). By input format, we mean a statement that describes how the columns present in the data structure in which the problem has been formulated are to be read and interpreted [lines 12-16]. The definition of the input format is done through a string to be passed as an argument to the setInputFormat() method [line 18]; in this string, the notation 'variable name: variable type' is used to define, in sequence, the names of the variables to be associated with the columns and the data type present in those columns. Specifically, it declares the variable names to be assigned to the first two columns, which represent the variables of the LP problem (in this case X1 and X2, of type double), the variable for the column of relationships (called TYPE and of type string with a length of 3 characters), and the variable for the column of RHS values (called RHS and of type double). The names assigned to the variables of the LP problem must be chosen by the analyst (they must start with an alphabetic character followed by alphanumeric characters). However, the names of the variables associated with the relationship column and the RHS values column must necessarily be TYPE and RHS [line 18].
Usually, variables can be named arbitrarily (however, they must start with an alphabetical character), even with names not necessarily followed by a number, for example: "PRICE:double, AMOUNT:double, WEIGHT:double," etc. However, it is usually preferable to declare the n variables of a problem using a different notation, called interval notation, which is particularly useful if the variables of the problem are dozens or hundreds. In this case, the declaration "X1:double, X2:double, X3:double, .... , Xn:double" of n variables can be replaced with the notation "X1-Xn:double". This second notation, certainly more compact, allows declaring all the variables included in the range from X1 to Xn.
We can notice that in the row corresponding to the objective function definition, the column for the RHS values contains a dot ("."), which represents an undefined value (similar to null). This is because, in the coefficients format, every declared variable must have an associated value in each row. In this case, we insert an undefined value in the RHS column, as it is irrelevant to the objective function's definition.
Once the problem is represented and variable names are assigned, the simplex algorithm is executed by creating an object of the LP class and invoking the resolve() method [lines 20-21]. After executing the simplex algorithm, the resolve() method returns the type of solution found; if the solution is optimal, it is possible to obtain the values of the variables and the optimal value of the objective function. It is worth noting that in SSC, by default, the variables of an LP problem are considered non-negative (≥ 0) unless otherwise specified.
max X1 + 3X2 X1 + X2 ≥-1 X1 + 1.4X2 ≤ 6 -5X1 + 3X2 = 5 with X1, X2 ≥ 0
We want to solve this problem using a second representation format. In this second case, we can utilize structured data where each row represents either the objective function or a constraint, while the columns represent the coefficients of the variables, the relationships, and the rhs values [lines 12-16 of the code below]. This representation is referred to as the coefficient format.
Once the problem is formulated, it is necessary to specify its record layout (or input format). By input format, we mean a statement that describes how the columns present in the data structure in which the problem has been formulated are to be read and interpreted [lines 12-16]. The definition of the input format is done through a string to be passed as an argument to the setInputFormat() method [line 18]; in this string, the notation 'variable name: variable type' is used to define, in sequence, the names of the variables to be associated with the columns and the data type present in those columns. Specifically, it declares the variable names to be assigned to the first two columns, which represent the variables of the LP problem (in this case X1 and X2, of type double), the variable for the column of relationships (called TYPE and of type string with a length of 3 characters), and the variable for the column of RHS values (called RHS and of type double). The names assigned to the variables of the LP problem must be chosen by the analyst (they must start with an alphabetic character followed by alphanumeric characters). However, the names of the variables associated with the relationship column and the RHS values column must necessarily be TYPE and RHS [line 18].
Usually, variables can be named arbitrarily (however, they must start with an alphabetical character), even with names not necessarily followed by a number, for example: "PRICE:double, AMOUNT:double, WEIGHT:double," etc. However, it is usually preferable to declare the n variables of a problem using a different notation, called interval notation, which is particularly useful if the variables of the problem are dozens or hundreds. In this case, the declaration "X1:double, X2:double, X3:double, .... , Xn:double" of n variables can be replaced with the notation "X1-Xn:double". This second notation, certainly more compact, allows declaring all the variables included in the range from X1 to Xn.
We can notice that in the row corresponding to the objective function definition, the column for the RHS values contains a dot ("."), which represents an undefined value (similar to null). This is because, in the coefficients format, every declared variable must have an associated value in each row. In this case, we insert an undefined value in the RHS column, as it is irrelevant to the objective function's definition.
Once the problem is represented and variable names are assigned, the simplex algorithm is executed by creating an object of the LP class and invoking the resolve() method [lines 20-21]. After executing the simplex algorithm, the resolve() method returns the type of solution found; if the solution is optimal, it is possible to obtain the values of the variables and the optimal value of the objective function. It is worth noting that in SSC, by default, the variables of an LP problem are considered non-negative (≥ 0) unless otherwise specified.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
import org.ssclab.ref.*;
public class Esempio2 {
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 lp_string = """
1 3 max .
1 1 ge -1
1 1.4 le 6
-5 3 eq 5 """;
Input lp_input = new InputString(lp_string).setInputFormat("X1-X2:double, TYPE:varstring(3), RHS:double");
LP lp = new LP(lp_input);
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("o.f. value:"+solution.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 1.3
Consider the LP problem reported in the previous example and given by:
The previous example problem can also be expressed through the use of vectors and matrices, with the matrix format. The representation format used is similar to that of simplex solver Apache. In this case it is necessary to define the matrix A of coefficients, the vector c of the coefficients of o.f. and the vector b of the RHS values.
Defined such entities [lines 8-13] you create a LinearObjectiveFunction object [line 17] which represents the objective function and Constraint objects [line 21] that represent the constraints. The type of constraint (LE, GE, EQ) is specified through the elements of the vector of the rel relations [line 15]. Finally, the list of constraints and the objective function are enough parameters to instantiate an object of class LP [line 24].
max X1 + 3X2 X1 + X2 ≥-1 X1 + 1.4X2 ≤ 6 -5X1 + 3X2 = 5 with X1, X2 ≥ 0
The previous example problem can also be expressed through the use of vectors and matrices, with the matrix format. The representation format used is similar to that of simplex solver Apache. In this case it is necessary to define the matrix A of coefficients, the vector c of the coefficients of o.f. and the vector b of the RHS values.
Defined such entities [lines 8-13] you create a LinearObjectiveFunction object [line 17] which represents the objective function and Constraint objects [line 21] that represent the constraints. The type of constraint (LE, GE, EQ) is specified through the elements of the vector of the rel relations [line 15]. Finally, the list of constraints and the objective function are enough parameters to instantiate an object of class LP [line 24].
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
public class Example {
public static void main(String[] args) throws Exception {
double A[][]={
{ 1.0 , 1.0 },
{ 1.0 , 1.4 },
{-5.0 , 3.0 } } ;
double b[]= {-1.0, 6.0 ,5.0 };
double c[]= { 1.0, 3.0 };
ConsType[] rel= {ConsType.GE, ConsType.LE, ConsType.EQ};
LinearObjectiveFunction of = new LinearObjectiveFunction(c, GoalType.MAX);
ListConstraints constraints = new ListConstraints();
for(int i=0; i < A.length; i++) {
constraints.add(new Constraint(A[i], rel[i], b[i]));
}
LP lp = new LP(of,constraints);
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("o.f. value:"+solution.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 1.4
Consider the following LP problem:
In this example, the variable X1 is bounded both from below (not from zero) and from above. Representing the problem in coefficient format, to define a variable with such constraints, one simply needs to add a line for the upper bound and one for the lower bound [lines 13-14]. For the variable X2 (a variable without bounds), one only needs to specify a lower bound and an indefinite upper bound (represented by ".").
It is important to emphasize that, in order to set free variables or variables that can take values in a negative range, it is sufficient to set an indefinite (.) or negative lower bound, or a negative upper bound. For example, considering the variable X1, it must take values greater than -1; therefore, introducing a constraint like "1 0 ge -1 \n" in the problem formulation (namely, the constraint that the variable X1 is greater than -1) does not imply that the variable X1 can take values up to -1, but only binds the problem to satisfy this condition. This condition cannot be fully evaluated (allowing the variable to take negative values) unless the variable is made effectively free to take negative values. To make it free to vary in such ranges, one must exclusively use the notation of upper and lower bounds. In this example, both X1 and X2 are variables that can take negative values (via lines 13-14).
Finally, when printing the solution, it is possible to retrieve for each variable the upper and lower bounds previously set during the formulation of the problem [line 24].
max X1 + 3X2 X1 + X2 ≥ 1 X1 + 1.4X2 ≤ 6 -5X1 + 3X2 = 5 with -1 ≤ X1 ≤ +1 -∞ ≤ X2 ≤ +∞
In this example, the variable X1 is bounded both from below (not from zero) and from above. Representing the problem in coefficient format, to define a variable with such constraints, one simply needs to add a line for the upper bound and one for the lower bound [lines 13-14]. For the variable X2 (a variable without bounds), one only needs to specify a lower bound and an indefinite upper bound (represented by ".").
It is important to emphasize that, in order to set free variables or variables that can take values in a negative range, it is sufficient to set an indefinite (.) or negative lower bound, or a negative upper bound. For example, considering the variable X1, it must take values greater than -1; therefore, introducing a constraint like "1 0 ge -1 \n" in the problem formulation (namely, the constraint that the variable X1 is greater than -1) does not imply that the variable X1 can take values up to -1, but only binds the problem to satisfy this condition. This condition cannot be fully evaluated (allowing the variable to take negative values) unless the variable is made effectively free to take negative values. To make it free to vary in such ranges, one must exclusively use the notation of upper and lower bounds. In this example, both X1 and X2 are variables that can take negative values (via lines 13-14).
Finally, when printing the solution, it is possible to retrieve for each variable the upper and lower bounds previously set during the formulation of the problem [line 24].
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
import org.ssclab.ref.*;
public class Example {
public static void main(String[] args) throws Exception {
String lp_string =
" 1 3 max . \n" +
" 1 1 ge 1 \n" +
" 1 1.4 le 6 \n" +
"-5 3 eq 5 \n" +
" 1 . upper . \n" +
"-1 . lower . \n" ;
Input lp_input = new InputString(lp_string).setInputFormat("X1-X2:double, TYPE:varstring(8), RHS:double");
LP lp = new LP(lp_input);
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("o.f. value:"+solution.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 1.5
Consider the following LP problem reported in the previous example:
Let's solve the previous example using the matrix format. In order to represent the variable X1, which is bounded both inferiorly and superiorly, it is necessary to add to the matrix A a line for the upper bounds and one for the lower bounds [lines 13-14]. In the case of the variable X2, or of a free variable without limits, it is sufficient to specify a lower bound and an upper bound indefinite with the value NaN.
Recall that in order to set the free variables, or variables that can assume negative values, must be set a lower bound infinity (-∞) or negative, or an upper bound negative.
It is then necessary to add in the vector of relations [line 19] the constants that declare that the last two lines of the matrix A are relative to the upper and lower bounds (add ConsType.UPPER and ConsType.LOWER). Finally, the size of vector b must also be updated (adding two NaN values) which must be equal to the number of staves of the matrix A.
max X1 + 3X2 X1 + X2 ≥ 1 X1 + 1.4X2 ≤ 6 -5X1 + 3X2 = 5 with -1 ≤ X1 ≤ +1 -∞ ≤ X2 ≤ +∞
Let's solve the previous example using the matrix format. In order to represent the variable X1, which is bounded both inferiorly and superiorly, it is necessary to add to the matrix A a line for the upper bounds and one for the lower bounds [lines 13-14]. In the case of the variable X2, or of a free variable without limits, it is sufficient to specify a lower bound and an upper bound indefinite with the value NaN.
Recall that in order to set the free variables, or variables that can assume negative values, must be set a lower bound infinity (-∞) or negative, or an upper bound negative.
It is then necessary to add in the vector of relations [line 19] the constants that declare that the last two lines of the matrix A are relative to the upper and lower bounds (add ConsType.UPPER and ConsType.LOWER). Finally, the size of vector b must also be updated (adding two NaN values) which must be equal to the number of staves of the matrix A.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
import static org.ssclab.pl.milp.LP.NaN;
public class Example {
public static void main(String[] args) throws Exception {
double A[][]={
{ 1.0 , 1.0 },
{ 1.0 , 1.4 },
{-5.0 , 3.0 },
{ 1.0 , NaN },
{-1.0 , NaN }} ;
double b[]= { 1.0, 6.0 ,5.0, NaN, NaN };
double c[]= { 1.0, 3.0 };
ConsType[] rel= {ConsType.GE, ConsType.LE, ConsType.EQ, ConsType.UPPER, ConsType.LOWER};
LinearObjectiveFunction of = new LinearObjectiveFunction(c, GoalType.MAX);
ListConstraints constraints = new ListConstraints();
for(int i=0; i < A.length; i++) {
constraints.add(new Constraint(A[i], rel[i], b[i]));
}
LP lp = new LP(of,constraints);
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("Value :"+solution.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 1.6
Consider the following LP problem:
We want to solve this problem using the text format once again. This problem is analogous to Problem 1.1, with the only addition of upper and lower bounds. In the text format, to define the upper u and lower bounds l, it is necessary to add a line for each variable to be constrained [lines 14-15] with statements such as: " u ≤ x ≤ l " , " x ≤ l " , " x ≥ u ".
We recall that to make a variable free or a variable that can take negative values, it is necessary to set a lower bound to -infinity (both +infinity and -infinity are represented with '.' in the text format) or a negative value, or an upper bound to a negative value (see Example 1.4). In the text format, upper and lower bound declarations like those in [lines 14-15] allow the variable to take negative values.
Finally, when printing the solution, it is possible to retrieve the upper and lower bounds for each variable [line 23] that were previously set during the problem formulation.
min 3Y + 2X2 + 4Z + 7X4 + 8X5 5Y + 2X2 + 3X4 ≥ 9 3Y + X2 + Z + 5X5 = 12 6Y + 3X2 + 4Z + 5X4 ≤ 124 Y + 3X2 + 3X4 + 6X5 ≤ 854 con Y, X4, X5 ≥ 0 -1 ≤ X2 ≤ +6 -∞ ≤ Z ≤ +∞
We want to solve this problem using the text format once again. This problem is analogous to Problem 1.1, with the only addition of upper and lower bounds. In the text format, to define the upper u and lower bounds l, it is necessary to add a line for each variable to be constrained [lines 14-15] with statements such as: " u ≤ x ≤ l " , " x ≤ l " , " x ≥ u ".
We recall that to make a variable free or a variable that can take negative values, it is necessary to set a lower bound to -infinity (both +infinity and -infinity are represented with '.' in the text format) or a negative value, or an upper bound to a negative value (see Example 1.4). In the text format, upper and lower bound declarations like those in [lines 14-15] allow the variable to take negative values.
Finally, when printing the solution, it is possible to retrieve the upper and lower bounds for each variable [line 23] that were previously set during the problem formulation.
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 +4Z +7x4 +8X5 \n"+
" 5Y +2x2 +3X4 >= 9 \n"+
" 3Y + X2 + Z +5X5 = 12 \n"+
" 6Y +3.0x2 +4Z +5X4 <= 124\n"+
" Y +3x2 +3X4 +6X5 <= 854\n"+
"-1<= x2 <= 6\n"+
". <= z <= .\n";
LP lp = new LP(pl_string);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMAL) {
Solution soluzione=lp.getSolution();
for(Variable var:soluzione.getVariables()) {
SscLogger.log("Variable "+var.getName() +": "+var.getLower() + " <= ["+var.getValue()+"] <= "+var.getUpper());
}
SscLogger.log("Value:"+soluzione.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 1.7
Consider the following LP problem reported in Example 1.4:
Example 1.4 can be represented with a fourth format called "sparse format" [lines 17-40]. When the processing engine analyzes a row with a defined TYPE (other than '.'), it begins defining a new entity and assigns it a marker, specified in the ROW_ column. This marker represents the name of the entity, which can be either a constraint or the objective function. Specifically, if the engine detects that the TYPE is set to 'MAX' or 'MIN', it starts defining the objective function. If instead the TYPE is 'EQ' (=), 'LE' (≤) o 'GE' (≥), it begins defining a constraint and assigns a name to these entities (the marker specified in ROW_). The TYPE column can take one of the following values: EQ, LE, GE, UPPER, LOWER, MAX, MIN.
Subsequently, the variables of the problem are specified by setting the COL_ column, which identifies the variable itself, and indicating the corresponding coefficient in the COEF column. If a row contains a value in ROW_ but has an undefined TYPE ('.'), a new entity is not being defined; instead, the coefficient that a variable takes on that entity is being specified. In this case, the COEF value indicates the coefficient that the variable, specified in COL_, takes on the entity corresponding to the marker present in ROW_.
In addition to the variable names (chosen by the developer), the COL_ column can also contain the value "RHS", which is used to define the known terms (the right-hand side) of the constraints. While the names of the variables can be freely chosen, the name for the rhs values must necessarily be indicated using the "RHS" notation.
Once the problem is defined, it is necessary to declare, in the reading format [line 44], the name and type (with the corresponding length) of the four columns required by this format: TYPE, COL_, ROW_, and COEF. The names of the variables to be assigned to the respective columns must necessarily be TYPE, COL_, ROW_, and COEF.
To be able to instantiate an LP object with this format, the FormatType.SPARSE constant must be passed as an argument to inform the LP object of the type of format used [line 46]. This format is particularly suitable for picking up problems in database tables, since the structure of the requested table is always the same: it is sufficient that this defines the columns TYPE, COL_, ROW_ and COEF.
Finally, it should be remembered that the values of the TYPE and COL_ column can be expressed both in uppercase and in lowercase; in both cases they will be returned to the upper case; while for the column ROW_ expressing the name of a entity simultaneously in lower case and in upper case, within the same formulation, means to declare two different names (and therefore two entities).
max X1 + 3X2 X1 + X2 ≥ 1 X1 + 1.4X2 ≤ 6 -5X1 + 3X2 = 5 with -1 ≤ X1 ≤ +1 -∞ ≤ X2 ≤ +∞
Example 1.4 can be represented with a fourth format called "sparse format" [lines 17-40]. When the processing engine analyzes a row with a defined TYPE (other than '.'), it begins defining a new entity and assigns it a marker, specified in the ROW_ column. This marker represents the name of the entity, which can be either a constraint or the objective function. Specifically, if the engine detects that the TYPE is set to 'MAX' or 'MIN', it starts defining the objective function. If instead the TYPE is 'EQ' (=), 'LE' (≤) o 'GE' (≥), it begins defining a constraint and assigns a name to these entities (the marker specified in ROW_). The TYPE column can take one of the following values: EQ, LE, GE, UPPER, LOWER, MAX, MIN.
Subsequently, the variables of the problem are specified by setting the COL_ column, which identifies the variable itself, and indicating the corresponding coefficient in the COEF column. If a row contains a value in ROW_ but has an undefined TYPE ('.'), a new entity is not being defined; instead, the coefficient that a variable takes on that entity is being specified. In this case, the COEF value indicates the coefficient that the variable, specified in COL_, takes on the entity corresponding to the marker present in ROW_.
In addition to the variable names (chosen by the developer), the COL_ column can also contain the value "RHS", which is used to define the known terms (the right-hand side) of the constraints. While the names of the variables can be freely chosen, the name for the rhs values must necessarily be indicated using the "RHS" notation.
Once the problem is defined, it is necessary to declare, in the reading format [line 44], the name and type (with the corresponding length) of the four columns required by this format: TYPE, COL_, ROW_, and COEF. The names of the variables to be assigned to the respective columns must necessarily be TYPE, COL_, ROW_, and COEF.
To be able to instantiate an LP object with this format, the FormatType.SPARSE constant must be passed as an argument to inform the LP object of the type of format used [line 46]. This format is particularly suitable for picking up problems in database tables, since the structure of the requested table is always the same: it is sufficient that this defines the columns TYPE, COL_, ROW_ and COEF.
Finally, it should be remembered that the values of the TYPE and COL_ column can be expressed both in uppercase and in lowercase; in both cases they will be returned to the upper case; while for the column ROW_ expressing the name of a entity simultaneously in lower case and in upper case, within the same formulation, means to declare two different names (and therefore two entities).
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.FormatTypeInput.FormatType;
import org.ssclab.pl.milp.LP;
import org.ssclab.pl.milp.Solution;
import org.ssclab.pl.milp.SolutionType;
import org.ssclab.pl.milp.Variable;
import org.ssclab.ref.InputString;
public class Example {
public static void main(String[] args) throws Exception {
String lp_sparse =
// TYPE COL_ ROW_ COEF
" MAX . profit . \n" +
" GE . row1 . \n" +
" LE . row2 . \n" +
" EQ . row3 . \n" +
" UPPER . lim_sup . \n" +
" LOWER . lim_inf . \n" +
" . X1 profit 1 \n" +
" . X1 row1 1 \n" +
" . X1 row2 1 \n" +
" . X1 row3 -5 \n" +
" . X1 lim_sup 1 \n" +
" . X1 lim_inf -1 \n" +
" . X2 profit 3 \n" +
" . X2 row1 1 \n" +
" . X2 row2 1.4 \n" +
" . X2 row3 3 \n" +
" . X2 lim_sup . \n" +
" . X2 lim_inf . \n" +
" . RHS row1 1 \n" +
" . RHS row2 6 \n" +
" . RHS row3 5 \n" ;
InputString lp_input = new InputString(lp_sparse);
lp_input.setInputFormat("TYPE:varstring(5), COL_:varstring(3) , ROW_:varstring(7), COEF:double");
LP lp = new LP(lp_input,FormatType.SPARSE);
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("o.f. value:"+solution.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 1.8
Consider the following LP problem:
In this case we want to solve the LP problem whose formulation is in a text file (.txt). We call this pl_problem.txt files and use, for the representation of the problem, the format coefficients. In pl_problem.txt files we will have the following content:
min 3Y1 + Y2 + 4Y3 + 7Y4 + 8Y5 5Y1 + 2Y2 + 3Y4 ≥ 9 3Y1 + Y2 + Y3 + 5Y5 ≥ 12 6Y1 + 3Y2 + 4Y3 + 5Y4 ≤ 124 1Y1 + 3Y2 + 3Y4 + 6Y5 ≤ 854 with Y1, Y4, Y5 ≥ 0 0 ≤ Y2 ≤ +6 1 ≤ Y3 ≤ +∞
In this case we want to solve the LP problem whose formulation is in a text file (.txt). We call this pl_problem.txt files and use, for the representation of the problem, the format coefficients. In pl_problem.txt files we will have the following content:
3 1 4 7 8 min . 5 2 0 3 0 ge 9 3 1 1 0 5 ge 12 6 3 4 5 0 le 124 1 3 0 3 6 le 854 . 6 . . . upper . 0 0 1 0 0 lower .Defined such content SSC should be informed that the problem is contained in a [line 12] file. If you have a significant number of variables (in this case only 5, but it may be many more) they can declare [line 13] with the syntax "Y1-Y5: double", that way you declare 5 different variables (Y1, Y2, Y3, Y4, Y5) of type double.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.LP;
import org.ssclab.pl.milp.Solution;
import org.ssclab.pl.milp.SolutionType;
import org.ssclab.pl.milp.Variable;
import org.ssclab.ref.InputFile;
public class Example {
public static void main(String[] args) throws Exception {
InputFile input = new InputFile("c:/dir_pl/pl_problem.txt");
input.setInputFormat("Y1-Y5:double, TYPE:varstring(10), RHS:double");
LP lp=new LP(input);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMAL) {
Solution soluzione=lp.getSolution();
for(Variable var:soluzione.getVariables()) {
SscLogger.log("Variable name :"+var.getName() + " value:"+var.getValue());
}
SscLogger.log("o.f. value:"+soluzione.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 1.9
Consider the LP problem in example 1.7:
In this example, we aim to retrieve the problem, formulated in sparse format, from a table in an Oracle database (RDBMS). Recall that in the sparse format, the input required to solve an LP problem must include the columns TYPE, ROW_, COL_, and COEF. We also include the field ID_PROBLEM in the table so that multiple problems can be stored in this table and identified through this field. Let's name the Oracle table that will contain these fields PL_PROBLEM; this table can be created with the following DDL (Data Definition Language) statement:
Invoking addLibrary() [line 18] allows you to add a library (named "DB_ORACLE") to the current SSC session, representing a connection to the Oracle DB. After this invocation, the addLibrary() method returns a Library object, which serves as an interface to the database. From this interface, we can [line 20] obtain, through an SQL query, an Input object that references the records related to the problem stored in the table, specifically the one with identifier 13. Once this input is obtained, it can be passed to the LP constructor [line 25] to execute the Simplex.
It should be noted that in the LP class constructor, in addition to the Input object that contains a reference to the records related to the problem formulation, the previously created SSC session is also passed as a second argument [line 25]. This prevents the LP object from instantiating a second, unnecessary session. Finally, as a third argument, a constant (FormatType.SPARSE) is passed, explicitly indicating the format (sparse) in which the problem was formulated. Naturally, any other RDBMS for which a JDBC driver is available can be used in place of the Oracle database.
max X1 + 3X2 X1 + X2 ≥ 1 X1 + 1.4X2 ≤ 6 -5X1 + 3X2 = 5 with -1 ≤ X1 ≤ +1 -∞ ≤ X2 ≤ +∞
In this example, we aim to retrieve the problem, formulated in sparse format, from a table in an Oracle database (RDBMS). Recall that in the sparse format, the input required to solve an LP problem must include the columns TYPE, ROW_, COL_, and COEF. We also include the field ID_PROBLEM in the table so that multiple problems can be stored in this table and identified through this field. Let's name the Oracle table that will contain these fields PL_PROBLEM; this table can be created with the following DDL (Data Definition Language) statement:
CREATE TABLE "PL_PROBLEM"
("TYPE" VARCHAR2(8),
"COL_" VARCHAR2(15),
"ROW_" VARCHAR2(15),
"COEF" FLOAT(24),
"ID_PROBLEM" NUMBER(4)
)
Finally, we insert in the table the following records
(by null, it means the null value, not the string "null"):
MAX null profit null 13 GE null row1 null 13 LE null row2 null 13 EQ null row3 null 13 UPPER null lim_sup null 13 LOWER null lim_inf null 13 null X1 profit 1 13 null X1 row1 1 13 null X1 row2 1 13 null X1 row3 -5 13 null X1 lim_sup 1 13 null X1 lim_inf -1 13 null X2 profit 3 13 null X2 row1 1 13 null X2 row2 1.4 13 null X2 row3 3 13 null X2 lim_sup null 13 null X2 lim_inf null 13 null RHS row1 1 13 null RHS row2 6 13 null RHS row3 5 13To retrieve the problem formulation from a table in a database, you need to download the JDBC driver for the respective database and instantiate a Connection object [lines 42-49]. Once a connection to the DB is obtained, SSC can access the DB through the concept of a library using the Connection object. SSC requires the creation of an SSC session [line 17] in order to allocate libraries. An SSC session represents the environment in which SSC operates. In previous examples, creating a session was not necessary because the LP object creates and uses its own implicit SSC session.
Invoking addLibrary() [line 18] allows you to add a library (named "DB_ORACLE") to the current SSC session, representing a connection to the Oracle DB. After this invocation, the addLibrary() method returns a Library object, which serves as an interface to the database. From this interface, we can [line 20] obtain, through an SQL query, an Input object that references the records related to the problem stored in the table, specifically the one with identifier 13. Once this input is obtained, it can be passed to the LP constructor [line 25] to execute the Simplex.
It should be noted that in the LP class constructor, in addition to the Input object that contains a reference to the records related to the problem formulation, the previously created SSC session is also passed as a second argument [line 25]. This prevents the LP object from instantiating a second, unnecessary session. Finally, as a third argument, a constant (FormatType.SPARSE) is passed, explicitly indicating the format (sparse) in which the problem was formulated. Naturally, any other RDBMS for which a JDBC driver is available can be used in place of the Oracle database.
import org.ssclab.context.Context;
import org.ssclab.context.Session;
import org.ssclab.library.Library;
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.FormatTypeInput.FormatType;
import org.ssclab.pl.milp.*;
import org.ssclab.ref.Input;
import java.sql.Connection;
import oracle.jdbc.pool.OracleDataSource;
public class Example {
public static void main(String[] args) throws Exception {
Session session = null;
try {
session = Context.createNewSession();
Library library_oracle=session.addLibrary("DB_ORACLE", connOracle());
Input select_id_13=library_oracle.getInputFromSQLQuery(
"select TYPE, COL_ , ROW_, COEF from PL_PROBLEM "+
"where ID_PROBLEM=13");
LP lp = new LP(select_id_13,session,FormatType.SPARSE);
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());
}
}
finally {
if(session!=null) session.close();
}
}
private static Connection connOracle() throws Exception {
OracleDataSource ods = new OracleDataSource();
String URL = "jdbc:oracle:thin:@//169.254.251.50:1521/XE";
ods.setURL(URL);
ods.setUser("system");
ods.setPassword("HAL9000");
return ods.getConnection();
}
}
Example 1.10
In the example below shows a simple LP problem. In this example you want
to highlight what are the values that the resolve method can return
according to the LP problem:
a) The problem admits an optimal solution
b) The problem has no feasible solutions
c) The problem has great Unlimited
d) Reaches the maximum number of possible iterations
e) A feasible solution is returned instead of an optimal solution
If the need is to obtain a feasible solution not necessarily optimal (case e), just invoke the setJustTakeFeasibleSolution () method giving it the value "true" (line 29). This option allows only the first phase of the simplex to be performed and to obtain a first (basic) allowable solution. In this case the value returned by the resolve () method (in case a feasible solution exists) will be SolutionType.FEASIBLE.
The maximum number of iterations can be changed by the analyst [line 27].
a) The problem admits an optimal solution
b) The problem has no feasible solutions
c) The problem has great Unlimited
d) Reaches the maximum number of possible iterations
e) A feasible solution is returned instead of an optimal solution
If the need is to obtain a feasible solution not necessarily optimal (case e), just invoke the setJustTakeFeasibleSolution () method giving it the value "true" (line 29). This option allows only the first phase of the simplex to be performed and to obtain a first (basic) allowable solution. In this case the value returned by the resolve () method (in case a feasible solution exists) will be SolutionType.FEASIBLE.
The maximum number of iterations can be changed by the analyst [line 27].
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.LP;
import org.ssclab.pl.milp.Solution;
import org.ssclab.pl.milp.SolutionType;
import org.ssclab.pl.milp.Variable;
import org.ssclab.ref.InputString;
public class Example {
public static void main(String[] args) throws Exception {
String lp_string =
"5 4 1 3 max . \n" +
"4 3 1 1 ge 2 \n" +
"1 -2 1 -1 le 2 \n" +
"3 2 1 1.4 le 6 \n" +
"9 8 4 1.7 le 7 \n" +
"5 3 -1 2.4 le 9 \n" +
"3 -2 -5 3 le 5 ";
InputString lp_input = new InputString(lp_string);
lp_input.setInputFormat("V1-V4:double, TYPE:varstring(8), RHS:double");
LP lp = new LP(lp_input);
SscLogger.log("Default number of iterations:"+lp.getNumMaxIteration());
lp.setNumMaxIteration(500);
//I require that the solution found, if it exists, be feasible and not necessarily optimal.
lp.setJustTakeFeasibleSolution(true);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.FEASIBLE) {
Solution solution=lp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Variable name :"+var.getName() + " value:"+var.getValue());
}
SscLogger.log("o.f. value of feasible solution:"+solution.getValue());
}
else if(solution_type==SolutionType.INFEASIBLE) {
SscLogger.log("Phase 1 of the simplex did not find feasible solutions:("+solution_type+")");
}
else if(solution_type==SolutionType.UNLIMITED) {
SscLogger.log("The problem has great Unlimited:("+solution_type+")");
}
else if(solution_type==SolutionType.MAX_ITERATIONS) {
SscLogger.log("Max iteration:("+solution_type+")");
}
else if(solution_type==SolutionType.OPTIMAL) {
// this section will never be reached as it has been set
// setJustTakeFeasibleSolution (true), the simplex can only return feasible solutions
}
}
}
Example 1.11
In the example below we want to solve the problem already faced in exercise 1.6,
with the particularity that the formulation of the problem (using the text format)
is stored in a file. We call this file pl_problem.txt. The file mentioned will contain the
following content:
min: 3Y +2x2 +4Z +7x4 +8X5 row1:5Y +2x2 +3X4 >= 9 row2:3Y + X2 +Z +5X5 = 12 Vin1:6Y +3.0x2 +4Z +5X4 <= 124 vin2: Y +3x2 +3X4 +6X5 <= 854 -1 <= x2 <= 6 . <= z <= .Unlike the formulation of example 1.6 in this case we have also associated with each constraint a label (name of the constraint) which is inserted before putting a name followed by two points at each constraint. In the code below, instructions have been added to retrieve information related to constraints, such as the name associated with the constraint and the type of constraint. It is worth noting that it is also possible to obtain the value that the LHS (left-hand side) of each constraint takes by assigning values to the unknown variables with the optimal solution. The LHS value is then compared to the corresponding RHS (right-hand side) value [lines 20-21]. It should be clarified that, in this specific case, given a linear programming problem AX <=> b , the LHS and RHS quantities referred to are AX (the LHS) and b (the RHS). Therefore, if variables are included on the right side of the inequality/equality sign in the problem definition, they will not be considered part of the RHS but will be grouped in the form: AX (LHS) and b (RHS).
import java.nio.file.Paths;
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
import java.util.ArrayList;
import java.util.Random;
public class Example {
public static void main(String[] args) throws Exception {
LP lp = new LP(Paths.get("C:\\pl_problem.txt"));
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMAL) {
Solution soluzione=lp.getSolution();
for(Variable var:soluzione.getVariables()) {
SscLogger.log("Variable name :"+var.getName() + " value :"+var.getValue());
}
for(SolutionConstraint sol_constraint: soluzione.getSolutionConstraint()) {
SscLogger.log("Constraint "+sol_constraint.getName()+" : value="+sol_constraint.getValue() +
"[ "+sol_constraint.getRel()+" "+sol_constraint.getRhs()+" ]" );
}
SscLogger.log("Optimal value:"+soluzione.getOptimumValue());
}
}
}
Example 1.12
Consider the following LP problem identical to Example 1.9:
In this example we want to recover the problem, formulated in the scattered format, from a text file called sparse_problem.txt containing the following listing:
It should be noted that the LP class constructor is passed as argument an object of type InputFile that refers to the file containing the problem.
max X1 + 3X2 X1 + X2 ≥ 1 X1 + 1.4X2 ≤ 6 -5X1 + 3X2 = 5 con -1 ≤ X1 ≤ +1 -∞ ≤ X2 ≤ +∞
In this example we want to recover the problem, formulated in the scattered format, from a text file called sparse_problem.txt containing the following listing:
MAX . profit . GE . row1 . LE . row2 . EQ . row3 . UPPER . lim_sup . LOWER . lim_inf . . X1 profit 1 . X1 row1 1 . X1 row2 1 . X1 row3 -5 . X1 lim_sup 1 . X1 lim_inf -1 . X2 profit 3 . X2 row1 1 . X2 row2 1.4 . X2 row3 3 . X2 lim_sup . . X2 lim_inf . . RHS row1 1 . RHS row2 6 . RHS row3 5
It should be noted that the LP class constructor is passed as argument an object of type InputFile that refers to the file containing the problem.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.FormatTypeInput.FormatType;
import org.ssclab.pl.milp.LP;
import org.ssclab.pl.milp.Solution;
import org.ssclab.pl.milp.SolutionType;
import org.ssclab.pl.milp.Variable;
import org.ssclab.ref.InputFile;
public class Example {
public static void main(String[] args) throws Exception {
InputFile input_sparse = new InputFile("C:/ssc_project/sparse_problem.txt");
input_sparse.setInputFormat("TYPE:varstring(5), COL_:varstring(3) , ROW_:varstring(7), COEF:double");
LP lp = new LP(input_sparse,FormatType.SPARSE);
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("o.f. value :"+solution.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 1.13
The example below shows an LP problem generated by pseudocausal numbers,
with the particularity that the vector b is made to take values of the order
of millions of millions. The consequence of working with large numbers may not make
the phase 1 of the simplex converge. In this particular case, if the tolerance ε of
the optimal value z of the objective function relative to the phase 1 is not modified,
the resolution of the problem may not give admissible solutions.
In other words, at the end of phase 1, if | z | > ε then the problem does not
allow solutions. In this
case the tolerance it is increased from 1E-8 (default value) to 1E-5.
In other words, if | z | < ε the problem admits solutions.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
import java.util.ArrayList;
import java.util.Random;
public class Example {
public static void main(String arg[]) throws Exception {
final int M = 445; // rows
final int N = 345; // cols
Random random = new Random();
double[] c = new double[N];
double[] b = new double[M];
double[][] A = new double[M][N];
for (int j = 0; j < N; j++) c[j] = (double) (random.nextInt(20));
for (int i = 0; i < M; i++) b[i] = (double) random.nextInt(100000000);
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++) A[i][j] = (double) random.nextInt(10);
LinearObjectiveFunction f = new LinearObjectiveFunction(c, GoalType.MAX);
ArrayList< Constraint > constraints = new ArrayList< Constraint >();
for(int i=0; i < A.length; i++) {
constraints.add(new Constraint(A[i], ConsType.LE, b[i]));
}
LP lp = new LP(f,constraints);
lp.setCEpsilon(EPSILON._1E_M5);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMAL) {
Solution solution=lp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Variable :"+var.getName() + " value:"+var.getValue());
}
SscLogger.log("Value o.f. :"+solution.getOptimumValue());
}
else SscLogger.log("no optimal solution. Tipo di soluzione:"+solution_type);
}
}
Example 1.14
Consider the following LP problem:
To solve this problem (identical to problem 1.1) with an implementation of the parallel simplex, we must add the instruction present in line 24. With this instruction we specify the number of threads to be used to execute an instance of the parallel simplex (in this case 4). Among the selectable values there is also the value LPThreadsNumber.AUTO, with which the number of threads to be used to execute the parallel simplex is delegated to the system. It should be remembered that advantages on the time of execution of the method are obtained with at least 4 or more physical cores.
max X1 + 3X2 X1 + X2 ≥-1 X1 + 1.4X2 ≤ 6 -5X1 + 3X2 = 5 con X1, X2 ≥ 0
To solve this problem (identical to problem 1.1) with an implementation of the parallel simplex, we must add the instruction present in line 24. With this instruction we specify the number of threads to be used to execute an instance of the parallel simplex (in this case 4). Among the selectable values there is also the value LPThreadsNumber.AUTO, with which the number of threads to be used to execute the parallel simplex is delegated to the system. It should be remembered that advantages on the time of execution of the method are obtained with at least 4 or more physical cores.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.LP;
import org.ssclab.pl.milp.Solution;
import org.ssclab.pl.milp.SolutionType;
import org.ssclab.pl.milp.Variable;
import org.ssclab.ref.InputString;
import org.ssclab.pl.milp.util.LPThreadsNumber;
public class Example {
public static void main(String[] args) throws Exception {
String lp_string =
" 1 3 max . \n" +
" 1 1 ge -1 \n" +
" 1 1.4 le 6 \n" +
"-5 3 eq 5";
InputString lp_input = new InputString(lp_string);
lp_input.setInputFormat("X1-X2:double, TYPE:varstring(3), RHS:double");
LP lp = new LP(lp_input);
lp.setThreadsNumber(LPThreadsNumber.N_4);
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("Not optimal solution:"+solution_type);
}
}
Example 1.15
Consider the following LP problem:
To solve this problem we use an ArrayList to store the individual lines where the problem is formulated.
min 3Y + 2X2 + 4Z + 7X4 + 8X5 5Y + 2X2 ≥ 9 - 3X4 3Y + X2 + Z + 5X5 = 12 6Y + 3X2 + 4Z ≤ 124 - 5X4 Y + 3X2 + 6X5 ≤ 854 - 3X4 with Y, X2, Z3, X4, X5 ≥ 0
To solve this problem we use an ArrayList to store the individual lines where the problem is formulated.
import java.util.ArrayList;
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
public class Example {
public static void main(String[] args) throws Exception {
ArrayList< String > constraints = new ArrayList< String >();
constraints.add("min: 3Y +2x2 +4Z +7x4 +8X5 ");
constraints.add(" 5Y +2x2 +3X4 >= 9");
constraints.add(" 3Y + X2 + Z +5X5 = 12");
constraints.add(" 6Y +3x2 +4Z +5X4 <= 124");
constraints.add(" Y +3x2 +3X4 +6X5 <= 854");
LP lp = new LP(constraints);
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("Not optimal solution:"+solution_type);
}
}
Example 1.16
Consider the following LP problem:
We want to solve this problem using a new representation format that allows formulating the problem via a JSON. In this format, the objective function must be expressed as an object with the key "objective" [line 12], while the constraints should be placed as an array of objects under the JSON key 'constraints' [line 22]. Finally, the upper and lower bounds are inserted into the object with the key "bounds." We can also assign names to the constraints using the key "name" [line 31].
It's important to note that in this representation format for an LP problem, both the keys ("objective", "coefficients", "constraints", etc.) and the values ("max", "min", "eq", etc.) must be written in lowercase. However, the names given to the variables are case-insensitive, meaning that "X3" and "x3" represent the same variable. Naturally, constraint names can be written in uppercase, lowercase, or a mix, but keep in mind that they are case-sensitive.
According to JSON specifications, keys must be unique. For example, in the object that defines the objective function (the one with the "objective" section), a variable can only appear once to satisfy the rules for proper JSON compilation.
It is essential to clarify that if a negative lower bound is defined, as in this case, the affected variable (Y) is no longer subject to non-negativity constraints. Additionally, to declare free variables, those without a lower bound (with the lower bound no longer being zero but negative infinity), you simply need to specify an undefined lower bound. If an undefined value is declared for a lower or upper bound, SSC converts these values to negative infinity in the first case and positive infinity in the second. In JSON format, an undefined value is represented by null (without quotes) [line 62].
One of the advantages of this format is that if a variable is not present in a constraint or in the objective function, it can be omitted, unlike the matrix or coefficient format where it must be represented with a coefficient of zero. It should be noted that in SSC, by default, the variables of an LP problem are considered non-negative (≥ 0), unless otherwise specified.
Once the problem is represented, you need to create an object of the JsonProblem class, passing the string containing the JSON as an argument. This object is sufficient to instantiate an object of the LP class and execute the Simplex algorithm. Once the Simplex algorithm is executed, the resolve() method returns the type of solution found. If the solution is optimal, you can retrieve the variable values and the optimal value of the objective function.
min 3Y + 2X2 + 4X3 + 7X4 + 8X5 5Y + 2X2 - 3X4 ≥ 9 3Y + X2 + X3 + 5X5 = 12 6Y + 3X2 + 4X3 - 5X4 ≤ 124 with X3, X4, X5 ≥ 0 -1 ≤ Y ≤ +4 -∞ ≤ X2 ≤ +5
We want to solve this problem using a new representation format that allows formulating the problem via a JSON. In this format, the objective function must be expressed as an object with the key "objective" [line 12], while the constraints should be placed as an array of objects under the JSON key 'constraints' [line 22]. Finally, the upper and lower bounds are inserted into the object with the key "bounds." We can also assign names to the constraints using the key "name" [line 31].
It's important to note that in this representation format for an LP problem, both the keys ("objective", "coefficients", "constraints", etc.) and the values ("max", "min", "eq", etc.) must be written in lowercase. However, the names given to the variables are case-insensitive, meaning that "X3" and "x3" represent the same variable. Naturally, constraint names can be written in uppercase, lowercase, or a mix, but keep in mind that they are case-sensitive.
According to JSON specifications, keys must be unique. For example, in the object that defines the objective function (the one with the "objective" section), a variable can only appear once to satisfy the rules for proper JSON compilation.
It is essential to clarify that if a negative lower bound is defined, as in this case, the affected variable (Y) is no longer subject to non-negativity constraints. Additionally, to declare free variables, those without a lower bound (with the lower bound no longer being zero but negative infinity), you simply need to specify an undefined lower bound. If an undefined value is declared for a lower or upper bound, SSC converts these values to negative infinity in the first case and positive infinity in the second. In JSON format, an undefined value is represented by null (without quotes) [line 62].
One of the advantages of this format is that if a variable is not present in a constraint or in the objective function, it can be omitted, unlike the matrix or coefficient format where it must be represented with a coefficient of zero. It should be noted that in SSC, by default, the variables of an LP problem are considered non-negative (≥ 0), unless otherwise specified.
Once the problem is represented, you need to create an object of the JsonProblem class, passing the string containing the JSON as an argument. This object is sufficient to instantiate an object of the LP class and execute the Simplex algorithm. Once the Simplex algorithm is executed, the resolve() method returns the type of solution found. If the solution is optimal, you can retrieve the variable values and the optimal value of the objective function.
import org.ssclab.log.*;
import org.ssclab.pl.milp.*;
public class Example {
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 pl_json = """
{
"objective": {
"type": "min",
"coefficients": {
"Y": 3,
"X2": 2,
"X3": 4,
"X4": 7,
"X5": 8
}
},
"constraints": [
{
"coefficients": {
"Y": 5,
"X2": 2,
"X4":-3
},
"relation": "ge",
"rhs": 9,
"name":"VINCOLO1"
},
{
"coefficients": {
"Y": 3,
"X2": 1,
"X3": 1,
"X5": 5
},
"relation": "eq",
"rhs": 12,
"name":"VINCOLO2"
},
{
"coefficients": {
"Y": 6,
"X2": 3,
"X3": 4,
"X4":-5
},
"relation": "le",
"rhs": 124,
"name":"VINCOLO3"
}
],
"bounds": {
"Y": {
"lower": -1,
"upper": 4
},
"X2": {
"lower": null,
"upper": 5
}
}
}""";
LP lp = new LP(new JsonProblem(pl_json));
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("Not optimal solution:"+solution_type);
}
}
Example 1.17
Consider the following LP problem:
In this case we want to solve a LP problem whose formulation is in an external JSON file. We call this file pl_problem.json. In the file we will have the following content:
To be able to reference the json file you simply need to create an instance of the JsonProblem class, passing it as an argument a Path object containing the path to where the file is located [line 9].
min 3Y + 2X2 + 4X3 + 7X4 + 8X5 5Y + 2X2 - 3X4 ≥ 9 3Y + X2 + X3 + 5X5 = 12 6Y + 3X2 + 4X3 - 5X4 ≤ 124 with X3, X4, X5 ≥ 0 1 ≤ Y ≤ +4 -∞ ≤ X2 ≤ +5
In this case we want to solve a LP problem whose formulation is in an external JSON file. We call this file pl_problem.json. In the file we will have the following content:
{
"objective": {
"type": "min",
"coefficients": {
"Y": 3,
"X2": 2,
"X3": 4,
"X4": 7,
"X5": 8
}
},
"constraints": [
{
"coefficients": {
"Y": 5,
"X2": 2,
"X4": -3
},
"relation": "ge",
"rhs": 9,
"name": "VINCOLO1"
},
{
"coefficients": {
"Y": 3,
"X2": 1,
"X3": 1,
"X5": 5
},
"relation": "eq",
"rhs": 12,
"name": "VINCOLO2"
},
{
"coefficients": {
"Y": 6,
"X2": 3,
"X3": 4,
"X4": -5
},
"relation": "le",
"rhs": 124,
"name": "VINCOLO3"
}
],
"bounds": {
"Y": {
"lower": 1,
"upper": 4
},
"X2": {
"lower": null,
"upper": 5
}
}
}
To be able to reference the json file you simply need to create an instance of the JsonProblem class, passing it as an argument a Path object containing the path to where the file is located [line 9].
import java.nio.file.Paths;
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
public class Example {
public static void main(String[] args) throws Exception {
LP lp = new LP(new JsonProblem(Paths.get("C:/appo/pl_problem.json")));
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("Not optimal solution:"+solution_type);
}
}
Esempio 1.18
Consider the following LP problem:
min 3Y + 2X2 + 4X3 + 7X4 + 8X5 5Y + 2X2 ≥ 9 - 3X4 3Y + X2 + X3 + 5X5 = 12 6Y + 3X2 + 4X3 ≤ 124 - 5X4 Y + 3X2 + 6X5 ≤ 854 - 3X4 con Y, X2, X3, X4, X5 ≥ 0This example is identical to example 1.1, with the distinction that the results of the identified optimal solution are stored in an object of the class JsonSolution, which allows saving the results either in an external JSON file, or a string containing the JSON, or as a JsonObject from the jakarta.json library. In this example, we will save the solution in an external JSON file, and we will obtain the following content:
{
"meta": {
"executionTimestamp": "2024-10-02 20:41:04",
"problemTitle": "Example 1.18",
"problemDescription": "LP problem",
"threads": 1,
"iterations": 3,
"optimizationDuration": "00:00:00:021",
"averageError": 2.886579864025407e-14,
"maxError": 1.1368683772161604e-13
},
"objectiveType": "min",
"status": "optimal",
"solution": {
"objectiveValue": 12.0,
"variables": {
"X2": {
"value": 0.0,
"lower": 0.0,
"upper": null
},
"X3": {
"value": 0.0,
"lower": 0.0,
"upper": null
},
"X4": {
"value": 0.0,
"lower": 0.0,
"upper": null
},
"X5": {
"value": 0.0,
"lower": 0.0,
"upper": null
},
"Y": {
"value": 4.0,
"lower": 0.0,
"upper": null
}
}
}
}
It is important to emphasize that various details about the identified solution can be optionally included
in the JSON by adding the corresponding SolutionDetail constants to the getSolutionAsJson() method of the LP
(or MILP) class. In this case, by adding INCLUDE_BOUNDS and INCLUDE_META, the basic information will be supplemented
with the upper and lower bounds, along with metadata about the computation, such as execution times, the number of
threads, etc. If no arguments are passed to the getSolutionAsJson() method, only the basic information will be stored.
import org.ssclab.pl.milp.*;
import static org.ssclab.pl.milp.SolutionDetail.*;
public class Example {
public static void main(String[] args) throws Exception {
String pl_string =
"min: 3Y +2x2 +4x3 +7x4 +8X5 \n"+
" 5Y +2x2 >= 9 -3X4 \n"+
" 3Y + X2 + X3 +5X5 = 12 \n" +
" 6Y+3.0x2 +4X3 <= 124 -5X4 \n" +
" y + 3x2 +6X5 <= 854 -3X4 ";
LP lp=new LP(pl_string).setTitle("Example 1.18");
lp.resolve();
lp.getSolutionAsJson(INCLUDE_BOUNDS,INCLUDE_META).saveToFile("c:\\solution.json");
}
}
Example 1.19
Consider the following LP problem:
This example is identical to example 1.1, with the difference that the results, normally displayed on the standard console, are saved to an external text file (result_lp.txt) via log redirection [line 16].
min 3Y + 2X2 + 4X3 + 7X4 + 8X5 5Y + 2X2 ≥ 9 - 3X4 3Y + X2 + X3 + 5X5 = 12 6Y + 3X2 + 4X3 ≤ 124 - 5X4 Y + 3X2 + 6X5 ≤ 854 - 3X4 with Y, X2, X3, X4, X5 ≥ 0
This example is identical to example 1.1, with the difference that the results, normally displayed on the standard console, are saved to an external text file (result_lp.txt) via log redirection [line 16].
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
public class Example {
public static void main(String[] args) throws Exception {
String pl_problem =
" min: 3Y +2x2 +4x3 +7x4 +8X5 \n"+
" 5Y +2x2 >= 9 -3X4 \n"+
" 3Y + X2 +X3 +5X5 = 12 \n"+
" 6Y+3.0x2 +4X3 <= 124-5X4 \n"+
" y + 3x2 +6X5 <= 854-3X4 \n";
SscLogger.setLogToFile("c:\\ssc\\result_lp.txt");
LP lp = new LP(pl_problem);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMAL) {
Solution soluzione=lp.getSolution();
for(Variable var:soluzione.getVariables()) {
SscLogger.log("Variable name :"+var.getName() + " value :"+var.getValue());
}
SscLogger.log("Objective function value:"+soluzione.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 1.20
Consider the following LP problem:
This example illustrates how to use operators and mathematical functions directly in the problem formulation using the notation with square brackets []. This allows for the representation of calculated constants [pi]=π , [e]=e, fractions [10/3] numbers in scientific notation [6000E-3], operations and mathematical functions [sqrt(44) * log(2)] in an intuitive and flexible way. The notation [] must completely replace the coefficient or number you want to represent.
min (10/3)Y + (3*π)X2 + 4X3 + 7X4 + 8X5 5Y + 2X2 ≥ 9 - 3X4 3Y + X2 + X3 + 5X5 = sqrt(44)*log(2) (π/2)Y + 3.1X2 + 6X5 ≤ e^3 - 3X4 Y ≥ 6000E-3 with X2, X3, X4, X5 ≥ 0
This example illustrates how to use operators and mathematical functions directly in the problem formulation using the notation with square brackets []. This allows for the representation of calculated constants [pi]=π , [e]=e, fractions [10/3] numbers in scientific notation [6000E-3], operations and mathematical functions [sqrt(44) * log(2)] in an intuitive and flexible way. The notation [] must completely replace the coefficient or number you want to represent.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
public class Example {
public static void main(String[] args) throws Exception {
String pl_problem =
"min: [10/3]Y + [3 * pi]x2 + 4X3 + 7X4 + 8X5 \n"+
" 5Y +2x2 >= 9 -3X4 \n"+
" 3Y + X2 + X3 +5X5 = [sqrt(44) * log(2)] \n"+
" [pi/2]Y +3.1x2 + 6X5 <= [e^3] -3X4 \n"+
" Y <= [6000E-3] ";
LP lp = new LP(pl_problem);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMAL) {
Solution soluzione=lp.getSolution();
for(Variable var:soluzione.getVariables()) {
SscLogger.log("Variable name :"+var.getName() + " value :"+var.getValue());
}
SscLogger.log("Objective function value:"+soluzione.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 1.21
Consider the following LP problem:
We want to solve this problem using the text format again. This problem includes a constraint, highlighted in bold, where the same linear combination of decision variables has both an upper and a lower bound. With the sparse format, it is possible to represent these types of constraints in a single line [line 13].
We have already mentioned that in the text format, the definition of upper and lower bounds on variables is done using statements such as: "u ≤ x ≤ l" , "x ≤ l" , "x ≥ u". These statements can also be listed on the same line [line 14], using a comma as a separator.
min 3Y + 2X2 + 4Z + 7X4 + 8X5 5Y + 2X2 + 3X4 ≥ 9 3Y + X2 + Z + 5X5 = 12 6Y + 3X2 + 4Z + 5X4 ≤ 124 23 ≤ Y + 3X2 + 3X4 + 6X5 ≤ 854 with X4, X5 ≥ 0 Y ≥ 1 -1 ≤ X2 ≤ +6 -∞ ≤ Z ≤ +∞
We want to solve this problem using the text format again. This problem includes a constraint, highlighted in bold, where the same linear combination of decision variables has both an upper and a lower bound. With the sparse format, it is possible to represent these types of constraints in a single line [line 13].
We have already mentioned that in the text format, the definition of upper and lower bounds on variables is done using statements such as: "u ≤ x ≤ l" , "x ≤ l" , "x ≥ u". These statements can also be listed on the same line [line 14], using a comma as a separator.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
public class Esempio {
public static void main(String[] args) throws Exception {
String pl_string =
"min: 3Y +2x2 +4Z +7x4 +8X5 \n"+
" 5Y +2x2 +3X4 >= 9 \n"+
" 3Y + X2 + Z +5X5 = 12 \n"+
" 6Y +3.0x2 +4Z +5X4 <= 124\n"+
"23 <= Y +3x2 +3X4 +6X5 <= 854\n"+
"-1<= x2 <= 6 , . <= z <= . , Y >=1";
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() +": "+var.getLower() + " <= ["+var.getValue()+"] <= "+var.getUpper());
}
SscLogger.log("Objective function value:"+solution.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 2.1
Consider the following problem of mixed integer linear programming
(MILP) :
This issue presents the variables X2, X3, X4, X5 integer, while the X1 variable is not. In SSC to resolve a MILP problem simply must introduce an additional line in format coefficients [line 20] to declare integer variables. Placing 1 on the line of the "integer" the variable is declared as a integer .
Another difference is that in this case must instantiate the object MILP [line 25] and not the LP object.
min 3X1 + X2 + 4X3 + 7X4 + 8X5 5X1 + 2X2 + 3X4 ≤ 9 3X1 + X2 + X3 + 5X5 ≥ 12 6X1 + 3X2 + 4X3 + 5X4 ≥ 124 1X1 + 3X2 + 3X4 + 6X5 ≥ 854 with X2, X3, X4, X5 ∈ ℤ 1 ≤ X2 ≤ +6 1 ≤ X3 ≤ +∞ X1, X4, X5 ≥ 0
This issue presents the variables X2, X3, X4, X5 integer, while the X1 variable is not. In SSC to resolve a MILP problem simply must introduce an additional line in format coefficients [line 20] to declare integer variables. Placing 1 on the line of the "integer" the variable is declared as a integer .
Another difference is that in this case must instantiate the object MILP [line 25] and not the LP object.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.MILP;
import org.ssclab.pl.milp.Solution;
import org.ssclab.pl.milp.SolutionType;
import org.ssclab.pl.milp.Variable;
import org.ssclab.ref.InputString;
public class Example {
public static void main(String[] args) throws Exception {
String milp_string=
"3 1 4 7 8 min . " +"\n"+
"5 2 0 3 0 le 9 " +"\n"+
"3 1 1 0 5 ge 12" +"\n"+
"6 3 4 5 0 ge 124" +"\n"+
"1 3 0 3 6 ge 854" +"\n"+
"0 1 1 0 0 lower . " +"\n"+
". 6 . . . upper . " +"\n"+
"0 1 1 1 1 integer . " +"\n" ;
InputString milp_input = new InputString(milp_string);
milp_input.setInputFormat("X1-X5:double, TYPE:varstring(20), RHS:double");
MILP milp=new MILP(milp_input);
SolutionType solution_type= milp.resolve();
if(solution_type==SolutionType.OPTIMAL) {
Solution solution=milp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Variable :"+var.getName() + " value:"+var.getValue());
}
SscLogger.log("o.f. value:"+solution.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 2.2
Consider the following problem MILP given by:
We want to solve this problem of integer linear programming using the matrix notation. To do this just add to the matrix of the coefficients a line to express what are the integer variables [line 21]. With the value 1 is declared integer variable, with 0 it is considered non-integer. Should also be declared to SSC that further added to line A is not related to constraints GE , LE, EQ, but the declaration of integer variables; this is accomplished by adding to the vector expressing the type of constraint rel[] the ConsType.INT value [line 26]. Finally it should be added to the vector b to a NaN value [line 23], to adapt the size of A with that of b as the size of b must coincide with the number of lines of the matrix A.
max X1 + 3.0X2 X1 + X2 ≥ 1 X1 + 1.4X2 ≤ 6 -5X1 + 3.0X2 ≤ 5 with X1, X2 ≥ 0 X1, X2 ∈ ℤ
We want to solve this problem of integer linear programming using the matrix notation. To do this just add to the matrix of the coefficients a line to express what are the integer variables [line 21]. With the value 1 is declared integer variable, with 0 it is considered non-integer. Should also be declared to SSC that further added to line A is not related to constraints GE , LE, EQ, but the declaration of integer variables; this is accomplished by adding to the vector expressing the type of constraint rel[] the ConsType.INT value [line 26]. Finally it should be added to the vector b to a NaN value [line 23], to adapt the size of A with that of b as the size of b must coincide with the number of lines of the matrix A.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.ConsType;
import org.ssclab.pl.milp.Constraint;
import org.ssclab.pl.milp.GoalType;
import org.ssclab.pl.milp.LinearObjectiveFunction;
import org.ssclab.pl.milp.MILP;
import org.ssclab.pl.milp.Solution;
import org.ssclab.pl.milp.SolutionType;
import org.ssclab.pl.milp.Variable;
import static org.ssclab.pl.milp.LP.NaN;
import java.util.ArrayList;
public class Example {
public static void main(String[] args) throws Exception {
double A[][]={
{ 1.0 , 1.0 },
{ 1.0 , 1.4 },
{-5.0 , 3.0 },
{ 1.0 , 1.0 }, //row of the matrix for defining integers
} ;
double b[]= { 1.0, 6.0 ,5.0, NaN};
double c[]= { 1.0, 3.0 };
ConsType[] rel= {ConsType.GE, ConsType.LE, ConsType.LE, ConsType.INT};
LinearObjectiveFunction f = new LinearObjectiveFunction(c, GoalType.MAX);
ArrayList< Constraint > constraints = new ArrayList< Constraint >();
for(int i=0; i < A.length; i++) {
constraints.add(new Constraint(A[i], rel[i], b[i]));
}
MILP lp = new MILP(f,constraints);
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("o.f. value:"+solution.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 2.3
Consider the following MILP problem :
We want to solve this problem of linear programming using the integer mixed sparse notation. To indicate that the variable Y2 is integer just add in the column of ROW_ a value to indicate what will be the marker that defines them. This marker (which we call "var_int", but may have any other name) must have an associated type INTEGER TYPE [line 23].
Once declared the marker of integer variables,, just declare [line 38] that the Y2 variable is var_int (ie INTEGER) placing in the column of COEF the value 1. If, however, a variable is not integer you must set the COEF column with 0 or, more briefly, neglecting the declaration. In fact, in the following formulation, Y1 variable is not integer and therefore it is not necessary to make the lack of association between the variable and the marker var_int placing the value 0 in COEF.
max Y1 + 3.0Y2 Y1 + Y2 ≥ 1 Y1 + 1.4Y2 ≤ 6 -5Y1 + 3.0Y2 = 5 with Y2 ∈ ℤ -1 ≤ Y1 ≤ +1 -∞ ≤ Y2 ≤ +∞
We want to solve this problem of linear programming using the integer mixed sparse notation. To indicate that the variable Y2 is integer just add in the column of ROW_ a value to indicate what will be the marker that defines them. This marker (which we call "var_int", but may have any other name) must have an associated type INTEGER TYPE [line 23].
Once declared the marker of integer variables,, just declare [line 38] that the Y2 variable is var_int (ie INTEGER) placing in the column of COEF the value 1. If, however, a variable is not integer you must set the COEF column with 0 or, more briefly, neglecting the declaration. In fact, in the following formulation, Y1 variable is not integer and therefore it is not necessary to make the lack of association between the variable and the marker var_int placing the value 0 in COEF.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.FormatTypeInput.FormatType;
import org.ssclab.pl.milp.MILP;
import org.ssclab.pl.milp.Solution;
import org.ssclab.pl.milp.SolutionType;
import org.ssclab.pl.milp.Variable;
import org.ssclab.ref.InputString;
public class Example {
public static void main(String[] args) throws Exception {
String lp_sparse =
// TYPE COL_ ROW_ COEF
" MAX . profit . \n" +
" GE . row1 . \n" +
" LE . row2 . \n" +
" EQ . row3 . \n" +
" UPPER . lim_sup . \n" +
" LOWER . lim_inf . \n" +
" INTEGER . var_int . \n" +
" . Y1 profit 1 \n" +
" . Y1 row1 1 \n" +
" . Y1 row2 1 \n" +
" . Y1 row3 -5 \n" +
" . Y1 lim_sup 1 \n" +
" . Y1 lim_inf -1 \n" +
" . Y2 profit 3 \n" +
" . Y2 row1 1 \n" +
" . Y2 row2 1.4 \n" +
" . Y2 row3 3 \n" +
" . Y2 lim_sup . \n" +
" . Y2 lim_inf . \n" +
" . Y2 var_int 1 \n" +
" . RHS row1 1 \n" +
" . RHS row2 6 \n" +
" . RHS row3 5 \n" ;
InputString lp_input = new InputString(lp_sparse);
lp_input.setInputFormat("TYPE:varstring(7), COL_:varstring(3) , ROW_:varstring(7), COEF:double");
MILP lp = new MILP(lp_input,FormatType.SPARSE);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMAL) {
Solution solution=lp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Variable :"+var.getName() + " value:"+var.getValue());
}
SscLogger.log("o.f. value:"+solution.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 2.4
Consider the following problem of mixed integer linear programming (MILP)
with some binary variables:
This problem has integer variables, and binary. while K3 variable is not subject to any constraint of entirety. To declare a binary variable simply add a line with TYPE "binary" [line 22]. If the i-th variable is binary just put one in the corresponding line of the binary. It is recalled that a variable can not be simultaneously both binary that integer. In our case the variables K1 and K4 are binary while K2 and K5 variables are integer.
min 3K1 + K2 + 4K3 + 7K4 + 8K5
5K1 + 2K2 + 3K4 ≤ 9
3K1 + K2 + K3 + 5K5 ≥ 12
6K1 + 3K2 + 4K3 + 5K4 ≥ 124
1K1 + 3K2 + 3K4 + 6K5 ≥ 854
with K2, K5 ∈ ℤ
K1, K4 ∈ {0,1}
1 ≤ K2 ≤ +6
1 ≤ K3 ≤ +∞
con K1, K4, K5 ≥ 0
This problem has integer variables, and binary. while K3 variable is not subject to any constraint of entirety. To declare a binary variable simply add a line with TYPE "binary" [line 22]. If the i-th variable is binary just put one in the corresponding line of the binary. It is recalled that a variable can not be simultaneously both binary that integer. In our case the variables K1 and K4 are binary while K2 and K5 variables are integer.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.MILP;
import org.ssclab.pl.milp.Solution;
import org.ssclab.pl.milp.SolutionType;
import org.ssclab.pl.milp.Variable;
import org.ssclab.ref.InputString;
public class Example {
public static void main(String[] args) throws Exception {
String milp_string=
"3 1 4 7 8 min . " +"\n"+
"5 2 0 3 0 le 9 " +"\n"+
"3 1 1 0 5 ge 12" +"\n"+
"6 3 4 5 0 ge 124" +"\n"+
"1 3 0 3 6 ge 854" +"\n"+
"0 1 1 0 0 lower . " +"\n"+
". 6 . . . upper . " +"\n"+
"0 1 0 0 1 integer . " +"\n"+
"1 0 0 1 0 binary . " +"\n";
InputString milp_input = new InputString(milp_string);
milp_input.setInputFormat("K1-K5:double, TYPE:varstring(20), RHS:double");
MILP milp=new MILP(milp_input);
SolutionType solution_type= milp.resolve();
if(solution_type==SolutionType.OPTIMAL) {
Solution solution=milp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Variable :"+var.getName() + " value:"+var.getValue());
}
SscLogger.log("o.f. value:"+solution.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 2.5
Consider the following MILP problem given by:
We want to solve this problem of integer linear programming, which also has binary variables, using the matrix notation. In this notation, to represent the binary variables, just add to the matrix of the coefficients a line [line 15]. With the value 1 is declared binary variable, with 0 it is considered non-binary. The ConsType.BIN value [line 20] should also be added to state that the last line of the matrix A is related to the definition of binary variables.
max X1 + 3.0X2
X1 + X2 ≥ 1
X1 + 1.4X2 ≤ 6
-5X1 + 3.0X2 ≤ 5
with X1, X2 ≥ 0
X1 ∈ ℤ
X2 ∈ {0,1}
We want to solve this problem of integer linear programming, which also has binary variables, using the matrix notation. In this notation, to represent the binary variables, just add to the matrix of the coefficients a line [line 15]. With the value 1 is declared binary variable, with 0 it is considered non-binary. The ConsType.BIN value [line 20] should also be added to state that the last line of the matrix A is related to the definition of binary variables.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
import java.util.ArrayList;
import static org.ssclab.pl.milp.LP.NaN;
public class Example {
public static void main(String[] args) throws Exception {
double A[][]={
{ 1.0 , 1.0 },
{ 1.0 , 1.4 },
{-5.0 , 3.0 },
{ 1.0 , 0.0 }, //definizione degli integer
{ 0.0 , 1.0 }, //definizione dei binary
} ;
double b[]= { 1.0, 6.0 ,5.0, NaN, NaN};
double c[]= { 1.0, 3.0 };
ConsType[] rel= {ConsType.GE, ConsType.LE, ConsType.LE, ConsType.INT , ConsType.BIN};
LinearObjectiveFunction f = new LinearObjectiveFunction(c, GoalType.MAX);
ArrayList< Constraint > constraints = new ArrayList< Constraint >();
for(int i=0; i < A.length; i++) {
constraints.add(new Constraint(A[i], rel[i], b[i]));
}
MILP lp = new MILP(f,constraints);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMAL) {
Solution solution=lp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Variable :"+var.getName() + " value:"+var.getValue());
}
SscLogger.log("o.f. value:"+solution.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 2.6
Consider the following MILP problem
We want to solve this problem of linear programming, which also presents binary variables, using the sparse notation. To indicate that the Y1 variable is binary just add in the ROW_ column the marker that defines. This marker (which we call "var_bin", but may have any other name) must have an associated BINARY type TYPE [line 24].
Once the marker of binary variables, just declare [line 32] that the Y1 variable is var_bin (or BINARY) placing in the column of the value COEF 1.
max Y1 + 3.0Y2
Y1 + Y2 ≥ 1
Y1 + 1.4Y2 ≤ 6
-5Y1 + 3.0Y2 ≤ 5
with Y1 ∈ {0,1}
Y2 ∈ ℤ
-∞ ≤ Y2 ≤ +∞
We want to solve this problem of linear programming, which also presents binary variables, using the sparse notation. To indicate that the Y1 variable is binary just add in the ROW_ column the marker that defines. This marker (which we call "var_bin", but may have any other name) must have an associated BINARY type TYPE [line 24].
Once the marker of binary variables, just declare [line 32] that the Y1 variable is var_bin (or BINARY) placing in the column of the value COEF 1.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.FormatTypeInput.FormatType;
import org.ssclab.pl.milp.MILP;
import org.ssclab.pl.milp.Solution;
import org.ssclab.pl.milp.SolutionType;
import org.ssclab.pl.milp.Variable;
import org.ssclab.ref.InputString;
public class Example {
public static void main(String[] args) throws Exception {
String lp_sparse =
// TYPE COL_ ROW_ COEF
" MAX . profit . \n" +
" GE . row1 . \n" +
" LE . row2 . \n" +
" LE . row3 . \n" +
" UPPER . lim_sup . \n" +
" LOWER . lim_inf . \n" +
" INTEGER . var_int . \n" +
" BINARY . var_bin . \n" +
" . Y1 profit 1 \n" +
" . Y1 row1 1 \n" +
" . Y1 row2 1 \n" +
" . Y1 row3 -5 \n" +
" . Y1 var_bin 1 \n" +
" . Y2 profit 3 \n" +
" . Y2 row1 1 \n" +
" . Y2 row2 1.4 \n" +
" . Y2 row3 3 \n" +
" . Y2 lim_sup . \n" +
" . Y2 lim_inf . \n" +
" . Y2 var_int 1 \n" +
" . RHS row1 1 \n" +
" . RHS row2 6 \n" +
" . RHS row3 5 \n" ;
InputString lp_input = new InputString(lp_sparse);
lp_input.setInputFormat("TYPE:varstring(7), COL_:varstring(3) , ROW_:varstring(7), COEF:double");
MILP milp = new MILP(lp_input,FormatType.SPARSE);
SolutionType solution_type=milp.resolve();
if(solution_type==SolutionType.OPTIMAL) {
Solution solution=milp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Variable :"+var.getName() + " value:"+var.getValue());
}
SscLogger.log("o.f. value:"+solution.getOptimumValue());
}
}
}
Example 2.7
Consider the following MILP problem:
We want to solve this mixed integer linear programming problem using a text format. In this format, to add the integer constraint on variables X2 and X3, simply add a line [line 15]. In case binary or semi-continuous variables need to be defined, the syntax is similar to that of integer declaration. Instead of "int", the keywords "bin" or "sec" are used, followed by a comma-separated list of variables. If all variables need to be integer (or binary or semi-continuous), the keyword "ALL" follows the variable type needed ("INT ALL"). Attention! If an "int" instruction has already been defined, other "int" or "bin" or "sec" instructions must each be placed on separate lines.
min 3X1 + X2 + 4X3 + 7X4 + 8X5 5X1 + 2X2 + 3X4 ≥ 9 3X1 + X2 + X3 + 5X5 ≥ 12.5 6X1 + 3X2 + 4X3 + 5X4 ≤ 124 X1 + 3X2 + 3X4 + 6X5 ≤ 854 with X1, X2, X3, X4, X5 ≥ 0 X2, X3 ∈ ℤ
We want to solve this mixed integer linear programming problem using a text format. In this format, to add the integer constraint on variables X2 and X3, simply add a line [line 15]. In case binary or semi-continuous variables need to be defined, the syntax is similar to that of integer declaration. Instead of "int", the keywords "bin" or "sec" are used, followed by a comma-separated list of variables. If all variables need to be integer (or binary or semi-continuous), the keyword "ALL" follows the variable type needed ("INT ALL"). Attention! If an "int" instruction has already been defined, other "int" or "bin" or "sec" instructions must each be placed on separate lines.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
public class Example {
public static void main(String[] args) throws Exception {
String pl_problem =
"min: 3x1 +X2 +4x3 +7x4 +8X5 \n"+
" 5x1 +2x2 +3X4 >= 9 \n"+
" 3x1 + X2 +X3 +5X5 >= 12.5 \n"+
" 6X1+3.0x2 +4X3 +5X4 <= 124 \n"+
" X1 + 3x2 +3X4 +6X5 <= 854 \n"+
" int x2, X3 ";
MILP milp = new MILP(pl_problem);
SolutionType solution_type=milp.resolve();
if(solution_type==SolutionType.OPTIMAL) {
Solution soluzione=milp.getSolution();
for(Variable var:soluzione.getVariables()) {
SscLogger.log("Variable name :"+var.getName() + " value :"+var.getValue());
}
SscLogger.log("o.f. value:"+soluzione.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 2.8
This example compares the final optimal solution integer with that obtained from its relaxation (the values of relaxed problem are shown in square brackets [46-49 lines])
import org.ssclab.context.exception.InvalidSessionException;
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
import java.util.ArrayList;
import static org.ssclab.pl.milp.LP.NaN;
public class Example {
public static void main(String arg[]) throws InvalidSessionException, Exception {
double[] c = { 2, 2, 2, 2, 2 ,2, 2, 2, 2, 2,2 ,2 ,2 };
double[] b = {1000, 1234, 1000, 1000, 1000, 1000, 1000, 1000, 1000};
double[][] A ={ { 2., 9. ,7. ,5. ,9. ,6. ,3., 7., 8. ,7. ,5. ,3. ,1. },
{ 4. ,1. ,2. ,3. ,6. ,4. ,5. ,2. ,8. ,5. ,3. ,4., 7. },
{ 3. ,4. ,2. ,5. ,7. ,6. ,3. ,5. ,7. ,4. ,6. ,8. ,6. },
{ 4. ,6. ,9. ,8. ,7. ,6. ,5. ,4. ,3. ,2. ,3. ,5. ,6. },
{ 4. ,4. ,7. ,5. ,3. ,8. ,5. ,6. ,3. ,5. ,6. ,4. ,6. },
{ 2. ,6. ,4. ,5. ,7. ,5. ,6. ,4. ,6. ,7. ,4. ,4. ,6. },
{ 4. ,6. ,9. ,8. ,3. ,6. ,5. ,5. ,3. ,2. ,9. ,5. ,6. },
{ 4. ,5. ,7. ,8. ,3. ,8. ,3. ,6. ,3. ,5. ,6. ,1. ,6. },
{ 2., 2., 4., 3., 7. ,5. ,9. ,4. ,6. ,7. ,8. ,4., 6. }};
double[] upper ={ 190.5, NaN, NaN, NaN, NaN ,NaN ,NaN ,NaN ,35.0 ,NaN ,NaN ,NaN, NaN };
double[] integer ={ 1.0, 1.0, 1.0, 1.0, 1.0 ,1.0 ,1.0 ,1.0 ,1.0 ,1.0 ,1.0 ,1.0, 1.0 };
LinearObjectiveFunction f = new LinearObjectiveFunction(c, GoalType.MAX);
ArrayList< Constraint > constraints = new ArrayList< Constraint >();
for(int i=0; i< A.length; i++) {
constraints.add(new Constraint(A[i], ConsType.LE, b[i]));
}
constraints.add(new Constraint(upper, ConsType.UPPER, NaN));
constraints.add(new Constraint(integer, ConsType.INT , NaN));
MILP milp = new MILP(f,constraints);
SolutionType solution=milp.resolve();
if(solution==SolutionType.OPTIMAL) {
Solution sol=milp.getSolution();
Solution sol_relax=milp.getRelaxedSolution();
Variable[] var_int=sol.getVariables();
Variable[] var_relax=sol_relax.getVariables();
for(int _i=0; _i< var_int.length;_i++) {
SscLogger.log("Variable name :"+var_int[_i].getName() + " value:"+var_int[_i].getValue()+
" ["+var_relax[_i].getValue()+"]");
}
SscLogger.log("o.f. value:"+sol.getOptimumValue() +" ["+sol_relax.getOptimumValue()+"]");
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 2.9
Consider the following MILP problem:
This problem is similar to problem 2.7. In the code for its resolution, lines have been added to retrieve the value that the left-hand side (LHS) of each constraint (the part to the left of the relation) takes by evaluating the unknown variables with the optimal solution. The LHS value is then compared with the corresponding RHS value [lines 24-27]. It is specified that the quantities LHS and RHS referred to in this specific case, i.e., to retrieve their value (given a linear programming problem AX <=> b), are represented by AX (LHS part) and b (RHS). Therefore, if we include variables on the right side of the inequality/equality sign in the problem definition, these will not be considered as part of the RHS but grouped in the form: AX (LHS part) and b (RHS). Constraints can be named by prefixing a name to the constraint followed by a colon (example 1.11).
In this example, all variables have been declared as integers. To declare them all as integers, you can use the notation "int all," or you can use the notation that uses the wildcard character *, which indicates that all variables beginning with a certain prefix are of a certain type (as in the example). Using this notation, you can, for example, use a notation like this: "int XI* \n bin XB*". This way, we declare that variables beginning with "XI" are integers, those beginning with "XB" are binary, and the remaining ones are real.
min 3X1 + X2 + 4X3 + 7X4 + 8X5 5X1 + 2X2 + 3X4 ≥ 9 3X1 + X2 + X3 + 5X5 ≥ 12.5 6X1 + 3X2 + 4X3 + 5X4 ≤ 124 X1 + 3X2 + 3X4 + 6X5 ≤ 854 with X1, X2, X3, X4, X5 ≥ 0 X1, X2, X3, X4, X5 ∈ ℤ
This problem is similar to problem 2.7. In the code for its resolution, lines have been added to retrieve the value that the left-hand side (LHS) of each constraint (the part to the left of the relation) takes by evaluating the unknown variables with the optimal solution. The LHS value is then compared with the corresponding RHS value [lines 24-27]. It is specified that the quantities LHS and RHS referred to in this specific case, i.e., to retrieve their value (given a linear programming problem AX <=> b), are represented by AX (LHS part) and b (RHS). Therefore, if we include variables on the right side of the inequality/equality sign in the problem definition, these will not be considered as part of the RHS but grouped in the form: AX (LHS part) and b (RHS). Constraints can be named by prefixing a name to the constraint followed by a colon (example 1.11).
In this example, all variables have been declared as integers. To declare them all as integers, you can use the notation "int all," or you can use the notation that uses the wildcard character *, which indicates that all variables beginning with a certain prefix are of a certain type (as in the example). Using this notation, you can, for example, use a notation like this: "int XI* \n bin XB*". This way, we declare that variables beginning with "XI" are integers, those beginning with "XB" are binary, and the remaining ones are real.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
public class Example {
public static void main(String[] args) throws Exception {
String pl_problem =
"min: 3x1 +X2 +4x3 +7x4 +8X5 \n"+
"constraint1: 5x1 +2x2 +3X4 >= 9\n"+
"constraint2: 3x1 + X2 +X3 +5X5 >= 12.5\n"+
"row3: 6X1+3.0x2 +4X3 +5X4 <= 124\n"+
"X1 + 3x2 +3X4 +6X5 <= 854\n"+
"int x* ";
MILP milp = new MILP(pl_problem);
SolutionType solution_type=milp.resolve();
if(solution_type==SolutionType.OPTIMAL) {
Solution soluzione=milp.getSolution();
for(Variable var:soluzione.getVariables()) {
SscLogger.log("Variable name :"+var.getName() + " value :"+var.getValue());
}
for(SolutionConstraint sol_constraint: soluzione.getSolutionConstraint()) {
SscLogger.log("Contraint: "+sol_constraint.getName()+" : value="+sol_constraint.getValue() +
"[ "+sol_constraint.getRel()+" "+sol_constraint.getRhs()+" ]" );
}
SscLogger.log("o.f. value:"+soluzione.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 2.10
Consider the following linear programming problem that also has a semi-continuous variable:
This problem is identical to the problem 2.4 with the addition of the condition that the variable K2 is semicontinuous, it is not tightly constrained to be between the upper and lower values, but can also assume the value 0.
min 3K1 + K2 + 4K3 + 7K4 + 8K5
5K1 + 2K2 + 3K4 ≤ 9
3K1 + K2 + K3 + 5K5 ≥ 12
6K1 + 3K2 + 4K3 + 5K4 ≥ 124
1K1 + 3K2 + 3K4 + 6K5 ≥ 854
with K2, K5 ∈ ℤ
K1, K4 ∈ {0,1}
1 ≤ K2 ≤ +6 or K2 =0
1 ≤ K3 ≤ +∞
con K1, K4, K5 ≥ 0
This problem is identical to the problem 2.4 with the addition of the condition that the variable K2 is semicontinuous, it is not tightly constrained to be between the upper and lower values, but can also assume the value 0.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
import org.ssclab.ref.*;
public class Example {
public static void main(String[] args) throws Exception {
String milp_string=
"3 1 4 7 8 min . " +"\n"+
"5 2 0 3 0 le 9 " +"\n"+
"3 1 1 0 5 ge 12" +"\n"+
"6 3 4 5 0 ge 124" +"\n"+
"1 3 0 3 6 ge 854" +"\n"+
"0 1 1 0 0 lower . " +"\n"+
". 6 . . . upper . " +"\n"+
"0 1 0 0 1 integer . " +"\n"+
"1 0 0 1 0 binary . " +"\n"+
"0 1 0 0 0 semicont . " +"\n";
Input input = new InputString(milp_string).setInputFormat("K1-K5:double, TYPE:varstring(20), RHS:double");
MILP milp=new MILP(input);
SolutionType solution_type= milp.resolve();
if(solution_type==SolutionType.OPTIMAL) {
Solution solution=milp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Variable :"+var.getName() + " value:"+var.getValue());
}
SscLogger.log("Best value:"+solution.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 2.11
Consider the following linear programming problem that also has a semi-continuous variable:
We want to solve this problem of integer linear programming, which also features semi-continuous variables, using the matrix notation.
max -X1 + 3.0X2
X1 + X2 ≥ 1
X1 + 1.4X2 ≤ 6
-5X1 + 3.0X2 ≤ 5
with X1, X2 ≥ 0
X1 ∈ ℤ
X2 ∈ {0,1}
1 ≤ X1 ≤ 3 or X1 =0
We want to solve this problem of integer linear programming, which also features semi-continuous variables, using the matrix notation.
import static org.ssclab.pl.milp.LP.NaN;
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
import static org.ssclab.pl.milp.ConsType.*;
import java.util.ArrayList;
public class Example {
public static void main(String[] args) throws Exception {
double A[][]={
{ 1.0 , 1.0 },
{ 1.0 , 1.4 },
{-5.0 , 3.0 },
{ 1.0 , 0.0 }, //def. integer
{ 0.0 , 1.0 }, //def. binary
{ 1.0 , 0.0 }, //def. semicontinuous
{ 3.0 , NaN}, //def. upper
{ 1.0 , 0.0 }, //def. lower
} ;
double b[]= { 1.0, 6.0 ,5.0, NaN, NaN, NaN, NaN, NaN};
double c[]= { -1.0, 3.0 };
ConsType[] rel= {GE, LE, LE, INT, BIN, SEMICONT, UPPER, LOWER};
LinearObjectiveFunction f = new LinearObjectiveFunction(c, GoalType.MAX);
ArrayList< Constraint > constraints = new ArrayList< Constraint >();
for(int i=0; i < A.length; i++) {
constraints.add(new Constraint(A[i], rel[i], b[i]));
}
MILP lp = new MILP(f,constraints);
SolutionType solution_type=lp.resolve();
if(solution_type==SolutionType.OPTIMAL) {
Solution solution=lp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Variable :"+var.getName() + " value:"+var.getValue());
}
SscLogger.log("best value:"+solution.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 2.12
Consider the following linear programming problem that also has a semi-continuous variable:
We want to solve this problem of integer linear programming, which also features semi-continuous variables, using the sparse notation.
max Y1 - 3.0Y2
Y1 + Y2 ≥ 1
Y1 + 1.4Y2 ≤ 6
-5Y1 + 3.0Y2 ≤ 5
with Y1 ∈ {0,1}
Y2 ∈ ℤ
1 ≤ Y2 ≤ +∞ or Y2 = 0
We want to solve this problem of integer linear programming, which also features semi-continuous variables, using the sparse notation.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.FormatTypeInput.FormatType;
import org.ssclab.pl.milp.*;
import org.ssclab.ref.*;
public class Example {
public static void main(String[] args) throws Exception {
String sparse =
// TYPE COL_ ROW_ COEF
" MAX . profit . \n" +
" GE . row1 . \n" +
" LE . row2 . \n" +
" LE . row3 . \n" +
" UPPER . lim_sup . \n" +
" LOWER . lim_inf . \n" +
" INTEGER . var_int . \n" +
" BINARY . var_bin . \n" +
" SEMICONT . var_sc . \n" +
" . Y1 profit 1 \n" +
" . Y1 row1 1 \n" +
" . Y1 row2 1 \n" +
" . Y1 row3 -5 \n" +
" . Y1 var_bin 1 \n" +
" . Y2 profit -3 \n" +
" . Y2 row1 1 \n" +
" . Y2 row2 1.4 \n" +
" . Y2 row3 3 \n" +
" . Y2 lim_sup . \n" +
" . Y2 lim_inf 1 \n" +
" . Y2 var_int 1 \n" +
" . Y2 var_sc 1 \n" +
" . RHS row1 1 \n" +
" . RHS row2 6 \n" +
" . RHS row3 5 \n" ;
Input input = new InputString(sparse).setInputFormat("TYPE:varstring(8), COL_:varstring(3) , ROW_:varstring(7), COEF:double");
MILP milp = new MILP(input,FormatType.SPARSE);
SolutionType solution_type=milp.resolve();
if(solution_type==SolutionType.OPTIMAL) {
Solution solution=milp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Name variable :"+var.getName() + " value :"+var.getValue());
}
SscLogger.log("o.f. value:"+solution.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 2.13
Consider the whole linear programming problem reported in the section below. We want to solve this problem by using a parallel B & B implementation. To do this, simply add the instruction to line [35], which declares the number of threads (in this case 4) to be used to execute a parallel B & B.
import org.ssclab.context.exception.InvalidSessionException;
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
import org.ssclab.pl.milp.util.MILPThreadsNumber;
import static org.ssclab.pl.milp.LP.NaN;
import java.util.ArrayList;
public class Example {
public static void main(String arg[]) throws InvalidSessionException, Exception {
double[] c = { 2, 2, 2, 2, 2 , 2, 2, 2, 2, 2, 2 ,2 , 2 };
double[] b = {1000, 1234, 1000, 1000, 1000, 1000, 1000, 1000, 1000};
double[][] A ={ { 2., 9. ,7. ,5. ,9. ,6. ,3., 7., 8. ,7. ,5. ,3. ,1. },
{ 4. ,1. ,2. ,3. ,6. ,4. ,5. ,2. ,8. ,5. ,3. ,4., 7. },
{ 3. ,4. ,2. ,5. ,7. ,6. ,3. ,5. ,7. ,4. ,6. ,8. ,6. },
{ 4. ,6. ,9. ,8. ,7. ,6. ,5. ,4. ,3. ,2. ,3. ,5. ,6. },
{ 4. ,4. ,7. ,5. ,3. ,8. ,5. ,6. ,3. ,5. ,6. ,4. ,6. },
{ 2. ,6. ,4. ,5. ,7. ,5. ,6. ,4. ,6. ,7. ,4. ,4. ,6. },
{ 4. ,6. ,9. ,8. ,3. ,6. ,5. ,5. ,3. ,2. ,9. ,5. ,6. },
{ 4. ,5. ,7. ,8. ,3. ,8. ,3. ,6. ,3. ,5. ,6. ,1. ,6. },
{ 2., 2., 4., 3., 7. ,5. ,9. ,4. ,6. ,7. ,8. ,4., 6. }};
double[] integer ={ 1.0, 1.0, 1.0, 1.0, 1.0 ,1.0 ,1.0 ,1.0 ,1.0 ,1.0 ,1.0 ,1.0, 1.0 };
LinearObjectiveFunction f = new LinearObjectiveFunction(c, GoalType.MAX);
ArrayList< Constraint > constraints = new ArrayList< Constraint >();
for(int i=0; i< A.length; i++) {
constraints.add(new Constraint(A[i], ConsType.LE, b[i]));
}
constraints.add(new Constraint(integer, ConsType.INT , NaN));
MILP milp = new MILP(f,constraints).setThreadsNumber(MILPThreadsNumber.N_4);
SolutionType solutionType=milp.resolve();
if(solutionType==SolutionType.OPTIMAL) {
Solution solution=milp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Variable name :"+var.getName() + " value:"+var.getValue());
}
SscLogger.log("Best value:"+solution.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solutionType);
}
}
Esempio 2.14
If the requirement is to obtain a feasible solution that is not necessarily optimal, just invoke the setJustTakeFeasibleSolution () method, passing it the "true" value (line 19). This option allows the B&B to be executed in order to obtain a feasible solution. In this case the value returned by resolve() (if a feasible solution exists) will be SolutionType.FEASIBLE. In our example the integer feasible solution obtained (X1=2,X2=2) has value on o.f. -6, while the optimal solution (X1=3,X2=1) has a value of -7.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
import org.ssclab.ref.InputString;
public class Example {
public static void main(String[] args) throws Exception {
String milp_string=
"-2 -1 min ." +"\n"+
"-1 -1 ge -5" +"\n"+
" 1 -1 ge 0" +"\n"+
"-6 -2 ge -21" +"\n"+
" 4 3 upper ." +"\n"+
" 1 1 integer ." +"\n" ;
InputString input = new InputString(milp_string).setInputFormat("X1-X2:double, TYPE:varstring(20), RHS:double");
MILP milp=new MILP(input).setJustTakeFeasibleSolution(true);
SolutionType solution_type= milp.resolve();
if(solution_type==SolutionType.FEASIBLE) {
Solution solution=milp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Variable name :"+var.getName() + " Value:"+var.getValue());
}
SscLogger.log("O.F. Value:"+solution.getValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 2.15
Consider the following linear programming problem :
We want to solve this problem using the JSON format. To specify which variables must be integers, you need to add the "variables" section, where the type of variables is indicated. Depending on whether they are integer, binary, semi-continuous, or integer semi-continuous, the respective values "integer", "binary", "semicont", and "integer-semicont" are used.
It's important to remember that in the JSON format, both the keys (such as "objective", "coefficients", "constraints", etc.) and the values (such as "max", "min", "eq", etc.) must be written in lowercase. However, the names given to variables are case-insensitive, meaning that "X3" and "x3" represent the same variable. Lastly, the names of the constraints can be written in uppercase, lowercase, or a mix, but keep in mind that they are case-sensitive.
min 3Y + 2X2 + 4X3 + 7X4 + 8X5 5Y + 2X2 - 3X4 ≥ 9 3Y + X2 + X3 + 5X5 = 12 6Y + 3X2 + 4X3 - 5X4 ≤ 124 with X3, X4, X5 ≥ 0 1 ≤ Y ≤ +4 -∞ ≤ X2 ≤ +5 Y ∈ ℤ
We want to solve this problem using the JSON format. To specify which variables must be integers, you need to add the "variables" section, where the type of variables is indicated. Depending on whether they are integer, binary, semi-continuous, or integer semi-continuous, the respective values "integer", "binary", "semicont", and "integer-semicont" are used.
It's important to remember that in the JSON format, both the keys (such as "objective", "coefficients", "constraints", etc.) and the values (such as "max", "min", "eq", etc.) must be written in lowercase. However, the names given to variables are case-insensitive, meaning that "X3" and "x3" represent the same variable. Lastly, the names of the constraints can be written in uppercase, lowercase, or a mix, but keep in mind that they are case-sensitive.
import org.ssclab.log.*;
import org.ssclab.pl.milp.*;
public class Example {
public static void main(String[] args) throws Exception {
String pl_json = "{ "
+ " 'objective': { "
+ " 'type': 'max', "
+ " 'coefficients': { "
+ " 'Y': 3, "
+ " 'X2': 2, "
+ " 'X3': 4, "
+ " 'X4': 7, "
+ " 'X5': 8 "
+ " } "
+ " }, "
+ " 'constraints': [ "
+ " { "
+ " 'coefficients': { "
+ " 'Y': 5, "
+ " 'X2': 2, "
+ " 'X4':-3 "
+ " }, "
+ " 'relation': 'ge', "
+ " 'rhs': 9, "
+ " 'name':'constraint1' "
+ " }, "
+ " { "
+ " 'coefficients': { "
+ " 'Y': 3, "
+ " 'X2': 1, "
+ " 'X3': 1, "
+ " 'X5': 5 "
+ " }, "
+ " 'relation': 'eq', "
+ " 'rhs': 12, "
+ " 'name':'constraint2' "
+ " }, "
+ " { "
+ " 'coefficients': { "
+ " 'Y': 6, "
+ " 'X2': 3, "
+ " 'X3': 4, "
+ " 'X4':-5 "
+ " }, "
+ " 'relation': 'le', "
+ " 'rhs': 124, "
+ " 'name':'constraint3' "
+ " } "
+ " ], "
+ " 'bounds': { "
+ " 'Y': { "
+ " 'lower': 1, "
+ " 'upper': 4 "
+ " }, "
+ " 'X2': { "
+ " 'lower': null, "
+ " 'upper': 5 "
+ " } "
+ " }, "
+ " 'variables': { "
+ " 'Y': 'integer' "
+ " } "
+ "}";
pl_json=pl_json.replace('\'', '"');
MILP milp = new MILP(new JsonProblem(pl_json));
SolutionType solution_type=milp.resolve();
if(solution_type==SolutionType.OPTIMAL) {
Solution solution=milp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Variable :"+var.getName() + " value:"+var.getValue());
}
SscLogger.log("o.f. value:"+solution.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 2.16
Consider the following linear programming problem :
min 3X1 + X2 + 4X3 + 7X4 + 8X5 5X1 + 2X2 + 3X4 ≥ 9 3X1 + X2 + X3 + 5X5 ≥ 12.5 6X1 + 3X2 + 4X3 + 5X4 ≤ 124 X1 + 3X2 + 3X4 + 6X5 ≤ 854 con X1, X2, X3, X4, X5 ≥ 0 1 ≤ X2 ≤ +3 X1, X3 ∈ ℤWe aim to solve this mixed-integer linear programming (MILP) problem and store the solution in an external JSON file. In this case, we include, using the "INCLUDE_XXX" declarations, all the additional available information to be saved in the solution in JSON format. We can observe how the resolve() method is passed the value null to distinguish it from the standard one, which returns the type of solution found, unlike this one, which allows chaining method calls on the MILP object.
import static org.ssclab.pl.milp.SolutionDetail.*;
import org.ssclab.pl.milp.*;
public class Example {
public static void main(String[] args) throws Exception {
String pl_problem =
"min: 3x1 +X2 +4x3 +7x4 +8X5 \n" +
" 5x1 +2x2 +3X4 >= 9 \n"+
" 3x1 + X2 +X3 +5X5 >= 12.5 \n"+
" 6X1+3.0x2 +4X3 +5X4 <= 124 \n"+
" X1 + 3x2 +3X4 +6X5 <= 854 \n"+
" 1<=X2<=3 \n"+
" int x1, X3 ";
new MILP(pl_problem)
.setTitle("Example 2.16")
.resolve(null)
.getSolutionAsJson(INCLUDE_BOUNDS,INCLUDE_META,INCLUDE_CONSTRAINT,INCLUDE_TYPEVAR,INCLUDE_RELAXED)
.saveToFile("solution.json");
}
}
Example 2.17
Consider the following linear programming problem :
We want to solve this linear programming problem which presents a set of SOS1 variables, meaning that among the variables belonging to this set, only one can be greater than zero.
min 3X1 + X2 + 4X3 + 7X4 + 8X5 5X1 + 2X2 + 3X4 ≥ 9 3X1 + X2 + X3 + 5X5 ≥ 12.5 6X1 + 3X2 + 4X3 + 5X4 ≤ 124 X1 + 3X2 + 3X4 + 6X5 ≤ 854 X1, X2, X3, X4, X5 ≥ 0 X1, X3, X4, X5 ∈ SOS1 1 ≤ X2 ≤ +3
We want to solve this linear programming problem which presents a set of SOS1 variables, meaning that among the variables belonging to this set, only one can be greater than zero.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
public class Esempio {
public static void main(String[] args) throws Exception {
String pl_problem =
"min: 3x1 +X2 +4x3 +7x4 +8X5 \n" +
" 5x1 +2x2 +3X4 >= 9 \n"+
" 3x1 + X2 +X3 +5X5 >= 12.5 \n"+
" 6X1+3.0x2 +4X3 +5X4 <= 124 \n"+
" X1 + 3x2 +3X4 +6X5 <= 854 \n"+
" 1<=X2<=3 \n"+
" sos1 x1,X3,x4,x5";
MILP milp = new MILP(pl_problem);
SolutionType solution_type=milp.resolve();
if(solution_type==SolutionType.OPTIMAL) {
Solution solution=milp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Variable :"+var.getName() + " value:"+var.getValue());
}
SscLogger.log("o.f. value:"+solution.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 2.18
Consider the following linear programming problem :
We aim to solve a linear programming problem with a set of integer SOS2 variables. This means that, within this set, only two variables can be greater than zero, and these must be consecutive. In other words, either (X2, X3) or (X3, X5) must be greater than zero, but no other combination.
min 3X1 + X2 - 4X3 + 7X4 + 8X5
5X1 + 2X2 + 3X4 ≥ 9
3X1 + X2 + X3 + 5X5 ≥ 12.5
6X1 +3.1X2 + 4X3 + 5X4 ≤ 24
X1 ≥ -1
-1 ≤ X2 ≤ +6
X3 ≤ -2
X5 ≥ 0
X1,X2,X3,X4,X5 ∈ ℤ
X2,X3,X5 ∈ SOS2
We aim to solve a linear programming problem with a set of integer SOS2 variables. This means that, within this set, only two variables can be greater than zero, and these must be consecutive. In other words, either (X2, X3) or (X3, X5) must be greater than zero, but no other combination.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
public class Esempio {
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" +
" int x1,X4 \n" +
" sos2:INT x2, X3,x5 ";
MILP milp = new MILP(lp_problem);
SolutionType solution_type = milp.resolve();
if(solution_type==SolutionType.OPTIMAL) {
Solution solution=milp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Variable :"+var.getName() + " value:"+var.getValue());
}
SscLogger.log("o.f. value:"+solution.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 2.19
Consider the following linear programming problem :
We aim to solve a linear programming problem characterized by a set of binary F-SOS1 and SOS2 variables. The former must be binary and at least one must be equal to 1 (F = forced). For the SOS2 variables, at most two consecutive ones can be greater than zero, specifically either (X4, X2) or (X2, X3), or one or none.
min 3X1 + X2 + 4X3 + 7X4 + 8X5
5X1 + 2X2 + 3X4 ≥ 9
3X1 + X2 + X3 + 5X5 ≥ 12.5
6X1 +3.1X2 + 4X3 + 5X4 ≥ 24
1 ≤ X2 ≤ +6
X1, X5 ∈ {0,1}
X1, X5 ∈ F-SOS1, which is equivalent X1 + X5 =1
X4, X2, X3 ∈ SOS2
We aim to solve a linear programming problem characterized by a set of binary F-SOS1 and SOS2 variables. The former must be binary and at least one must be equal to 1 (F = forced). For the SOS2 variables, at most two consecutive ones can be greater than zero, specifically either (X4, X2) or (X2, X3), or one or none.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
public class Esempio {
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 lp_problem = """
min: 3x1 +X2 +4x3 +7x4 +8X5
5x1 +2x2 +3X4 >= 9
3x1 + X2 +X3 +5X5 >= 12.5
6X1+3.1x2 +4X3 +5X4 >= 24
1 <= x2 <= 6
sos1:bin:force x1, X5
sos2 x4,x2,X3 """;
MILP milp = new MILP(lp_problem);
SolutionType solution_type = milp.resolve();
if(solution_type==SolutionType.OPTIMAL) {
Solution solution=milp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Variable :"+var.getName() + " value:"+var.getValue());
}
SscLogger.log("o.f. value:"+solution.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 3.1
Consider the following MILP problem:
We want to solve this problem using Text format.
min 3X1 + X2 - 4X3 + 7X4 + 8X5
5X1 + 2X2 + 3X4 ≥ 9
3X1 + X2 + X3 + 5X5 = 12.5
6X1 +3.1X2 + 4X3 + 5X4 ≤ 24
X1 ≥ -1
-1 ≤ X2 ≤ +6
X3 ≤ -2
-∞ ≤ X4 ≤ +∞
X5 ≥ 0
X2, X3 ∈ ℤ
We want to solve this problem using Text format.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
public class Example {
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 ";
MILP milp = new MILP(lp_problem);
SolutionType solution_type = milp.resolve();
if(solution_type==SolutionType.OPTIMAL) {
Solution solution=milp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Variable :"+var.getName() + " value:"+var.getValue());
}
SscLogger.log("o.f. value:"+solution.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 3.2
Consider the following MILP problem:
We want to solve this problem using Coefficients format.
min 3X1 + X2 - 4X3 + 7X4 + 8X5
5X1 + 2X2 + 3X4 ≥ 9
3X1 + X2 + X3 + 5X5 = 12.5
6X1 +3.1X2 + 4X3 + 5X4 ≤ 24
X1 ≥ -1
-1 ≤ X2 ≤ +6
X3 ≤ -2
-∞ ≤ X4 ≤ +∞
X5 ≥ 0
X2, X3 ∈ ℤ
We want to solve this problem using Coefficients format.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
import org.ssclab.ref.InputString;
public class Example {
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-X5:double, TYPE:varstring(8), RHS:double");
MILP milp = new MILP(milp_input);
SolutionType solution_type = milp.resolve();
if(solution_type==SolutionType.OPTIMAL) {
Solution solution=milp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Variable :"+var.getName() + " value:"+var.getValue());
}
SscLogger.log("o.f. value:"+solution.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 3.3
Consider the following MILP problem:
We want to solve this problem using Matrix format.
min 3X1 + X2 - 4X3 + 7X4 + 8X5
5X1 + 2X2 + 3X4 ≥ 9
3X1 + X2 + X3 + 5X5 = 12.5
6X1 +3.1X2 + 4X3 + 5X4 ≤ 24
X1 ≥ -1
-1 ≤ X2 ≤ +6
X3 ≤ -2
-∞ ≤ X4 ≤ +∞
X5 ≥ 0
X2, X3 ∈ ℤ
We want to solve this problem using Matrix format.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
import static org.ssclab.pl.milp.ConsType.*;
import static org.ssclab.pl.milp.LP.NaN;
public class Example {
public static void main(String[] args) throws Exception {
double c[] =
{ 3.0, 1.0, -4.0, 7.0, 8.0 }; //array 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 REL
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]));
MILP milp = new MILP(fo,constraints);
SolutionType solution_type = milp.resolve();
if(solution_type==SolutionType.OPTIMAL) {
Solution solution=milp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Variable :"+var.getName() + " value:"+var.getValue());
}
SscLogger.log("o.f. value:"+solution.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 3.4
Consider the following MILP problem:
We want to solve this problem using Sparse format.
min 3X1 + X2 - 4X3 + 7X4 + 8X5
5X1 + 2X2 + 3X4 ≥ 9
3X1 + X2 + X3 + 5X5 = 12.5
6X1 +3.1X2 + 4X3 + 5X4 ≤ 24
X1 ≥ -1
-1 ≤ X2 ≤ +6
X3 ≤ -2
-∞ ≤ X4 ≤ +∞
X5 ≥ 0
X2, X3 ∈ ℤ
We want to solve this problem using Sparse format.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
import org.ssclab.pl.milp.FormatTypeInput.FormatType;
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");
MILP milp = new MILP(lp_input,FormatType.SPARSE);
SolutionType solution_type=milp.resolve();
if(solution_type==SolutionType.OPTIMAL) {
Solution solution=milp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Variable :"+var.getName() + " value:"+var.getValue());
}
SscLogger.log("o.f. value:"+solution.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
Example 3.5
Consider the following MILP problem:
We want to solve this problem using JSON format.
min 3X1 + X2 - 4X3 + 7X4 + 8X5
5X1 + 2X2 + 3X4 ≥ 9
3X1 + X2 + X3 + 5X5 = 12.5
6X1 +3.1X2 + 4X3 + 5X4 ≤ 24
X1 ≥ -1
-1 ≤ X2 ≤ +6
X3 ≤ -2
-∞ ≤ X4 ≤ +∞
X5 ≥ 0
X2, X3 ∈ ℤ
We want to solve this problem using JSON format.
import org.ssclab.log.SscLogger;
import org.ssclab.pl.milp.*;
public class Example {
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"
}
}""";
MILP milp = new MILP(new JsonProblem(stringJson));
SolutionType solution_type=milp.resolve();
if(solution_type==SolutionType.OPTIMAL) {
Solution solution=milp.getSolution();
for(Variable var:solution.getVariables()) {
SscLogger.log("Variable :"+var.getName() + " value:"+var.getValue());
}
SscLogger.log("o.f. value:"+solution.getOptimumValue());
}
else SscLogger.log("no optimal solution:"+solution_type);
}
}
In SSC, an LP problem can be solved using different formats. We want to solve this problem by using a firt representation: text format. In this format the objective function and the constraints can be expressed by means of equations / inequalities represented inside strings [lines 12-16]. The variables can have any name (they must however start with an alphabetic character followed by alphanumeric characters) and are not case-sensitive (ie x3 and X3 represent the same variable). In this format, however, each constraint and the objective function must be expressed on different lines.
One advantage of this format is that if a variable is not present in a constraint this may be omitted, unlike the matrix format or coefficients format where it needs to be represented with a coefficient equal to zero.
Once the problem is represented, the simplex algorithm is executed by creating an object of the LP class and invoking the resolve() method [lines 18-19]. After executing the simplex algorithm, the resolve() method returns the type of solution found; if the solution is optimal, it is possible to obtain the values of the variables and the optimal value of the objective function. It is worth noting that in SSC, by default, the variables of an LP problem are considered non-negative (≥ 0) unless otherwise specified.