Library for linear programming
Online LP Solver
The SSC linear programming library is now even more versatile: in addition to comprehensive documentation and practical examples, you can use it directly
online with the Online LP Solver. Powered by the SSC-LP engine, you can solve linear programming problems conveniently from your browser,
achieving quick results.
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} \)
\( \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} \)
\( \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.
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.
The SSC library is also capable of solving linear programming problems with semi-continuous variables and supports Special Ordered Sets (SOS) of type 1 and 2. This allows the handling of a wide range of complex optimization problems, such as those that require binary variable selection or the management of consecutive variables with specific constraints.
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.