Library for linear programming
The problem
The type of problems that the APIs provided by SSC solve is the following:
\( \hspace{3cm} \text{ max/min } \hspace{0.3cm} c^{\mathrm{T}}x \hspace{1cm} \text{it is the objective function (o.f.) } \)
subject to :
\( \hspace{3cm} Ax\, (\le , = , \ge)\, b \)
\( \hspace{3cm} l_{i} \le x_{i} \le u_{i} \hspace{0.5cm} \text{ or }\, x_{i}=0\)
\( \hspace{3cm} x_{i} \in \mathbb{Z} \hspace{1.6cm} \forall i \in \text{I} \)
\( \hspace{3cm} x_{i} \in \{0,1\} \hspace{0.8cm} \forall i \in \text{B} \)
\( \hspace{3cm} x_{i} \in \mathbb{R} \hspace{1.6cm} \forall i \notin (\text{I} \cup \text{B}) \)
where:
\( \hspace{3cm} x\, \in \mathbb{R}^{n} \hspace{5cm} \text{it is the vector of variables}\, x_{i} \)
\( \hspace{3cm} A \in \mathbb{Q}^{m \times n} \hspace{4.4cm} \text{it is the coefficient matrix} \)
\( \hspace{3cm} c\,\, \in \mathbb{Q}^{n} \hspace{5cm} \text{it is the coefficient vector of the objective function} \)
\( \hspace{3cm} b\,\, \in \mathbb{Q}^{m} \hspace{4.9cm} \text{it is the RHS coefficient vector} \)
\( \hspace{3cm} l\,\,\, \in \mathbb{Q}^{n} \hspace{5cm} \text{it is the vector of lower bounds }\, l_{i} \)
\( \hspace{3cm} u\, \in \mathbb{Q}^{n} \hspace{5cm} \text{it is the vector of upper bounds }\, u_{i} \)
\( \hspace{3cm} \text{I}\,\, \subseteq \{1,..,n\} \hspace{3.7cm} \text{it is a subset of indices related to the integer variables} \)
\( \hspace{3cm} \text{B} \subseteq \{1,..,n\}\, : \, (\text{I} \cap \text{B}) = \emptyset \hspace{0.9cm} \text{it is a subset of indices related to the binary variables} \)
\( \hspace{3cm} \text{ max/min } \hspace{0.3cm} c^{\mathrm{T}}x \hspace{1cm} \text{it is the objective function (o.f.) } \)
subject to :
\( \hspace{3cm} Ax\, (\le , = , \ge)\, b \)
\( \hspace{3cm} l_{i} \le x_{i} \le u_{i} \hspace{0.5cm} \text{ or }\, x_{i}=0\)
\( \hspace{3cm} x_{i} \in \mathbb{Z} \hspace{1.6cm} \forall i \in \text{I} \)
\( \hspace{3cm} x_{i} \in \{0,1\} \hspace{0.8cm} \forall i \in \text{B} \)
\( \hspace{3cm} x_{i} \in \mathbb{R} \hspace{1.6cm} \forall i \notin (\text{I} \cup \text{B}) \)
where:
\( \hspace{3cm} x\, \in \mathbb{R}^{n} \hspace{5cm} \text{it is the vector of variables}\, x_{i} \)
\( \hspace{3cm} A \in \mathbb{Q}^{m \times n} \hspace{4.4cm} \text{it is the coefficient matrix} \)
\( \hspace{3cm} c\,\, \in \mathbb{Q}^{n} \hspace{5cm} \text{it is the coefficient vector of the objective function} \)
\( \hspace{3cm} b\,\, \in \mathbb{Q}^{m} \hspace{4.9cm} \text{it is the RHS coefficient vector} \)
\( \hspace{3cm} l\,\,\, \in \mathbb{Q}^{n} \hspace{5cm} \text{it is the vector of lower bounds }\, l_{i} \)
\( \hspace{3cm} u\, \in \mathbb{Q}^{n} \hspace{5cm} \text{it is the vector of upper bounds }\, u_{i} \)
\( \hspace{3cm} \text{I}\,\, \subseteq \{1,..,n\} \hspace{3.7cm} \text{it is a subset of indices related to the integer variables} \)
\( \hspace{3cm} \text{B} \subseteq \{1,..,n\}\, : \, (\text{I} \cap \text{B}) = \emptyset \hspace{0.9cm} \text{it is a subset of indices related to the binary variables} \)
Details
The simplex method can 'be divided into two phases. In phase 1 is identified a basic
feasible solution, while in the phase 2 is identified an optimal solution. The procedure
manages free variables, bounded variables bottom and top and the different ranges
of constraints. If they are not explicitly specified lower limits,
SSC considers the variables to be not negative.
In SSC when a variable is defined as an integer variable or binary, the procedure uses the algorithm of Branch and Bound for optimization. The Branch and Bound resolves a succession of relaxed problems (deprived of integer constraints); to solve these problems is used the Simplex algorithm.
Size of problems and memory request
The simplex method is an efficient algorithm for solving continuous linear programming problems (i.e., those without integer variables),
which allows for handling problems with a large number of variables and constraints. Running the simplex method with SSC,
the limitations are eventually related to the JVM's memory availability. For example, if you allocate a maximum of 4 Gigabytes
of memory to the JVM (using the -Xmx4g declaration), it is possible to solve problems with thousands of variables and constraints.
On the other hand, the Branch and Bound method has a higher computational complexity, as it must solve a succession of simplexes; this makes it much more demanding in terms of calculation time and required resources compared to the single simplex method. Consequently, the size of the MILP (Mixed Integer Linear Programming) problems that can be solved is necessarily limited.
SSC (Software for Simplex Calculation) is an open-source Java library for solving linear programming (LP) problems. Distributed as free and open-source software (FOSS), SSC is available for download on GitHub and Maven. The library comes with examples and documentation, offering easy integration into Java projects, making it ideal for anyone seeking an efficient solution for optimization problems.
The SSC library supports the formulation of linear programming problems in various formats: text, coefficient, matrix, sparse, and even JSON. Problems can be specified directly in code or through an external file, simplifying integration with existing projects and facilitating the management of complex inputs.
SSC uses the Simplex algorithm to solve this class of problems, commonly referred to as LP (Linear Programming). It also supports problems with free, integer, binary, semicontinuous, and semi-continuous integer variables, known as MILP (Mixed Integer Linear Programming). To solve MILP problems, which include integer or binary variables, SSC employs the Branch and Bound (B&B) algorithm.