A java simplex solver

SSC (Software for Simplex Calculation) is a java library for solving linear programming problems. SSC uses the Simplex algorithm for solving this class of optimization problems normally indicated with the initials LP (Linear Programming).

In SSC you can solve problems with free variables, integer, binary and semi-continuous. This subclass of problems are usually named with the initials MILP (Mixed Integer Linear Programming). For MILP problems, which have all or part of integer or binary or semi-continuous variables, SSC uses the algorithm of Branch and Bound (B&B) for their resolution.

Starting from version 2.1.0 it is possible to perform an implementation of the parallel simplex. This option (see example 1.14) makes it possible to exploit multiple threads for the simulation of the simplex and is of significant advantage in the case of architectures with at least 4 or more physical cores.

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} \)

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 highly efficient, allowing simple LP problems (non-integer) solvable with SSC to have no limits on the number of variables and constraints; the limits are determined by the availability of JVM memory. For example, if the JVM is instructed to allocate a maximum of 4 gigabytes of memory (using the declaration -Xmx4g), it is possible to solve problems with tens of thousands of variables and thousands of constraints.

Conversely, the Branch and Bound method is not efficient, and the one implemented in this library, used to solve integer linear programming problems, is not highly optimized. Additionally, there are methods in the literature that are certainly much more efficient in terms of computational complexity and memory usage. Consequently, the size of solvable MILP problems is necessarily limited.

Technical requirements

The requirement to perform the SSC program is to be able to have a JDK (or SDK) java version 10.x or higher. No other requirement is requested.