% This LaTeX document was generated using the LaTeX backend of PlDoc,
% The SWI-Prolog documentation system



\subsection{Introduction}

\label{sec:simplex-intro}

A \textbf{linear programming problem} or simply \textbf{linear program} (LP)
consists of:

\begin{shortlist}
    \item a set of \textit{linear} \textbf{constraints}
    \item a set of \textbf{variables}
    \item a \textit{linear} \textbf{objective function}.
\end{shortlist}

The goal is to assign values to the variables so as to \textit{maximize} (or
minimize) the value of the objective function while satisfying all
constraints.

Many optimization problems can be modeled in this way. As one basic
example, consider a knapsack with fixed capacity C, and a number of
items with sizes \verb$s(i)$ and values \verb$v(i)$. The goal is to put as many
items as possible in the knapsack (not exceeding its capacity) while
maximizing the sum of their values.

As another example, suppose you are given a set of \textit{coins} with
certain values, and you are to find the minimum number of coins such
that their values sum up to a fixed amount. Instances of these
problems are solved below.

Solving an LP or integer linear program (ILP) with this library
typically comprises 4 stages:

\begin{enumerate}
    \item an initial state is generated with \predref{gen_state}{1}
    \item all relevant constraints are added with \predref{constraint}{3}
    \item \predref{maximize}{3} or \predref{minimize}{3} are used to obtain a \textit{solved state} that
represents an optimum solution
    \item \predref{variable_value}{3} and \predref{objective}{2} are used on the solved state to obtain
variable values and the objective function at the optimum.
\end{enumerate}

The most frequently used predicates are thus:

\begin{description}
    \predicate{gen_state}{1}{-State}
Generates an initial state corresponding to an empty linear program.

    \predicate{constraint}{3}{+Constraint, +S0, -S}
Adds a linear or integrality constraint to the linear program
corresponding to state \arg{S0}. A linear constraint is of the form \verb$Left Op C$, where \arg{Left} is a list of \verb$Coefficient*Variable$ terms
(variables in the context of linear programs can be atoms or
compound terms) and \arg{C} is a non-negative numeric constant. The list
represents the sum of its elements. \arg{Op} can be \verb$=$, \verb$=<$ or \verb$>=$.
The coefficient \verb$1$ can be omitted. An integrality constraint is of
the form \verb$integral(Variable)$ and constrains Variable to an integral
value.

    \predicate{maximize}{3}{+Objective, +S0, -S}
Maximizes the objective function, stated as a list of
\verb$Coefficient*Variable$ terms that represents the sum of its
elements, with respect to the linear program corresponding to state
\arg{S0}. \Sneg{}arg\{\arg{S}\} is unified with an internal representation of the solved
instance.

    \predicate{minimize}{3}{+Objective, +S0, -S}
Analogous to \predref{maximize}{3}.

    \predicate{variable_value}{3}{+State, +Variable, -Value}
\arg{Value} is unified with the value obtained for \arg{Variable}. \arg{State} must
correspond to a solved instance.

    \predicate{objective}{2}{+State, -Objective}
Unifies \arg{Objective} with the result of the objective function at the
obtained extremum. \arg{State} must correspond to a solved instance.
\end{description}

All numeric quantities are converted to rationals via \predref{rationalize}{1},
and rational arithmetic is used throughout solving linear programs. In
the current implementation, all variables are implicitly constrained
to be \textit{non-negative}. This may change in future versions, and
non-negativity constraints should therefore be stated explicitly.

\subsection{Delayed column generation}

\label{sec:simplex-delayed-column}

\textit{Delayed column generation} means that more constraint columns are
added to an existing LP. The following predicates are frequently used
when this method is applied:

\begin{description}
    \predicate{constraint}{4}{+Name, +Constraint, +S0, -S}
Like \predref{constraint}{3}, and attaches the name \arg{Name} (an atom or compound
term) to the new constraint.

    \predicate{shadow_price}{3}{+State, +Name, -Value}
Unifies \arg{Value} with the shadow price corresponding to the linear
constraint whose name is \arg{Name}. \arg{State} must correspond to a solved
instance.

    \predicate{constraint_add}{4}{+Name, +Left, +S0, -S}
\arg{Left} is a list of \verb$Coefficient*Variable$ terms. The terms are added
to the left-hand side of the constraint named \arg{Name}. \arg{S} is unified
with the resulting state.
\end{description}

An example application of \textit{delayed column generation} to solve a \textit{bin
packing} task is available from:
\href{https://www.metalevel.at/various/colgen/}{\textbf{metalevel.at/various/colgen/}}

\subsection{Solving LPs with special structure}

\label{sec:simplex-special-structure}

The following predicates allow you to solve specific kinds of LPs more
efficiently:

\begin{description}
    \predicate{transportation}{4}{+Supplies, +Demands, +Costs, -Transport}
Solves a transportation problem. \arg{Supplies} and \arg{Demands} must be lists
of non-negative integers. Their respective sums must be equal. \arg{Costs}
is a list of lists representing the cost matrix, where an entry
(\textit{i},\textit{j}) denotes the integer cost of transporting one unit from \textit{i}
to \textit{j}. A transportation plan having minimum cost is computed and
unified with \arg{Transport} in the form of a list of lists that
represents the transportation matrix, where element (\textit{i},\textit{j})
denotes how many units to ship from \textit{i} to \textit{j}.

    \predicate{assignment}{2}{+Cost, -Assignment}
Solves a linear assignment problem. \arg{Cost} is a list of lists
representing the quadratic cost matrix, where element (i,j) denotes
the integer cost of assigning entity \$i\$ to entity \$j\$. An
assignment with minimal cost is computed and unified with
\arg{Assignment} as a list of lists, representing an adjacency matrix.
\end{description}

\subsection{Examples}

\label{sec:simplex-examples}

We include a few examples for solving LPs with this library.

\subsubsection{Example 1}

\label{sec:simplex-ex-1}

This is the "radiation therapy" example, taken from
\textit{Introduction to Operations Research} by Hillier and Lieberman.

\href{https://www.metalevel.at/prolog/dcg}{\textbf{Prolog DCG notation}} is
used to \textit{implicitly} thread the state through posting the
constraints:

\begin{code}
:- use_module(library(simplex)).

radiation(S) :-
        gen_state(S0),
        post_constraints(S0, S1),
        minimize([0.4*x1, 0.5*x2], S1, S).

post_constraints -->
        constraint([0.3*x1, 0.1*x2] =< 2.7),
        constraint([0.5*x1, 0.5*x2] = 6),
        constraint([0.6*x1, 0.4*x2] >= 6),
        constraint([x1] >= 0),
        constraint([x2] >= 0).
\end{code}

An example query:

\begin{code}
?- radiation(S), variable_value(S, x1, Val1),
                 variable_value(S, x2, Val2).
Val1 = 15 rdiv 2,
Val2 = 9 rdiv 2.
\end{code}

\subsubsection{Example 2}

\label{sec:simplex-ex-2}

Here is an instance of the knapsack problem described above, where
\verb$C = 8$, and we have two types of items: One item with value 7
and size 6, and 2 items each having size 4 and value 4. We introduce
two variables, \verb$x(1)$ and \verb$x(2)$ that denote how many items
to take of each type.

\begin{code}
:- use_module(library(simplex)).

knapsack(S) :-
        knapsack_constraints(S0),
        maximize([7*x(1), 4*x(2)], S0, S).

knapsack_constraints(S) :-
        gen_state(S0),
        constraint([6*x(1), 4*x(2)] =< 8, S0, S1),
        constraint([x(1)] =< 1, S1, S2),
        constraint([x(2)] =< 2, S2, S).
\end{code}

An example query yields:

\begin{code}
?- knapsack(S), variable_value(S, x(1), X1),
                variable_value(S, x(2), X2).
X1 = 1
X2 = 1 rdiv 2.
\end{code}

That is, we are to take the one item of the first type, and half of one of
the items of the other type to maximize the total value of items in the
knapsack.

If items can not be split, integrality constraints have to be imposed:

\begin{code}
knapsack_integral(S) :-
        knapsack_constraints(S0),
        constraint(integral(x(1)), S0, S1),
        constraint(integral(x(2)), S1, S2),
        maximize([7*x(1), 4*x(2)], S2, S).
\end{code}

Now the result is different:

\begin{code}
?- knapsack_integral(S), variable_value(S, x(1), X1),
                         variable_value(S, x(2), X2).

X1 = 0
X2 = 2
\end{code}

That is, we are to take only the \textit{two} items of the second type.
Notice in particular that always choosing the remaining item with best
performance (ratio of value to size) that still fits in the knapsack
does not necessarily yield an optimal solution in the presence of
integrality constraints.

\subsubsection{Example 3}

\label{sec:simplex-ex-3}

We are given:

\begin{shortlist}
    \item 3 coins each worth 1 unit
    \item 20 coins each worth 5 units and
    \item 10 coins each worth 20 units.
\end{shortlist}

The task is to find a \textit{minimal} number of these coins that amount to
111 units in total. We introduce variables \verb$c(1)$, \verb$c(5)$ and \verb$c(20)$
denoting how many coins to take of the respective type:

\begin{code}
:- use_module(library(simplex)).

coins(S) :-
        gen_state(S0),
        coins(S0, S).

coins -->
        constraint([c(1), 5*c(5), 20*c(20)] = 111),
        constraint([c(1)] =< 3),
        constraint([c(5)] =< 20),
        constraint([c(20)] =< 10),
        constraint([c(1)] >= 0),
        constraint([c(5)] >= 0),
        constraint([c(20)] >= 0),
        constraint(integral(c(1))),
        constraint(integral(c(5))),
        constraint(integral(c(20))),
        minimize([c(1), c(5), c(20)]).
\end{code}

An example query:

\begin{code}
?- coins(S), variable_value(S, c(1), C1),
             variable_value(S, c(5), C5),
             variable_value(S, c(20), C20).

C1 = 1,
C5 = 2,
C20 = 5.
\end{code}