<gh_stars>10-100
\documentclass[aspectratio = 169]{beamer}

\usepackage[utf8]{inputenc} % Character encoding.

\pdfinfo{
   /Author (<NAME>)
   /Title  (The Simplex Algorithm II)
   /Subject (Linear Programs)
}


\usepackage{./Style/linearProgramsBeamer} % This is extra styling for Beamer environments.
\usepackage{./Style/linearProgramsStyle} % This is a set of commands for maths content.

%-------------------------------------------------------------------------------
%   TITLE PAGE
%-------------------------------------------------------------------------------

\author[BD]{<NAME>}

\institute[]{EPITA}

\title{Linear Programs} %
\subtitle{The Simplex Algorithm II}

%-------------------------------------------------------------------------------
%   DOCUMENT BODY
%-------------------------------------------------------------------------------

\begin{document}

\begin{frame}[plain]
\titlepage % Print the title page as the first slide
\end{frame}

\begin{frame}{Où on en est, à quoi on fait face.}
  La procédure adoptée à ce stade s'est toujours terminée. Notre
  conjecture de base est qu'elle nous renvoie un point optimal du
  programme linéaire de départ. Pour l'instant on ne peut pas en être
  certains. Par bien des égards ce qu'on a fait jusqu'à présent est
  loin d'être satisfaisant. Étant donné un programme linéaire $L$,
  voici une liste de points qu'ils nous restent à éclaircir:
    \begin{itemize}
    \item[\textcolor<6>{lightgray}{\textbullet}]<1->
      \textcolor<6>{lightgray}{Comment savoir si $L$ est admissible?}
    \item[\textcolor<6>{lightgray}{\textbullet}]<2->
      \textcolor<6>{lightgray}{Que faire lorsque la solution de base
        n'est pas admissible?}
        \item[\textbullet]<3->
          Comment vérifier que $L$ n'est pas majoré?
        \item[\textbullet]<4-> Est-ce que la procédure qu'on a pu
          tester jusqu'à présent se termine en général?
        \item[\textcolor<6>{lightgray}{\textbullet}]<5->
          \textcolor<6>{lightgray}{Si la procédure se termine, est-ce
            qu'on en déduit toujours une valeur optimale?}
    \end{itemize}
\end{frame}

\section{Pivoter}

\begin{frame}{Pivoter | Fixer la notation}
  Dans le but de répondre aux questions qu'ils nous restent à aborder
  il va nous falloir écrire au propre les algorithmes qu'on a testés à
  la main. On considère le programme linéaire $L$
  \begin{figure}
    \alt<4>{
      \textcolor{orange}{
        \begin{linearProgG}{
            ${\displaystyle z - \sum_{j=1}^n c_jx_j} = \nu$
          }{
            ${\displaystyle \forall i \in \{1, \ldots, m\}, \quad \sum_{j=1}^n a_{ij}x_j + x_{i+m} = b_i}$
          }{
            $\forall j \in N\cup B, \quad x_j \geq 0$
          }
        \end{linearProgG}
      }
    }{
      \alt<3>{
        \begin{linearProgG}{
            ${\displaystyle z = \nu + \sum_{j=1}^n c_jx_j}$
          }{
            ${\displaystyle \forall i \in \{1, \ldots m \}, \quad x_{i+m} = b_i - \sum_{j=1}^n a_{ij}x_j}$
          }{
            $\forall j \in N\cup B, \quad x_j \geq 0.$
          }
        \end{linearProgG}
      }{
        \begin{linearProgG}{
            ${\displaystyle z = \nu + \sum_{j=1}^n c_jx_j}$
          }{
            ${\displaystyle \forall i \in \{1, \ldots, m\}, \quad \sum_{j=1}^n a_{ij}x_j \leq b_i}$
          }{
            $\forall j \in N, \quad x_j \geq 0$
          }
        \end{linearProgG}
      }
    }
    \end{figure}
    \begin{overlayarea}{\textwidth}{.3\textheight}
        \begin{onlyenv}<1>
          On écrit
            \begin{itemize}
            \item[\textbullet]
              $\bs{A}$ pour la matrice de taille $(m, n)$ des coefficients
              $\big(a_{ij}\big)_{\substack{1 \leq i \leq m \\ 1 \leq j \leq n}}$
            \item[\textbullet]
              $\bs{b}$ pour le $m$-tuple $(b_1, \ldots, b_m)$
            \item[\textbullet]
              $\bs{c}$ pour le $n$-tuple $(c_1, \ldots, c_n)$.
            \end{itemize}
            Noter que $\nu$ est la valeur objective de la solution de
            base.
        \end{onlyenv}
        \begin{onlyenv}<2> Le programme linéaire $L$ dans cette forme
          est décrit par la donnée $(\bs{A}, \bs{b}, \bs{c},
          \nu)$. Le programme initial a en général $\nu = 0$.
        \end{onlyenv}
        \begin{onlyenv}<3-> Pour encoder la forme slack on inclus
          également les données $N$, $B$ des indices de variables
          hors-base et de base. Une forme slack est donc donnée par
          $(N, B, \bs{A}, \bs{b}, \bs{c}, \nu)$. L'ensemble $N$ est
          initialisé à $\{1, \ldots, n\}$ et $B$ à
          $\{n+1, \ldots, n+m\}$. \pause[4] \textcolor{orange}{Pour se
            rapprocher de l'écriture d'un système linéaire on modifie
            légèrement l'écriture de la forme slack.}
        \end{onlyenv}
    \end{overlayarea}
\end{frame}

\begin{frame}
  \frametitle{Pivoter | Le tableau d'un programme linéaire}
  Les contraintes linéaires de $L$ dans la forme slack représente une
  matrice $(m, n+m)$ notée $\underline{\bs{A}}$ et obtenue comme
  concaténation de $\bs{A}$ et $\bs{I}_m$ le long des lignes de
  $\bs{A}$. Le \emph{tableau} $T$ de $L$ est obtenu en
  \begin{itemize}
  \item<2-> concaténant $\underline{\bs{A}}$ et $b^T$ le long des
    lignes de $A$
  \item<3-> concaténant les résultats avec le vecteur
    $(-c_1, \ldots, -c_n, 0, \ldots 0, \nu)$ de taille $n+m+1$ le long
    des colonnes de $\bs{A}$.
  \end{itemize}
  \pause[4]
  \begin{figure}
    \begin{tabular}{c|ccc|cccc|c|}
       & \alert{$\bs{x_1}$} & \alert{$\cdots$} & \alert{$\bs{x_n}$} & \alert{$\bs{x_{n+1}}$} & \alert{$\bs{x_{n+2}}$} & \alert{$\cdots$} & \alert{$\bs{x_{n+m}}$} &  \\
      \hline
       & $-c_1$ & $\cdots$ & $-c_n$ & $0$ & $0$ & $\cdots$ & $0$ & $\nu$ \\
      \hline
      \alert{$\bs{n+1}$} & $a_{11}$ & $\cdots$ & $a_{1n}$ & $1$ & $0$ & $\cdots$ & $0$ & $b_1$ \\
      \alert{$\bs{n+2}$}& $a_{21}$ & $\cdots$ & $a_{2n}$ & $0$ & $1$ & $\cdots$ & $0$ & $b_2$ \\
      \alert{$\vdots$}& $\vdots$ & $\ddots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\ddots$ & $\vdots$ & $\vdots$ \\
      \alert{$\bs{n+m}$} & $a_{m1}$ & $\cdots$  & $a_{mn}$  & $0$ & $\cdots$ & $\cdots$ & $1$ & $b_m$
    \end{tabular}
  \end{figure}
  Le tableau $T$ est de taille $(m + 1, n + m + 1)$.
\end{frame}

\begin{frame}[fragile]{Pivoter}
  We are given input $(N, B, \bs{A}, \bs{b}, \bs{c}, \nu)$ and two
  indexes $e \in N$, $l\in B$ respectively corresponding to
  entering and leaving variables to and from the set of \textit{basic}
  variables $B$.
    \begin{columns}
        \begin{column}{.5\textwidth}
            \begin{itemize}
                \item[\textbullet]<2->
                  Express $x_e$ in terms of other variables in
                  equation $l$
                \item[\textbullet]<3->
                  Replace $x_e$ by previously obtained expression in
                  linear constraints
                \item[\textbullet]<4->
                  Replace $x_e$ by corresponding expression in the
                  value function
                \item[\textbullet]<5->
                  Update basic and none basic sets of variables.
            \end{itemize}
        \end{column}
        \begin{column}{.5\textwidth}
            \begin{overlayarea}{.96\textwidth}{.45\textheight}
            \begin{onlyenv}<2->
                \begin{tcolorbox}[
                    enhanced,
                    parbox = false,
                    colback = mLightBrown!10!white,
                    colframe = mLightBrown,
                    arc = 0mm,
                    ]
                    \small{
                    \mint{python}{T[l, :] = (1/T[l, e])*T[l, :]}
                    }
                    \end{tcolorbox}
            \end{onlyenv}
            \begin{onlyenv}<3->
                \begin{tcolorbox}[
                    enhanced,
                    parbox = false,
                    colback = mLightBrown!10!white,
                    colframe = mLightBrown,
                    arc = 0mm,
                    ]
                    \small{
                      \begin{minted}[autogobble]{python}
                        if i != l:
                          T[i, :] -= T[i, e]*T[l, :]
                      \end{minted}
                    }
                \end{tcolorbox}
            \end{onlyenv}
            \begin{onlyenv}<5>
                \begin{tcolorbox}[
                    enhanced,
                    parbox = false,
                    colback = mLightBrown!10!white,
                    colframe = mLightBrown,
                    arc = 0mm,
                    ]
                    \small{
                      \begin{minted}[autogobble]{python}
                        N.insert(N.index(e), l).remove(e)
                        B.insert(B.index(l), e).remove(l)
                      \end{minted}
                    }
            \end{tcolorbox}
            \end{onlyenv}
        \end{overlayarea}
        \end{column}
    \end{columns}
\end{frame}

\begin{frame}[fragile]{Pivoter | Full Function}
     \small{
      \begin{minted}[linenos]{python}
        def pivot(N, B, T, e, l):
            """Pivoting in linear programs.

            Pivots entering and leaving variables in linear
            program given as tableau. Done in place.
            """
            T[l, :] = (1/T[l, e])*T[l, :]
            for i in range(m+1):
                if i != l:  # ugly
                    T[i, :] -= T[i, e]*T[i, :]
            N.insert(N.index(e), l).remove(e)
            B.remove(B.index(l), e).remove(l)
      \end{minted}
    }
\end{frame}

\begin{frame}{Pivoter | Full Function}
  \begin{itemize}
  \item<1->
    Index $e$ is an element of $N$ and $l$ one of $B$.
  \item<2->
    There better be no entries $e$, $l$ such that
    \mintinline{python}{T[l, e] == 0}. We shall ensure this is never
    the case when \mintinline{python}{pivot} is used.
  \item<3->
    The objective value and basic solution of obtained linear program
    can be read on last column to the right.
  \end{itemize}
\end{frame}

\section{Détecter le fait de ne pas être borné}

\begin{frame}{Tester la non \emph{bornitude}}
  On note $L$ le programme linéaire en forme standard
  \begin{figure}
    \begin{linearProgG}{
        ${\displaystyle z = \nu + \sum_{j=1}^n c_jx_j}$
      }{
        ${\displaystyle \forall i \in \{1, \ldots, m\}, \quad \sum_{j=1}^n a_{ij}x_j \leq b_i}$
      }{
        $\forall j \in N, \quad x_j \geq 0$
      }
    \end{linearProgG}
  \end{figure}
  \begin{halfshyblock}{Fait}
    \begin{onlyenv}<1
      >S'il y a un indice $j$ tel que $c_j > 0$ et
      tous les coefficients de $x_j$ dans les contraintes linéaires
      sont négatifs alors $L$ est non majoré.
    \end{onlyenv}
    \begin{onlyenv}<2-
      >\!\alert{De manière équivalente, s'il y a une
        colonne dans le tableau de $L$ ayant une première entrée
        négative non nulle et toutes les autres négatives alors $L$
        est non majoré.}
    \end{onlyenv}
    \end{halfshyblock}
\end{frame}

\begin{frame}{Tester la non \emph{bornitude}}
  En utilisant le fait précédent, à chaque appel de
  \mintinline{python}{pivot}, on teste si on ne satisfait pas la
  propriété:
  \begin{quote}
    Il existe un indice $j$ tel que $c_j > 0$ et tous les autres
    coefficients de $x_j$ sont négatifs ou nuls.
    \end{quote}
    \pause
    C'est une condition nécessaire, pour l'instant on a aucune
    garantie qu'on tombe dans une telle situation quand $L$ n'est pas
    majoré. Le fait que ce soit le cas vient des résultats de dualité.

    \pause Pour l'instant on va devoir accepter que ce test naïf sera
    suffisant\footnote{Il l'est mais on a encore aucune certitude.}.
\end{frame}

\section{The Simplex Algorithm : Second Try}

\begin{frame}[fragile]{The Simplex Algorithm \emph{Restricted}}
  \begin{overlayarea}{1.1\textwidth}{.75\textheight}
  \setlength{\columnsep}{-10pt}
  \begin{multicols}{2}
    \scriptsize{
      \begin{minted}[autogobble, linenos, breaklines]{python}
        # Under construction function!
        def _simplex(N, B, T):
            """Restricted simplex algorithm

            Runs simplex algorithm on basic feasible
            linear program in slack form.

            Args:
              N, B (list[int]): lists of non-basic
              and basic variables.
              T (ndarray[float]): numpy array for
              tableau of linear program.
            Output:
              (ndarray[float]) vector tail of which
              is maximal objective value, rest is
              optimal point.
            """
            m, margins = len(B), dict()
            aug_var = [i for i in N if T[0, i] < 0]
            while aug_var:
              e = random.choice(augmenting_var)
              for i in range(m):
                if T[i, e] > 0:
                  margins[B[i]] = T[i, -1]/T[i, e]
              if not margins:
                raise Exception("Unbounded LP")
              min_margin = min(margins.values())
              minima = [i for i in margins\
                        if margins[i] == min_margin]
              l = random.choice(minima)
              pivot(N, B, T, e, l)
              aug_var = [i for i in N if T[0, i] < 0]
            return T[:, -1]
      \end{minted}
    }
  \end{multicols}
  \end{overlayarea}
\end{frame}

\begin{frame}{Boucler}
  À chaque fois qu'on entre dans la boucle \mintinline{python}{while}
  de \mintinline{python}{_simplex} ou bien on \textit{augmente la
    valeur objective} ou alors on découvre que le PL est non-majoré. A
  priori, \mintinline{python}{_simplex} pourrait s'exécuter
  indéfiniment, en itérant entre des formes slack équivalentes ayant
  une valeur objective constante. On va chercher à étudier ce
  phénomène.
  \pause
  \begin{prop}[\textbf{C}]
    Soit $L$ un PL $(N, B, \bs{A}, \bs{b}, \bs{c}, \nu)$ où $\bs{A}$
    est une matrice $(m, n)$. Si la boucle de
    \mintinline{python}{_simplex} s'exécute plus de $\binom{n+m}{m}$
    fois, alors l'algorithme boucle, i.e. la boucle s'exécute
    indéfiniment en alternant entre un nombre fini de formes slack
    ayant la même valeur objective.
  \end{prop}
  \begin{rem}
    Cela signifie que dès que \mintinline{python}{_simplex} entre
    dans sa boucle principale plus $\binom{n+m}{m}$ fois alors on
    peut retourner la valeur objective et la solution de base
    courante.
  \end{rem}
\end{frame}

\begin{frame}{Boucler}
  La preuve de la proposition ci-dessus se base sur deux faits:
  \begin{itemize}
  \item si on tombe sur une forme slack déjà vue au cours de la
    résolution des précédentes itérations, alors on retrouvera par
    la suite les mêmes itérations qui s'ensuivaient, on a un
    comportement périodique ;
  \item il n'y a qu'un nombre fini de formes slacks possibles pour
    un même programme linéaire.
  \end{itemize}

  \pause Seul le second point nécessite d'être clarifié. On se
  contente de le montrer dans le cas de PL ayant un lieu admissible
  d'intérieur non vide.
\end{frame}

\begin{frame}{Boucler}
  \begin{lem}[$\bs{B}$]
    Soit $L$ un PL donné par $(\bs{A}, \bs{b}, \bs{c})$. Une forme
    slack de $L$ qui apparaît dans \mintinline{python}{_simplex} est
    déterminée par le choix d'un sous-ensemble $B$ de variables de
    base.
  \end{lem}
  \pause
  \setlength\columnseprule{.1pt}
  \begin{multicols}{2}
    \begin{demo}
      Deux formes slacks $(N, B, \bs{A}, \bs{b}, \bs{c}, \nu)$ et
      $(N, B, \bs{A'}, \bs{b'}, \bs{c'}, \nu')$ sont équivalentes.
      \pause

      \vspace{\baselineskip}
      En étudiants la différence des contraintes linéaires, on obtient
      les relations:
      \[
        0 = (\nu - \nu') + \sum_{j \in N} (c_j - c_j')x_j
      \]
      et pour chaque $i \in B$
      \[
        0 = (b_i - b_i') - \sum_{j \in N} (a_{ij} - a_{ij}')x_j.
      \]

      \pause Ces relations étant vraie pour tout vecteur
      $(x_1, \ldots, x_n)$ dans le lieu admissible de LP, si le lieu
      admissible de LP est d'intérieur non vide, il est clair que pour
      tout $i \in B$ et $j \in N$ on a $\nu = \nu'$, $b_i = b_i'$,
      $c_j = c_j'$, $a_{ij} = a_{ij}'$.
    \end{demo}
  \end{multicols}
\end{frame}

\begin{frame}{Boucler}
  Rajouter un compteur de boucle à l'algo du
  \mintinline{python}{_simplex} garanti la terminaison de
  \mintinline{python}{_simplex}.
  \pause
  \begin{rem}
    Cette solution n'est pas intelligente. Il y a plusieurs solutions
    à ce problème en pratique. Dans notre cas on implémente la règle
    de \emph{Bland}: à chaque choix d'indice aux lignes $21$ et $30$
    de \mintinline{python}{_simplex}, on choisit le plus petit
    possible.
  \end{rem}
\end{frame}

\begin{frame}[fragile]{The Simplex Algorithm \emph{Restricted} | No Cycling Version}
  \begin{overlayarea}{1.1\textwidth}{.75\textheight}
  \setlength{\columnsep}{-10pt}
  \begin{multicols}{2}
    \scriptsize{
      \begin{minted}[autogobble, linenos, breaklines]{python}
        def _simplex(N, B, T):
            """Restricted simplex algorithm

            Runs simplex algorithm on basic feasible
            linear program in slack form.

            Args:
              N, B (list[int]): lists of non-basic
              and basic variables.
              T (ndarray[float]): numpy array for
              tableau of linear program.
            Output:
              (ndarray[float]) vector tail of which
              is maximal objective value, rest is
              optimal point.
            """
            m = len(B)
            l, margin = None, float('inf')
            aug_var = [i for i in N if T[0, i] < 0]
            while aug_var:
              e = min(augmenting_var)
              for i in range(m):
                if T[i, e] > 0:
                   if T[i, -1]/T[i, e] < margin:
                     margin = T[i, -1]/T[i,e]
                     l = i
              if not l:
                raise Exception("Unbounded LP")
              pivot(N, B, T, e, l)
              aug_var = [i for i in N if T[0, i] < 0]
            return T[:, -1]
      \end{minted}
    }
  \end{multicols}
  \end{overlayarea}
\end{frame}

\begin{frame}
  \centering
  {\huge \textbf{C'est tout pour aujourd'hui!}}
\end{frame}

\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:
