\chapterauthor{Xavier Meyer and Bastien Chopard}{Department of Computer Science, University of Geneva, Switzerland}
-\chapterauthor{Paul Albuquerque}{Institute for Informatics and Telecommunications, hepia, \\ University of Applied Sciences of Western Switzerland -- Geneva, Switzerland}
+\chapterauthor{Paul Albuquerque}{Institute for Informatics and Telecommunications, HEPIA, \\ University of Applied Sciences of Western Switzerland -- Geneva, Switzerland}
%\chapterauthor{Bastien Chopard}{Department of Computer Science, University of Geneva}
%\chapter{Linear programming on a GPU: a study case based on the simplex method and the branch-cut-and bound algorithm}
-\chapter{Linear Programming on a GPU: A~Case~Study}
+\chapter{Linear programming on a GPU: a~case~study}
\section{Introduction}
\label{chXXX:sec:intro}
The simplex method~\cite{VCLP} is a well-known optimization algorithm for solving linear programming (LP) models in the field of operations research. It is part of software often employed by businesses for finding solutions to problems such as airline scheduling problems. The original standard simplex method was proposed by Dantzig in 1947. A more efficient method, named the revised simplex, was later developed. Nowadays its sequential implementation can be found in almost all commercial LP solvers. But the always increasing complexity and size of LP problems from the industry, drives the demand for more computational power.
\subsubsection*{Choice of the leaving variable}
The stability and robustness of the algorithm depend considerably on the choice of the leaving variable. With respect to this, the \textit{expand} method~\cite{GILL1989} proves to be very useful in the sense that it helps to avoid cycles and reduces the risks of encountering numerical instabilities. This method consists of two steps of complexity $\mathcal{O}(m)$. In the first step, a small perturbation is applied to the bounds of the variables to prevent stalling of the objective value, thus avoiding cycles. These perturbed bounds are then used to determine the greatest gain on the entering variable imposed by the most constraining basic variable. The second phase uses the original bounds to define the basic variable offering the gain closest to the one of the first phase. This variable will then be selected for leaving the basis.
-
+\clearpage
\section{Branch-and-bound\index{branch-and-bound} algorithm}
\label{chXXX:sec:bnb}
\subsection{Integer linear programming\index{integer linear programming}}
The cutting-planes generated must be carefully selected in order to avoid a huge increase in the problem size. They are selected according to three criteria: their efficiency, their orthogonality with respect to other cutting-planes, and their parallelism with respect to the objective function.
Cutting-planes having the most impact on the problem are then selected, while the others are dropped.
-
+\clearpage
\section{CUDA considerations}
\label{chXXX:sec:cuda}
The most expensive operations in the simplex algorithm are linear algebra functions.
\begin{figure}[!h]
\centering
\includegraphics[width=10cm]{Chapters/chapter10/figures/Reduc3.pdf}
-\caption{Example of a parallel reduction at block level (courtesy NVIDIA).}
+\caption{Example of a parallel reduction at block level. (Courtesy NVIDIA).}
\label{chXXX:fig:reduc}
\end{figure}
Only variables required for decision-making operations are updated on the CPU.
The communications arising from the aforementioned scheme are illustrated in Figure~\ref{chXXX:fig:diagSTD}.
The amount of data exchanged at each iteration is independent of the problem size ensuring that this implementation scales well as the problem size increases.
-
+\clearpage
\begin{figure}[!h]
\centering
\includegraphics[width=90mm]{Chapters/chapter10/figures/DiagSTD_cap.pdf}
maros.mps & 847 & 1443 & 10006 & 1.7\\ \hline
perold.mps & 626 & 1376 & 6026 & 1.0\\ \hline
\end{tabular}
-\caption{NETLIB problems solved in the range of 1 to 4 seconds}
+\caption{NETLIB problems solved in the range of 1 to 4 seconds.}
\label{chXXX:tab:medium}
\end{center}
\end{table}
\end{figure}
Finally, the biggest problems, and slowest to solve, are given in Table~\ref{chXXX:tab:big}. A new tendency can be observed in Figure~\ref{chXXX:fig:SlowSolve}. The \textit{Revised-sparse} method is the fastest on most of the problems. The performances are still close between the best two methods on problems having a C-to-R ratio close to 2 such as bnl2.mps, pilot.mps, or greenbeb.mps. However, when this ratio is greater, the \textit{Revised-sparse} can be nearly twice as fast as the standard method. This is noticeable on 80bau3b.mps (4.5) and fit2p.mps (4.3). Although the C-to-R ratio of d6cube.mps (14.9) exceeds the ones previously mentioned, the \textit{Revised-sparse} method doesn't show an impressive performance, probably due to the small amount of rows and the density of this problem, which doesn't fully benefit from the lower complexity of sparse operations.
-
+\clearpage
\begin{table}[!h]
\begin{center}
\begin{tabular}{|l|r|r|r|r|}
