\documentclass[11pt,A4]{article}
\usepackage[a4paper, total={15cm, 20cm}]{geometry}
\usepackage{xcolor}
\usepackage[colorlinks]{hyperref}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,      
    urlcolor=cyan,
    pdftitle={Overleaf Example},
    pdfpagemode=FullScreen,
    }
\urlstyle{same}

\usepackage{fancyvrb}
\usepackage{wrapfig}
\usepackage{graphicx}
\usepackage{imakeidx}

\usepackage{titlesec}
\usepackage{wrapfig}

\usepackage[all,cmtip]{xy}

\setcounter{secnumdepth}{4}
%\setcounter{secnumdepth}{0} %no numbering of sections
%\titleformat{\section}
%  {\normalfont\Large\bfseries\filcenter}{Excursion \thesection}
%  {0em}{}


\usepackage{amsmath}
\usepackage{amsthm}
\theoremstyle{definition}
\newtheorem{excursion}{Excursion}[section]

\usepackage{xspace}

\newcommand{\allbases}{\textsf{allbases}\xspace}
\newcommand{\Begin}{\textsf{begin}\xspace}
\newcommand{\eliminate}{\textsf{eliminate}\xspace}
\newcommand{\extract}{\textsf{extract}\xspace}
\newcommand{\End}{\textsf{end}\xspace}
\newcommand{\fel}{\textsf{fel}\xspace}
\newcommand{\geometric}{\textsf{geometric}\xspace}
\newcommand{\lrs}{\textsf{lrs}\xspace}
\newcommand{\lrslib}{\textsf{lrslib-073}\xspace}
\newcommand{\minrep}{\textsf{minrep}\xspace}
\newcommand{\mplrs}{\textsf{mplrs}\xspace}
\newcommand{\plrs}{\textsf{plrs}\xspace}
\newcommand{\printcobasis}{\textsf{printcobasis}\xspace}
\newcommand{\project}{\textsf{project}\xspace}
\newcommand{\redund}{\textsf{redund}\xspace}
\newcommand{\redundl}{\textsf{redund\_list}\xspace}
\newcommand{\testlin}{\textsf{testlin}\xspace}
\newcommand{\volume}{\textsf{volume}\xspace}

\newcommand{\Hr}{\textit{H}-representation\xspace}
\newcommand{\Vr}{{\textit{V}-representation}\xspace}
\newcommand{\bv}{\begin{Verbatim}[samepage=true,fontsize=\footnotesize]}

\renewcommand{\contentsname}{Excursions}

\title{Excursions in Polyhedral Computation using \lrs }

\makeindex 

%%% BEGIN DOCUMENT

\begin{document}

\let\cleardoublepage\clearpage


\maketitle

(Under construction)

\textbf{Copyright: David Avis } 
\url{https://cgm.cs.mcgill.ca/~avis/}

%\mainmatter
\sloppy
Welcome to the world of Polyhedral Computation. This 
hands-on guide is meant
to be used in conjunction with Komei Fukuda's 
\href{https://people.inf.ethz.ch/fukudak/polyfaq/node2.html}{Polyhedral Computation FAQ}.
If you are new to the field and want to find out what it
is please click that link now! In fact, most definitions and other 
theoretical
explanations will be given by links to this very useful site.
To dive deeper into the theory two excellent resources are
Komei Fukuda's \href{https://www.research-collection.ethz.ch/bitstream/handle/20.500.11850/426218/PolyCompBook20200829.pdf}{Polyhedral Computation} and 
G\"{u}nter Ziegler's \href{https://www.scribd.com/document/378130534/Lectures-on-Polytopes}{Lectures on Polytopes}.

We will run almost all examples using the program
\lrs and a few test files. 
\textcolor{red}{
Most examples can be run directly in your browser by clicking
the link} 
\href{https://ym28-it.github.io/lrs-web-app/lrs-common.html?mode=hybrid&version=v7.3&test=ex1.ine}{run} 
\textcolor{red}{
at various places. 
}
(Thanks to Yuta Muraya for
providing this interface). Note that the input files can be
modified and re-run 
directly in the browser window and this is highly recommended!
Alternatively you can download \lrs yourself following instructions
\href{https://cgm.cs.mcgill.ca/~avis/C/lrs.html}{here}
and use these
\href{https://cgm.cs.mcgill.ca/~avis/epc/inputs}{input files}.

Everyone should at least have the "hello world" experience
by doing \hyperref[ex:hw]{Excursion \ref{ex:hw}}. 
\hyperref[ex:bc]{Excursion \ref{ex:bc}} is a bit technical and boring,
but pretty much essential to get any kind of understanding for what
is going on. After that most excursions are independent.
 
Above all this is meant to be a hands on experience, so 
be sure to run (and modify!) the examples.
%\tableofcontents  %make4ht prints all links twice

%\textcolor{red}{Download:} 
%\href{https://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/archive/binaries}{binaries} 
%\xspace
%\href{https://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/archive/epc}{inputs}

%DIY table of contents
\newpage

\phantomsection
\hypertarget{contents}{}

\section*{Excursions}
\begin{enumerate}
\item
\hyperref[ex:hw]{Hello world, \Hr and \Vr: \lrs mode}
\item
\hyperref[ex:bc]{Bases, cobases and degeneracy (the villain)}
\item
\hyperref[ex:up]{Unbounded polyhedra, cuts and metrics}
\item
\hyperref[ex:ts]{Linearities and the travelling salesman}
\item
\hyperref[ex:vo]{Volume, triangulations, more cuts and metrics}
\item
\hyperref[ex:re]{Redundancy is bad and how to get rid of it: redund mode}
\item
\hyperref[ex:hl]{Hidden linearities and minimum representations: minrep mode}
\item
\hyperref[ex:pr]{Projections, Fourier-Motkin elimination: fel mode}
\item
\hyperref[ex:pr2]{More projections, the golden square}
\item
\hyperref[ex:ih]{Integer hull, more fun with cuts, metrics and the TSP}
\end{enumerate}

\newpage
\section{Hello world, \Hr and \Vr : \lrs mode}
\label{ex:hw}

A \href{https://people.inf.ethz.ch/fukudak/polyfaq/node4.html}{convex polyhedron} is defined by a set of linear
inequalities
and equations. One of the simplest and most useful examples is the
3-dimensional unit cube defined by the inequalities:
\[
0 \le x_i \le 1 \qquad i=1,2,3   
\]
It is an example of a bounded polyhedron, or polytope and this
representation of it is known as an (halfspace)$H$-representation.
Polyhedra can of course be unbounded, but for now we will deal only
with polytopes. We will also leave aside for now the possibility of using
equations. So an \Hr can be written in the form
\[
b + Ax \ge 0
\]
where $b$ is a column vector of length $m$ and $A$ is an 
$m$ by $d$ coefficient matrix. An inequality that can be deleted
without changing the solution set is \textit{redundant} and the
remaining rows after deleting all redundant ones are said to support
\textit{facets}\index{facets} of $P$. Redundancy removal is treated in 
\hyperref[ex:re]{Excursion \ref{ex:re}}

It will be represented in \lrs
by just the table of $m$ by $d+1$ coefficients $[b~ A]$
and a few headers.
For example the input file $cube.ine$ contains an \Hr for the cube:

\bv
mayumi% cat cube.ine
H-representation
begin
6 4 integer 
 0  1  0  0 
 0  0  1  0 
 0  0  0  1 
 1 -1  0  0 
 1  0 -1  0 
 1  0  0 -1 
end
\end{Verbatim}
We have a table of coefficients of size 6 by 4 integers which is bracketed
by \Begin and \End lines. Each of these rows represents the corresponding
row of the matrix $A$. 

The \href{https://people.inf.ethz.ch/fukudak/polyfaq/node14.html#thm:Minkowski-Weyl1}{Minkowski-Weyl Theorem} states every polytope can also be represented
as the convex hull of a set of extreme points, its \Vr.
The most fundamental task of \lrs is to compute a \Vr from an \Hr
and vice versa. So let us do it.

The \Vr of the cube is the list of the 8 0-1 vectors of length 3. 
We can compute these by running \lrs: 
\\
\href{https://ym28-it.github.io/lrs-web-app/lrs-common.html?mode=hybrid&version=v7.3&test=ex1.ine}{(run)}

\bv
mayumi% lrs cube.ine cube.ext
lrs:lrslib_v.7.3_2023.11.28(64bit,lrslong.h,hybrid_arithmetic)
*Input taken from  cube.ine
*Output sent to file cube.ext

mayumi% cat cube.ext
*lrs:lrslib_v.7.3_2023.11.28(64bit,lrslong.h,hybrid_arithmetic)
V-representation
begin
***** 4 rational
 1  1  1  1 
 1  0  1  1 
 1  1  0  1 
 1  0  0  1 
 1  1  1  0 
 1  0  1  0 
 1  1  0  0 
 1  0  0  0 
end
*Totals: vertices=8 rays=0 bases=8 integer_vertices=8  max_vertex_depth=3
\end{Verbatim}

For simplicity we have deleted a few other lines of output.
In the output file $cube.ext$
the 8 vertices are shown with a leading "1" that indicates the
line gives a vertex (a zero here would indicate an extreme ray, more later).
The "*****" indicates that the number of vertices is not known
when the output has started. This is due to the fact that \lrs uses
the \href{https://cgm.cs.mcgill.ca/%7Eavis/doc/rs/rsorigins.html}{reverse search technique} which  generates output as a stream,
a useful feature for very long runs. The data type is indicated
as "rational" even though all coefficients are integral. Again
this  is due to the fact the output is generated as a stream.
This is our "hello world" example.
If you were able to duplicate this \lrs run on your computer, congratulations,
everything else will be simple!

If we replace the "*****" by 8 in $cube.ext$ we get a valid \Vr
in \lrs format. We can run \lrs to compute its \Hr:
\\
\href{https://ym28-it.github.io/lrs-web-app/lrs-common.html?mode=hybrid&version=v7.3&test=cube.ext}{(run)}


\bv
mayumi% lrs cube.ext
*Input taken from  cube.ext
H-representation
begin
***** 4 rational
 0  1  0  0 
 0  0  1  0 
 0  0  0  1 
 1 -1  0  0 
 1  0  0 -1 
 1  0 -1  0 
end
*Totals: facets=6 bases=6 max_facet_depth=3
\end{Verbatim}

In this case since an output file was not specified the output is
produced on the terminal. We find the original 6 halfspaces, albeit in
a different order. 

This ends our first excursion, we invite you to try out some of the other
input files converting from \Hr to \Vr and vice versa.

\hyperlink{contents}{List of Excursions}

\newpage
\section{Bases, cobases and degeneracy (the villain)}
\label{ex:bc}
In  \hyperref[ex:hw]{Excursion \ref{ex:hw}} on the *Totals:
line you may have noticed the "bases=n" count. 
What is a basis? Given an \Hr for a polyhedron in $R^d$, an
\textit{extreme point} or \textit{vertex} is defined
by a linearly independent subset of $d$ inequalities
satisfied as equations, whose unique solution $\bar{x}$
satisfies the other inequalities. For example, given $cube.ine$
rows 1,2,6 give the equations
\[
x_1=0~~x_2=0~~x_3=1
\]
which has solution $\bar{x}=(0,0,1)$ that satisfies the other 3 
inequalities. Therefore $(0,0,1)$ is a vertex of $cube.ine$.
The set of rows $C=\{1,2,6\}$ are called \textit{cobasic indices}
and form a \textit{cobasis}.
The complementary set of rows $B=\{3,4,5\}$are called \textit{basic indices}
and form a \textit{basis}. Since bases are in 1-1 correspondence with
co-bases we tend to use the terms interchangeably. By definition, every
vertex has a basis. In polyhedral computation the number of rows is usually
much larger than the number of columns, so printing out the cobasis
is usually shorter than printing the basis. 
There are many options in \lrs (see \href{https://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/man/man1/lrs.1.html}{manual}) and most of these
are placed after the end statement. 
In \lrs adding the
\printcobasis option following the \End line does just this.
So for example:
\\
\href{https://ym28-it.github.io/lrs-web-app/lrs-common.html?mode=hybrid&version=v7.3&test=cube.ine}{(run)}
\bv
mayumi% lrs cube.ine
printcobasis
V-representation
begin
***** 4 rational
V#1 R#0 B#1 h=0 facets  4 5 6 I#3 det= 1 in_det= 1 z= 1 
 1  1  1  1 
V#2 R#0 B#2 h=1 facets  1 5 6 I#3 det= 1 in_det= 1 z= 1 
 1  0  1  1 
V#3 R#0 B#3 h=1 facets  2 4 6 I#3 det= 1 in_det= 1 z= 1 
 1  1  0  1 
V#4 R#0 B#4 h=2 facets  1 2 6 I#3 det= 1 in_det= 1 z= 1 
 1  0  0  1 
V#5 R#0 B#5 h=1 facets  3 4 5 I#3 det= 1 in_det= 1 z= 1 
 1  1  1  0 
V#6 R#0 B#6 h=2 facets  1 3 5 I#3 det= 1 in_det= 1 z= 1 
 1  0  1  0 
V#7 R#0 B#7 h=2 facets  2 3 4 I#3 det= 1 in_det= 1 z= 1 
 1  1  0  0 
V#8 R#0 B#8 h=3 facets  1 2 3 I#3 det= 1 in_det= 1 z= 1 
 1  0  0  0 
end
*Totals: vertices=8 rays=0 bases=8 integer_vertices=8  max_vertex_depth=3
\end{Verbatim}
Before each vertex is a line giving its cobasis as a list of facet
indices. The cobasis we use above is B\#4. The cube has the property
that the number of vertices is equal to the number of bases, making
it a \textit{simplicial} polyhedron. Things are not also so nice.

The next example is an inverted pyramid with \Hr

\includegraphics[width=1.8\textwidth]{figs/pyr.eps}

We see from the figure it has 5 vertices. If we run \lrs with the \printcobasis option we get:
\\
\href{https://ym28-it.github.io/lrs-web-app/lrs-common.html?mode=hybrid&version=v7.3&test=pyr.ine}{(run)}

\bv
mayumi% lrs pyr.ine
V-representation
begin
***** 4 rational
V#1 R#0 B#1 h=0 facets  3 4 5 I#3 det= 1 in_det= 1 z= 1 
 1 -1 -1  0 
V#2 R#0 B#2 h=1 facets  1 4 5 I#3 det= 1 in_det= 1 z= 1 
 1  1 -1  0 
V#3 R#0 B#3 h=1 facets  2 3 5 I#3 det= 1 in_det= 1 z= 1 
 1 -1  1  0 
V#4 R#0 B#4 h=2 facets  1 2 5 I#3 det= 1 in_det= 1 z= 1 
 1  1  1  0 
V#5 R#0 B#5 h=1 facets  2 3 4 I#4 det= 2 in_det= 2 z= 1 
 1  0  0 -1 
end
*Totals: vertices=5 rays=0 bases=6 integer_vertices=5  max_vertex_depth=2
\end{Verbatim}
However this time we see in the *Totals
that \lrs found 6 bases. Note that the top
of the pyramid has 4 vertices, each the intersection of 3 facets,
so each vertex has a unique basis.
However the apex $(0,0,-1)$ is the intersection of 4 facets
and any 3 of these define it. So it has in fact 4 bases representing it.
The normal output of \lrs lists each vertex once even if it is
represented by more than one basis.
To get \lrs to print all bases it discovers we insert additionally
the \allbases option and now get:
\\
\href{https://ym28-it.github.io/lrs-web-app/lrs-common.html?mode=hybrid&version=v7.3&test=pyr1.ine}{(run)}

\bv
mayumi% lrs pyr1.ine
V-representation
begin
***** 4 rational
V#1 R#0 B#1 h=0 facets  3 4 5 I#3 det= 1 in_det= 1 z= 1
 1 -1 -1  0
V#2 R#0 B#2 h=1 facets  1 4 5 I#3 det= 1 in_det= 1 z= 1 
 1  1 -1  0 
V#3 R#0 B#3 h=1 facets  2 3 5 I#3 det= 1 in_det= 1 z= 1 
 1 -1  1  0 
V#4 R#0 B#4 h=2 facets  1 2 5 I#3 det= 1 in_det= 1 z= 1 
 1  1  1  0 
V#5 R#0 B#5 h=1 facets  2 3 4 I#4 det= 2 in_det= 2 z= 1
 1  0  0 -1
V#6 R#0 B#6 h=2 facets  1 2 4 I#4 det= 2 in_det= 2 z= 1 
 1  0  0 -1 
end
*Note! Duplicate vertices/rays may be present
*Totals: vertices=6 rays=0 bases=6 integer_vertices=5  max_vertex_depth=2
\end{Verbatim}
The apex is now printed twice giving two of the four bases
that represents it. What about the other two bases?
\lrs avoids generating these vertices by enumerating only a subset
of all bases, those known as \textit{lexicographically positive}.
This is an important topic and will be treated in the
Excursion on lexicography.

If a vertex can be represented by more than one basis it is called
\textit{degenerate}. Degeneracy can be extremely high: if $m$
facets contain a single vertex in $R^d$ then it could have as many
as $\binom{m}{d}$ bases. Obviously we only need to find one of basis
for each vertex, but no-one has a good way of doing this. For
algorithms like reverse search that generate vertices by generating
bases, high degeneracy is indeed the villain. Solutions involve
using large scale parallelization, as in the \mplrs wrapper for \lrs
or using a completely different method, such as the \textit{double
description method} discussed in another Excursion. Finally we
note that a \Vr may be degenerate also and this is discussed in
\hyperref[ex:vo]{Excursion \ref{ex:vo}}
 
\hyperlink{contents}{List of Excursions}

\newpage
\section{Unbounded polyhedra, cuts and metrics}
\label{ex:up}
If we delete the inequality $x_3 \le 1$ from the unit cube
we get
an unbounded polyhedron which is the cube with
its "top" cap removed. 
$cube2.ine$ is the \Hr:
\bv
mai6% lrs cube2.ine
H-representation
begin
5 4 rational
 0  1  0  0
 0  0  1  0
 0  0  0  1
 1 -1  0  0
 1  0 -1  0
end
printcobasis
\end{Verbatim}
Computing the \Vr with the \printcobasis option
(see \hyperref[ex:bc]{Excursion \ref{ex:bc}}) we get:
\\
\href{https://ym28-it.github.io/lrs-web-app/lrs-common.html?mode=hybrid&version=v7.3&test=cube2.ine}{(run)}

\bv
mai6% lrs cube2.ine
printcobasis
V-representation
begin
***** 4 rational
V#1 R#0 B#1 h=0 facets  3 4 5 I#3 det= 1 in_det= 1 z= 1 
 1  1  1  0 
V#1 R#1 B#1 h=0 facets  3* 4 5 I#2 det= 1 in_det= 1 z= 1 
 0  0  0  1 
V#2 R#1 B#2 h=1 facets  1 3 5 I#3 det= 1 in_det= 1 z= 1 
 1  0  1  0 
V#3 R#1 B#3 h=1 facets  2 3 4 I#3 det= 1 in_det= 1 z= 1 
 1  1  0  0 
V#4 R#1 B#4 h=2 facets  1 2 3 I#3 det= 1 in_det= 1 z= 1 
 1  0  0  0 
end
*Totals: vertices=4 rays=1 bases=4 integer_vertices=4  max_vertex_depth=2 vertices+rays=5
\end{Verbatim}
We now have the 4 vertices of the cube on the $x_3=0$ plane plus the
extreme ray, indicated by a zero in the first column, (0,0,1).
Any point in $cube2$ can be expressed as a convex combination of the
4 vertices plus a non-negative scale of (0,0,1). Turning to the
cobasis listing, the 4 vertices are expressed as the intersection
of 3 input inequalities satisfied as equations,
as we saw in \hyperref[ex:bc]{Excursion \ref{ex:bc}}. The extreme ray 
is output as:

\bv
V#1 R#1 B#1 h=0 facets  3* 4 5 I#2 det= 1 in_det= 1 z= 1
 0  0  0  1 
\end{Verbatim}

This indicates that it
can be
expressed as the intersection of inequalities 4 and 5 satisfied
as equations, ie $x_1 = 1$ and $x_2=1$, and bounded by inequality 3
(indicated by 3* ), ie. $x_3 \ge 0$. The extreme ray follows
the vertex to which it is attached in the output listing.
Note that the extreme ray could also have been expressed as the intersection
of $x_1=1, x_2=0$, or  $x_1=0, x_2=0$ or $x_1=0, x_2=1$. There are
4 parallel rays in the geometric figure. \lrs with the \geometric
option will list all the geometric rays.
\\
\href{https://ym28-it.github.io/lrs-web-app/lrs-common.html?mode=hybrid&version=v7.3&test=cube2a.ine}{(run)}

\bv
mai6% lrs cube2a.ine
printcobasis
*geometric
V-representation
begin
***** 4 rational
V#1 R#0 B#1 h=0 facets  3 4 5 I#3 det= 1 in_det= 1 z= 1 
 1  1  1  0 
V#1 R#1 B#1 h=0 facets  3* 4 5 I#2 det= 1 in_det= 1 z= 1 
 0  0  0  1 
V#2 R#1 B#2 h=1 facets  1 3 5 I#3 det= 1 in_det= 1 z= 1 
 1  0  1  0 
V#2 R#2 B#2 h=1 facets  1 3* 5 I#2 det= 1 in_det= 1 z= 1 
 0  0  0  1 
V#3 R#2 B#3 h=1 facets  2 3 4 I#3 det= 1 in_det= 1 z= 1 
 1  1  0  0 
V#3 R#3 B#3 h=1 facets  2 3* 4 I#2 det= 1 in_det= 1 z= 1 
 0  0  0  1 
V#4 R#3 B#4 h=2 facets  1 2 3 I#3 det= 1 in_det= 1 z= 1 
 1  0  0  0 
V#4 R#4 B#4 h=2 facets  1 2 3* I#2 det= 1 in_det= 1 z= 1 
 0  0  0  1 
end
*Note! Duplicate rays may be present
*Totals: vertices=4 rays=4 bases=4 integer_vertices=4  max_vertex_depth=2 vertices+rays=8
\end{Verbatim}
In the output there are 4 parallel geometric rays, all with direction (0,0,1)
and following the vertex to which they are attached. \lrs will normally
not report parallel rays and gives a message when this is a possibility.

An important case of an unbounded polyhedra are cones. 
Here the $b$ vector is all zeroes.
An important example relates to finite metrics which can be viewed
as weighted complete graphs $K_n$ whose edge weights satisfy the triangle
inequality. Specifically, let the edge weights of $K_n$
be represented by variables $x_{ij},1 \le i < j \le n$.
Given $1 \le i < j < k \le n$ the triangle 
inequality can be written
\[
x_{ik} - x_{ij} - x_{ik} \le 0.
\] 
$K_n$ gives us a set of $3~\binom{n}{3}$ triangle inequalities which
define the
metric cone $m_n$. For $n=4$ we have 12 triangle inequalities:

\bv
mai6% cat m4.ine
H-representation
begin
12 7 rational
 0 -1  1  0  1  0  0
 0  1 -1  0  1  0  0
 0  1  1  0 -1  0  0
 0 -1  0  1  0  1  0
 0  1  0 -1  0  1  0
 0  1  0  1  0 -1  0
 0  0 -1  1  0  0  1
 0  0  1 -1  0  0  1
 0  0  1  1  0  0 -1
 0  0  0  0 -1  1  1
 0  0  0  0  1 -1  1
 0  0  0  0  1  1 -1
end
\end{Verbatim}

Let us find the \Vr:
\\
\href{https://ym28-it.github.io/lrs-web-app/lrs-common.html?mode=hybrid&version=v7.3&test=m4.ine}{(run)}

\bv
mai6% lrs m4.ine
*Input taken from  m4.ine
V-representation
begin
***** 7 rational
 1  0  0  0  0  0  0 
 0  1  0  0  1  1  0 
 0  0  0  1  0  1  1 
 0  0  1  0  1  0  1 
 0  1  1  0  0  1  1 
 0  1  1  1  0  0  0 
 0  0  1  1  1  1  0 
 0  1  0  1  1  0  1 
end
*Totals: vertices=1 rays=7 bases=10 integer_vertices=1  max_vertex_depth=1 vertices+rays=8
\end{Verbatim}

The output indicates one vertex, the origin, and 7 other lines indicating
extreme rays. Note that these are all 0/1 vectors so we can interpret them
as subgraphs of $K_n$. The first ray indicates the star $K_{1,3}$ and
the fourth ray indicates the bipartite graph $K_{2,2}$. In fact
the output consists of all cuts in $K_n$ and is known as the
cut cone. For $n \le 4$ the cut cone and metric cones are identical,
but this is not the case for $n \ge 5$. 
For example, for $n=5$, $m5.ine$ contains all cut vectors in
$K_5$ plus and additional class of extreme rays. 
\\
\href{https://ym28-it.github.io/lrs-web-app/lrs-common.html?mode=hybrid&version=v7.3&test=m5.ine}{(run)}

\bv
mai6% lrs m5.ine
*Input taken from  m5.ine
V-representation
begin
***** 11 rational
 0  0  1  0  0  1  0  0  1  1  0
 0  1  1  1  0  0  0  1  0  1  1
 0  1  1  2  1  2  1  2  1  2  1
.....
end
*Totals: vertices=1 rays=25 bases=573 integer_vertices=1  max_vertex_depth=8 vertices+rays=26
\end{Verbatim}

We can turn the cut cone into the cut polytope by changing the $b$
vector to all ones, converting extreme rays
into extreme points. Similarly we can obtain the metric
polytope from the metric cone. For $n=4$
the \Vr of the cut polytope is denoted $cp4.ext$ and its \Hr can
be computed by \lrs:
\\
\href{https://ym28-it.github.io/lrs-web-app/lrs-common.html?mode=hybrid&version=v7.3&test=cp4.ext}{(run)}

\bv
mai6% lrs cp4.ext 
H-representation
begin
***** 7 rational
 2 -1 -1  0 -1  0  0 
 2  0 -1 -1  0  0 -1 
 2 -1  0 -1  0 -1  0 
 2  0  0  0 -1 -1 -1 
 0  0 -1  1  0  0  1 
........
 0  1  1  0 -1  0  0 
end
*Totals: facets=16 bases=4 max_facet_depth=1
\end{Verbatim} 
In addition to the 12 triangle inequalities defining $c4$ we
find 4 new triangle inequalities. This is also the \Hr of
the metric polytope $mp4$.

You are invited to investigate
these two cones in directories ../ine/metric and ../ext/cut in
the \lrslib distribution. The essential reference for cuts and 
metrics is Deza and Laurent's \href{https://convexoptimization.com/TOOLS/cutbook.pdf}{Geometry of Cuts and Metrics}.

\hyperlink{contents}{List of Excursions}

\newpage
\section{Linearities and the travelling salesman}

\label{ex:ts}

In \hyperref[ex:hw]{Excursion \ref{ex:hw}} we noted that equations can be used in an \Hr
as well as inequalities. Of course any equation can be expressed as
two inequalities but there are various reasons why it is better
to express them explicitly. Returning to the cube, we can
consider the system:
\[
0 \le x_i \le 1,\qquad i=1,2 \qquad x_3=1 
\]
In \lrs format the input file $lcube.ine$ can be written:
\bv
lcube
H-representation
linearity 1 5
begin
5 4 rational
 0  1  0  0
 0  0  1  0
 1 -1  0  0
 1  0 -1  0
 1  0  0 -1
end
\end{Verbatim}
The first 4 input rows give the inequalities and the fifth gives the 
equation. Applying \lrs to compute a \Vr :
\\
\href{https://ym28-it.github.io/lrs-web-app/lrs-common.html?mode=hybrid&version=v7.3&test=lcube.ine}{(run)}

\bv
lg% lrs lcube.ine
V-representation
begin
***** 4 rational
 1  1  1  1 
 1  0  1  1 
 1  1  0  1 
 1  0  0  1 
end
\end{Verbatim}

The output gives the 4 vertices of a square located on the plane
$x_3=1$.

For another simple example consider the line
$x_1 + x_2 =1$
represented by the \Hr $line.ine$:

\bv
line
H-representation
linearity 1 1
begin
1 3 integer
1 -1 -1
end
\end{Verbatim}

We compute the \Vr:
\\
\href{https://ym28-it.github.io/lrs-web-app/lrs-common.html?mode=hybrid&version=v7.3&test=line.ine}{(run)}
\bv
line
V-representation
linearity 1  1
begin
***** 3 rational
 0 -1  1 
 1  1  0 
end
\end{Verbatim}

Now we have a linearity in a \Vr which describes the line as  
\[
(x_1,x_2)=(1,0) + \lambda (-1,1),\qquad   \lambda \in R^1.
\]

Next we we turn to the travelling salesman problem.
If we have four cities labelled $1..4$ then there are three tours:
12341, 13241, 12431. 

\includegraphics[width=.8\textwidth]{figs/tsp4.eps}

Using variables
$x_{ij}, 1 \le i<j \le 4$ these can be coded as 0/1 vectors of length 6.
In \lrs format we have the \Vr $tsp4.ext$ :
\bv
tsp4
V-representation
begin
3 7 integer
1 1 0 1 1 0 1
1 1 1 0 0 1 1
1 0 1 1 1 1 0
end
\end{Verbatim}
What is the \Hr?
\\
\href{https://ym28-it.github.io/lrs-web-app/lrs-common.html?mode=hybrid&version=v7.3&test=tsp4.ext}{(run)}

\bv
lg% lrs tsp4.ext
H-representation
linearity 4  1 2 3 4
begin
***** 7 rational
-2  1  1  1  0  0  0 
-2  1  1  0  1  0  0 
 0  0 -1  0  0  1  0 
 0 -1  0  0  0  0  1 
 1 -1  0  0  0  0  0 
-1  1  1  0  0  0  0 
 1  0 -1  0  0  0  0 
end
*Totals: facets=3 bases=1 linearities=4 facets+linearities=7 max_facet_depth=0
\end{Verbatim}
The output contains 4 linearities which (up to row operations) are
equivalent to the degree constraints
indicating that a tour must use two edges for each city:
\[
x_{12}+x_{13}+x_{14}=2 \qquad x_{12}+x_{23}+x_{24}=2 \qquad
x_{13}+x_{23}+x_{34}=2 \qquad x_{14}+x_{24}+x_{34}=2 .
\]
The \Hr is rounded out by the three inequalities:
\[
\qquad x_{12} \le 1 \qquad x_{12}+x_{13} \ge 1 \qquad x_{13} \le 1 
\]
These seem surprisingly unsymmetrical given the symmetry of the problem.
This is due to the linearities. Indeed if we subtract the first
linearity from the first inequality we get the
equivalent inequality $x_{13}+x_{14} \ge 1$. If we subtract the second
linearity we get $x_{23}+x_{24} \ge 1$. 
This illustrates a problem created by linearities:
the \Hr is not unique. To get a unique \Hr we need to
use the linearities to remove variables from the problem. 
Adding the \extract option to the \Hr $tsp4.ine$ and running \lrs:
\\
\href{https://ym28-it.github.io/lrs-web-app/lrs-common.html?mode=hybrid&version=v7.3&test=tsp4a.ine}{(run)}

\bv
lg% lrs tsp4a.ine
*switching to extract mode
*extract 0  
*extract col order: 1 2 3 4 5 6 
H-representation
begin
3 3 rational
 1 -1  0 
-1  1  1 
 1  0 -1 
end
*columns retained: 0 1 2
\end{Verbatim}
\lrs has eliminated one variable for each linearity. The user
can specify which ones to eliminate but the default is to eliminate
from the highest column index to the lowest. The output shows that
the \Hr of $tsp4$ in terms of variables $x_{12}$ and $x_{13}$ is
\[
x_{12} \le 1 \qquad x_{12}+x_{13} \ge 1 \qquad x_{13} \le 1 \qquad
\]
plus the above displayed 4 linearities.

We should caution that the \extract option does not necessarily give
a minimum representation as an \Hr may contain hidden, ie. not explicitly
stated, inequalities. This is the subject of 
\hyperref[ex:hl]{Excursion \ref{ex:hl}}.

To delve deeper into the travelling salesman problem there is nowhere
better than \href{https://www.math.uwaterloo.ca/tsp/}{Bill Cook's home page}.

\hyperlink{contents}{List of Excursions}

\newpage
\section{Volume, triangulations, more cuts and metrics}
\label{ex:vo}

Computing the \href{https://people.inf.ethz.ch/fukudak/polyfaq/node26.html}{volume} of a polytope is a notoriously difficult problem.
One way to do this if you have a \Vr is to use \lrs with the \volume
option. Adding this to $cube.ext$ we obtain the additional output line
\bv
*Volume=1 
\end{Verbatim} 
as expected. To see how \lrs computes the volume we need to return
to the topic of bases and cobases introduced
in \hyperref[ex:bc]{Excursion \ref{ex:bc}}. Let us insert the 
\volume, \printcobasis and \allbases options to $cube.ext$.
getting $cube1.ext$
We now get output:
\\
\href{https://ym28-it.github.io/lrs-web-app/lrs-common.html?mode=hybrid&version=v7.3&test=cube1.ext}{(run)}


\bv
mayumi% lrs cube1.ext
lrs:lrslib_v.7.3_2023.12.7(64bit,lrslong.h,hybrid_arithmetic)
*Input taken from  cube1.ext
cube
begin
***** 4 rational
F#0 B#1 h=0 vertices/rays  2 4 6 7 I#8 det= 1 in_det= 1 z= 1 
F#1 B#1 h=0 vertices/rays  2 4 6 7* I#4 det= 1 in_det= 1 z= 1 
 1 -1  0  0 
F#1 B#2 h=1 vertices/rays  4 6 7 8 I#8 det= 1 in_det= 1 z= 1 
F#2 B#2 h=1 vertices/rays  4 6 7* 8 I#4 det= 1 in_det= 1 z= 1 
 1 -1  0  0 
F#3 B#2 h=1 vertices/rays  4* 6 7 8 I#4 det= 1 in_det= 1 z= 1 
 1  0  0 -1 
F#4 B#2 h=1 vertices/rays  4 6* 7 8 I#4 det= 1 in_det= 1 z= 1 
 1  0 -1  0 
F#4 B#3 h=1 vertices/rays  2 3 4 7 I#8 det= 1 in_det= 1 z= 1 
F#5 B#3 h=1 vertices/rays  2* 3 4 7 I#4 det= 1 in_det= 1 z= 1 
 1  0 -1  0 
F#6 B#3 h=1 vertices/rays  2 3 4 7* I#4 det= 1 in_det= 1 z= 1 
 0  0  0  1 
F#6 B#4 h=1 vertices/rays  2 5 6 7 I#8 det= 1 in_det= 1 z= 1 
F#7 B#4 h=1 vertices/rays  2* 5 6 7 I#4 det= 1 in_det= 1 z= 1 
 1  0  0 -1 
F#8 B#4 h=1 vertices/rays  2 5 6 7* I#4 det= 1 in_det= 1 z= 1 
 0  0  1  0 
F#8 B#5 h=2 vertices/rays  2 3 5 7 I#8 det= 1 in_det= 1 z= 1 
F#9 B#5 h=2 vertices/rays  2* 3 5 7 I#4 det= 1 in_det= 1 z= 1 
 0  1  0  0 
F#9 B#6 h=3 vertices/rays  1 2 3 5 I#8 det= 1 in_det= 1 z= 1 
F#10 B#6 h=3 vertices/rays  1 2* 3 5 I#4 det= 1 in_det= 1 z= 1 
 0  1  0  0 
F#11 B#6 h=3 vertices/rays  1 2 3 5* I#4 det= 1 in_det= 1 z= 1 
 0  0  0  1 
F#12 B#6 h=3 vertices/rays  1 2 3* 5 I#4 det= 1 in_det= 1 z= 1 
 0  0  1  0 
end 
*Volume=1 
*Totals: facets=12 bases=6 max_facet_depth=3
\end{Verbatim}
Each new basis is accompanied by a list of $d+1=4$ indices representing
vertices in the input file. To be a cobasis these vertices are affinely
independent representing a simplex. The full set of 6 cobases decomposes
the cube into 6 simplices:
\bv
2 4 6 7,  4 6 7 8,  2 3 4 7, 2 5 6 7,  2 3 5 7,  1 2 3 5 
\end{Verbatim}
as shown in the figure.

\includegraphics[width=.8\textwidth]{figs/cube_tri.eps}

On each cobasis line printed we find "in\_det=1" which
indicates the determinant of the current basis matrix. This
determinant is $d!$ times the volume of the simplex.
Since \lrs has computes the decomposition of the cube into
simplices the sum of the 6 determinants divided by $3!$ gives
the volume of 1. A general discussion of the theory behind
this can be found \href{https://cgm.cs.mcgill.ca/~avis/doc/avis/Av98a.pdf}{here}.
 
We can also obtain a triangulation of the surface of the polyhedron from
the \printcobasis listing. We see that the first cobasis 2 4 6 7 
generates the facet F\#1, 1 -1 0 0, ie. $x_1 \le 1$, with cobasis
2 4 6 7*.
Deleting the starred index 7*
we see that F\#1 is spanned by the vertices 
on rows 2,4,6 of the input $cube1.ext$, ie. (1,0,0),  
(1,1,0) and (1,0,1).
when index 7* is deleted.
The second cobasis 4 6 7 8
generates 3 facets with cobases 4 6 8, 4 7 8, 6 7 8.

In the full
output each of the 6 facets of the cube appears twice corresponding 
to two triangles:
\bv
2 4 6, 4 6 8, 6 7 8, 4 7 8, 3 4 7, 2 3 4
5 6 7, 2 5 6, 3 5 7, 1 3 5, 1 2 3, 1 2 5
\end{Verbatim}
Together these 12 triangles
triangulate the boundary
of the cube, as can be verified in the figure. 

The repetition of facets in the \allbases listing is
how degeneracy appears in a \Vr. In a non-degenerate \Vr each facet
is a simplex and appears once. Such a polyhedron is called \textit{simplicial}.
The triangulation produced by \lrs corresponds to a deformation of the 
cube into a simplicial polytope. Note that this is the analog of
the cobases generated in an \Hr to \Vr computation corresponding to
the vertices of a simple polytope, after deformation in case of degeneracy.

As an example using volumes we return to
the cut and metric polyhedra we met in \hyperref[ex:up]{Excursion \ref{ex:up}}. 
As we noted,
the extreme points of the cut polytope $cp5.ext$ are a 
subset of those of the metric polytope $mp5.ext$. So we may wonder
how much bigger the latter is? We can compute the volume of each
by including the \volume option:
\\
$mp5$: 
\href{https://ym28-it.github.io/lrs-web-app/lrs-common.html?mode=hybrid&version=v7.3&test=mp5.ext}{(run)}
$~~~~~~~~~cp5$:
\href{https://ym28-it.github.io/lrs-web-app/lrs-common.html?mode=hybrid&version=v7.3&test=cp5.ext}{(run)}


\bv
mai6% lrs mp5.ext
*volume
H-representation
begin
***** 11 rational
 0  0  0  0  0  0  0  0  1 -1  1 
 0  0 -1  1  0  0  0  0  1  0  0 
.......
 0  0  0  0  0  0  1  1  0  0 -1 
 0  1 -1  0  0  1  0  0  0  0  0 
end 
*Volume=4/1701 
*Totals: facets=40 bases=14108 max_facet_depth=12

mai6% lrs cp5.ext
*volume
H-representation
begin
***** 11 rational
 2  0  0  0  0  0  0  0 -1 -1 -1 
 2  0  0  0  0  0 -1 -1  0  0 -1 
.......
 2 -1 -1  0  0 -1  0  0  0  0  0 
 6 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
end 
*Volume=32/14175 
*Totals: facets=56 bases=124 max_facet_depth=4
\end{Verbatim}
We can calculate that cp5 has volume 96\% of the metric polytope
mp5. In general, optimizing over the cut polytope, the max-cut problem,
is NP-hard whereas it can be done by linear programming in polynomial
time over the metric polytope (since the \Hr has a cubic number of
inequalities). 
%Goemans and Williamson have shown that a semidefinite
%programming relaxation wraps the cut polytope even more closely
%(see, eg, \href{https://convexoptimization.com/TOOLS/cutbook.pdf}{Deza and Laurent}).

\hyperlink{contents}{List of Excursions}

\newpage
\section{Redundancy is bad and how to get rid of it: redund mode}
\label{ex:re}
In \hyperref[ex:up]{Excursion \ref{ex:up}} we discovered the metric cone which gives all the
distances, known as semi-metrics, on a give finite set. Most people
learn that distances are non-negative and satisfy the triangle inequalities.
However we did not specify non-negativity in the \Hr $m4.ine$. Let
us do this getting $m4n.ine$. It just requires us to append an identity matrix.
\bv
lg% cat m4n.ine
m4
H-representation
begin
18 7 rational
 0 -1  1  0  1  0  0
 0  1 -1  0  1  0  0
.....
 0  0  0  0  1 -1  1
 0  0  0  0  1  1 -1
 0  1  0  0  0  0  0
 0  0  1  0  0  0  0
 0  0  0  1  0  0  0
 0  0  0  0  1  0  0
 0  0  0  0  0  1  0
 0  0  0  0  0  0  1
end
\end{Verbatim}
When we run \lrs we obtain the same \Vr as we did with $m4.ine$:
\\
\href{https://ym28-it.github.io/lrs-web-app/lrs-common.html?mode=hybrid&version=v7.3&test=m4n.ine}{(run)}

\bv
lg% lrs m4n.ine
V-representation
begin
***** 7 rational
 1  0  0  0  0  0  0 
 0  1  1  1  0  0  0 
 0  0  1  1  1  1  0 
 0  1  0  0  1  1  0 
 0  0  1  0  1  0  1 
 0  1  0  1  1  0  1 
 0  0  0  1  0  1  1 
 0  1  1  0  0  1  1 
end
*Totals: vertices=1 rays=7 bases=68 integer_vertices=1  max_vertex_depth=3 vertices+rays=8
\end{Verbatim}
This indicates that the  non-negative inequalities are \href{https://people.inf.ethz.ch/fukudak/polyfaq/node24.html}{redundant}, ie.
they can be deleted without changing the output.
However there is a big difference in the length of two calculations.
The Totals line we obtained in \hyperref[ex:up]{Excursion \ref{ex:up}} when running \lrs on $m4.ine$ was:
\bv
*Totals: vertices=1 rays=7 bases=10 integer_vertices=1  max_vertex_depth=1 vertices+rays=8
\end{Verbatim}
This has the same number of vertices and rays, but bases=10 versus
bases=68 for the redundant representation $m4n.ine$.
Methods like \lrs enumerate bases and the running time is
proportionate to their number (see Excursion X on degeneracy).
So the running time increases by a factor of about 7. This is a tiny
problem, but if we look at the same Totals for $m5.ine$ and
$m5n.ine$ we get respectively:
\bv
lg% lrs m5.ine
.......
*Totals: vertices=1 rays=25 bases=573 integer_vertices=1  max_vertex_depth=8 vertices+rays=26

lg% lrs m5n.ine
......
*Totals: vertices=1 rays=25 bases=5197 integer_vertices=1  max_vertex_depth=10 vertices+rays=26
\end{Verbatim}
Now 9 times as many bases are enumerated, so things are getting worse.
Clearly it is important for large problems to eliminate any redundancy
before doing the \lrs run. This can be achieved by using the program
\redund in the \lrslib distribution, or adding a \redund option
after at the end of the input file. The format of the option is

\redund i j

which checks lines $i,~i+1,~...,~j$ in the input file for redundancy, and
removes any redundant ones giving a new \Hr. Without specifying $i$ and
$j$
the entire input file is checked. After inserting \redund at the end
of the input file $m4n.ine$ we obtain $m4nr.ine$ and running \lrs :
\\
\href{https://ym28-it.github.io/lrs-web-app/lrs-common.html?mode=hybrid&version=v7.3&test=m4nr.ine}{(run)}

\bv
lg% lrs m4nr.ine
*switching to redund mode
*redund  1 18
*checking for redundant rows only
H-representation
begin
12 7 rational
 0 -1  1  0  1  0  0 
 0  1 -1  0  1  0  0 
..............
 0  0  0  0  1 -1  1 
 0  0  0  0  1  1 -1 
end
*input had 18 rows and 7 columns
* 6 redundant row(s) found
 13 14 15 16 17 18
*no check for hidden linearities
\end{Verbatim}
This is the original \Hr $m4.ine$ and this output can be
piped back into \lrs to obtain the \Vr $m4.ext$.

\bv
lg% lrs m4nr.ine |lrs
V-representation
begin
***** 7 rational
 1  0  0  0  0  0  0 
 0  1  0  0  1  1  0 
 0  0  0  1  0  1  1 
 0  0  1  0  1  0  1 
 0  1  1  0  0  1  1 
 0  1  1  1  0  0  0 
 0  0  1  1  1  1  0 
 0  1  0  1  1  0  1 
end
*Totals: vertices=1 rays=7 bases=10 integer_vertices=1  max_vertex_depth=1 vertices+rays=8
\end{Verbatim}
Note that only 10 bases are enumerated in the second step, as expected.
The message about "hidden linearities" will be discussed in
Excursion Y.

A more general form of the \redund command is 

\redundl $k ~~~  i_1~ i_2~ ... ~i_k$

which instructs \lrs to
check the $k$ input line numbers with indices $i_1~ i_2~ ...~ i_k$ and remove
any redundant lines. 

In general checking redundancy is much faster than
computing an \Hr to \Vr conversion, so if there is any doubt redundancy
should be eliminated.

Adding \redund or \redundl options to an input file
puts \lrs into \redund mode. If \redund is a link to \lrs then

\bv
mai6% redund filename
\end{Verbatim}

performs the same function as adding \redund as an option.

\hyperlink{contents}{List of Excursions}

\newpage
\section{Hidden linearities and minimum representations:minrep mode}
\label{ex:hl}

Although it is best to specify linearities directly in the input file
they may appear implicitly in an \Hr by having an inequality and its
negation. For example, $cube4.ine$ is $cube.ine$ with the negation
of the first row, ie.$x_1 \le 0$ added as a 7th inequality. Together
the make the linearity $x_1=0$. However if we do a redund check by
adding the \redund option and running \lrs we get:
\\
\href{https://ym28-it.github.io/lrs-web-app/lrs-common.html?mode=hybrid&version=v7.3&test=cube4.ine}{(run)}

\bv
mayumi% lrs cube4.ine
*redund  1 7
*checking for redundant rows only
H-representation
begin
6 4 rational
 0  1  0  0 
 0  0  1  0 
 0  0  0  1 
 1  0 -1  0 
 1  0  0 -1 
 0 -1  0  0 
end
*input had 7 rows and 4 columns
* 1 redundant row(s) found
 4
*no check for hidden linearities
\end{Verbatim}
\lrs has eliminated the now redundant $x_1 \le 1$ but did not locate
the hidden linearity. This is because the (legacy) operation of \redund
does not look for them! To do this it is necessary to insert a new
(from \lrs v.7.3) option \testlin~ {\em before} the \Begin line.
\\
\href{https://ym28-it.github.io/lrs-web-app/lrs-common.html?mode=hybrid&version=v7.3&test=cube4.ine}{(run)}

\bv
mayumi% lrs cube4.ine
*testlin
*redund  1 7
*hidden linearities exist
H-representation
linearity 1 1
begin
5 4 rational
 0  1  0  0 
 0  0  1  0 
 0  0  0  1 
 1  0 -1  0 
 1  0  0 -1 
end
*input had 7 rows and 4 columns
* 2 redundant row(s) found
 4 7
* 1 hidden linearity found
*minimum representation : dimension=2
\end{Verbatim}

In this case \lrs first performs an LP to determine if hidden
linearities exist. If so, each input line is first checked 
to see if it is redundant and if so it is eliminated. If it is not
redundant a second LP is used to check if it is a linearity.
If so the two inequalities are replaced by a single linearity.
At the end of the run all linearities are printed first, after
eliminating any linearly dependent ones. 
Since the remaining rows do not contain linearities or redundancies,
the output is minimum in terms of the number of rows in the \Hr.
A minimum representation can greatly speed up an \Hr to \Vr conversion
or a projection (see \hyperref[ex:pr]{Excursion \ref{ex:pr}}) 
and so is highly recommended.

In the presence of other  linearities, even explicit ones, hidden
linearities can be hard to find. For example, can you find
a hidden linearity in this input derived from $tsp4.ine$ that
we encountered in \hyperref[ex:ts]{Excursion \ref{ex:ts}}?

\bv
tsp4b
testlin
H-representation
linearity 4  1 2 3 4
begin
8 7 rational
-2  1  1  1  0  0  0 
-2  1  1  0  1  0  0 
 0  0 -1  0  0  1  0 
 0 -1  0  0  0  0  1 

-1  0  1  1  0  0  0 
-1  1  1  0  0  0  0 
-1  0 -1  0  0  1  1
 1  0 -1  0  0  0  0 
end
redund
\end{Verbatim}
We label the variables as edges of $K_4$ as before.
If you subtract the first linearity (row 1) to the first inequality
(row 5) you obtain 1 -1  0  0  0  0  0 corresponding to the
inequality 
$x_1 \le 1$. Similarly if you add the third and fourth 
linearities from row 7 you get -1 1  0  0  0  0, or $x_1 \ge 1$.
Hence the hidden linearity $x_{12}=1$ exists in the input file.
Running \lrs in \minrep mode we get the same result:
\\
\href{https://ym28-it.github.io/lrs-web-app/lrs-common.html?mode=hybrid&version=v7.3&test=tsp4b.ine}{(run)}

\bv
tsp4b
*testlin
*hidden linearities exist
H-representation
linearity 5 1 2 3 4 5
begin
7 7 rational
-2  1  1  1  0  0  0 
-2  1  1  0  1  0  0 
 0  0 -1  0  0  1  0 
 0 -1  0  0  0  0  1 
-1  0  1  1  0  0  0 

-1  1  1  0  0  0  0 
 1  0 -1  0  0  0  0 
end
*input had 8 rows and 7 columns
* 1 redundant row(s) found
 7
* 1 hidden linearity found
\end{Verbatim}
The new inequality is obtained from the original row 5 and
is $x_{13}+x_{14}=1$ which is equivalent to $x_{12}=1$.


To just find out if an \Hr or \Vr contains hidden linearities
one can just add the \testlin option but not the \redund option
to the input file.
Adding \testlin and \redund inequalities to an input file
puts \lrs into \minrep mode. If \minrep is a link to \lrs then

\bv
mai6% minrep filename
\end{Verbatim}

performs the same functions without the need for options.

\hyperlink{contents}{List of Excursions}
\newpage
\section{Projections, Fourier-Motkin elimination: fel mode}
\label{ex:pr}
An important operation in manipulating polyhedra is projection
to lower dimensions. \lrs projects a polyhedron $P$ onto a
subset of its variables by use of either the \project or \eliminate
options. The former option has the form:

 \project  $k$  $~~~ i_1~i_2~...~i_k$  

This asks for the projection of the polyhedron onto the $k$ variables
corresponding to columns $i_1 .. i_k$ 
Column indices are between 1 and $n-1$ and column zero is automatically
retained. Alternatively we can specify which columns to eliminate:

 \eliminate  $k$  $~~~ i_1~i_2~...~i_k$     

This eliminates $k$ variables
corresponding to columns $i_1 .. i_k$ by projection onto the remaining
variables. They are eliminated in the order given. 

These computations are easy for a \Vr but potentially very difficult
problem for an \Hr. For a \Vr it is a matter of extracting the
required columns and then removing redundancy. 
Adding \project 2  1 3
to $cube.ext$ we obtain $cube7.ext$ and running:
\\
\href{https://ym28-it.github.io/lrs-web-app/lrs-common.html?mode=hybrid&version=v7.3&test=cube7.ext}{(run)}


\bv
mayumi% lrs cube.ext
*switching to fel mode
*project 2  1 3
*removing redundant rows
V-representation
begin
4 3 rational
 1  1  1
 1  0  1
 1  1  0
 1  0  0
end
*columns retained: 0 1 3
\end{Verbatim}
These are the 4 vertices of the unit square.
There is no search for hidden linearities, so if this is required
the input file should be pre-processed or post-processed in \minrep
mode, described in \hyperref[ex:hl]{Excursion \ref{ex:hl}}.

Given an \Hr the projection problem is considerably more complicated.
\lrs solves this by using the Fourier-Motzkin elimination method.

Variables not contained in the list are eliminated using a
heuristic which chooses the column which minimizes the product of the
number of positive and negative entries.  Redundancy is removed after
each iteration using linear programming.
Adding \project 2  1 3 to modification of $cube.ine$ we obtain
$cube6.ine$
\bv
mayumi% cat cube6.ine
cube6
H-representation
begin
7 4 rational
 0  1  0  0 
 0  0  1  0 
 0  0  0  1 
 1 -1  0  0 
 1  0 -1  0 
 1  0  0 -1 
-1  0  0  1 
end
project 2 1 3
\end{Verbatim}
and doing a \lrs run we obtain:
\\
\href{https://ym28-it.github.io/lrs-web-app/lrs-common.html?mode=hybrid&version=v7.3&test=cube6.ine}{(run)}


\bv
cube6
*switching to fel mode
*project 2  1 3 
*after removing column 2
*checking for redundant rows only
H-representation
begin
4 3 rational
 0  1  0 
 1 -1  0 
 1  0 -1 
-1  0  1 
end

*original vars remaining: 1 3
\end{Verbatim}

Note that the input has a hidden linearity in lines 6 and 7,
so the output is $0 \le x_1 \le 1,~x_2=1$.
A similar result is
produced by the option \eliminate 1 2.
The output as a valid lrs input file. 

It is preferable to remove any hidden linearities and redundancy
before projection by 
pre-processing the input file in \minrep
mode, as described in \hyperref[ex:hl]{Excursion \ref{ex:hl}}.
Using preprocessing
and a pipe we get:

\bv
mayumi% minrep cube5.ine | lrs    
*hidden linearities exist
*finding minimum representation
H-representation
linearity 1 1
begin
3 3 rational
 1  0 -1 
 0  1  0 
 1 -1  0 
end
*input had 4 rows and 3 columns
* 1 redundant row(s) found
 4
* 1 hidden linearity found
\end{Verbatim}

Projection is a useful operation for combinatorial polytopes.
We saw in \hyperref[ex:up]{Excursion \ref{ex:up}}
that all extreme rays of the metric cone $m4.ine$ can be expressed
by 0/1 vectors, but this  is not the case for $m5.ine$. If we
project out any variable, corresponding to an edge $e$ in $K_5$, 
from $m5.ine$ we get the metric cone for
the graph $K_5 \setminus e$. This can be computed by inserting
\eliminate 1 1 to the input file getting $m5e.ine$ and running \lrs to get:
\\
\href{https://ym28-it.github.io/lrs-web-app/lrs-common.html?mode=hybrid&version=v7.3&test=m5e.ine}{(run)}

\bv
*switching to fel mode
*eliminate 1  1 
*after removing column 1
*checking for redundant rows only
H-representation
begin
21 10 rational
 0 -1  1  0  0  0  0  1  0  0 
 0  1 -1  0  0  0  0  1  0  0 
 0  1  1  0  0  0  0 -1  0  0 
..................
 0  0  0  0  0  0  0 -1  1  1 
 0  0  0  0  0  0  0  1 -1  1 
 0  0  0  0  0  0  0  1  1 -1 
end

*original vars remaining: 2 3 4 5 6 7 8 9 10
\end{Verbatim}
Applying \lrs again we see that all extreme rays are 0/1 valued.
This can be done in one step by use of a pipe:
\\
\href{https://ym28-it.github.io/lrs-web-app/lrs-common.html?mode=hybrid&version=v7.3&test=m5.ine}{(run)}

\bv
mayumi% lrs m5.ine | lrs
V-representation
begin
***** 10 rational
 1  0  0  0  0  0  0  0  0  0 
 0  1  0  0  1  0  0  1  1  0 
 0  0  0  1  0  0  1  0  1  1 
 0  1  1  0  0  0  1  0  1  1 
 0  1  1  1  0  0  0  0  0  0 
 0  0  1  1  1  0  0  1  1  0 
 0  0  0  1  1  1  0  0  1  1 
 0  0  1  0  0  1  0  1  0  1 
 0  1  1  0  1  1  0  0  1  1 
 0  1  0  1  0  1  0  1  0  1 
 0  0  0  0  1  1  1  0  0  0 
 0  1  0  0  0  1  1  1  1  0 
 0  0  1  1  0  1  1  1  1  0 
 0  0  1  0  1  0  1  1  0  1 
 0  1  0  1  1  0  1  1  0  1 
end
*Totals: vertices=1 rays=14 bases=100 integer_vertices=1  max_vertex_depth=2 vertices+rays=15
\end{Verbatim}
The observant reader will have noticed that these extreme rays are 
cut vectors and that the cut set with vertices $\{1,2\}$ is missing.
This is because it gives a redundant
cut vector, being the sum of cut vectors generated by the sets $\{1\}$ $\{2\}$. 
In fact a theorem of Barahona and Mahjoub says that the metric
cone of any graph without a $K_5$ minor is the same as its cut cone.
See, e.g.,  Deza and Laurent's \href{https://convexoptimization.com/TOOLS/cutbook.pdf}{Geometry of Cuts and Metrics}.


In closing we should remark that once hidden linearities have been
removed from the input file new ones cannot appear during the 
Fourier-Motzkin elimination process. This follows from a simple dimensionality
argument.


\hyperlink{contents}{List of Excursions}

\section{More projections, the golden square}
\label{ex:pr2}


\begin{wrapfigure}{r}{0.5\textwidth}
\[
\xymatrix{
P_H \ar[r] \ar[d]_{\pi} & P_V \ar[d]^{\pi} \ar[l]<1.0ex> \\
Q_H \ar[r] & Q_V \ar[l]<1.0ex>
}
\]
\end{wrapfigure}
We saw in
\hyperref[ex:pr]{Excursion \ref{ex:pr}}
that it is generally much easier to project a \Vr than to project
an \Hr. We can make use of this fact to produce a projection of
an \Hr without using Fourier-Motzkin elimination. Let $P_H$ 
be an \Hr of a polyhedron $P$. Suppose a projection
map $\pi$ projects $P$ onto $Q$. Fourier-Motzkin elimination directly
computes $Q_H = \pi(P_H)$. However, as shown in the golden square
to the right, one
could first convert $P_H$ into its \Vr $P_V$, compute $Q_V=\pi(P_V)$
and finally compute $Q_H$ from $Q_V$. The first and third operations
are \lrs mode computations. The success of this method depends on
doing these more efficiently that the Fourier-Motzkin elimination
computation.

As an example of when this second method is very effective we
consider projecting $rc150.ine$ onto its first three coordinates.
This example is a randomly generated polyhedron and provides a
difficult case for Fourier-Motzkin elimination. This is because
if we start with $n$ inequalities and the input coefficients are
positive or negative with probability 1/2, then we create about
$n^2/4$ inequalities for which we need to do redundancy removal.
These polyhedra have little or no degeneracy since they are randomly
generated, which is the easy case for \lrs. Using the second approach
it takes less than a second to compute $Q_H$, which has 342 facets.
A direct approach with  Fourier-Motzkin elimination took 3176 seconds.

As an example where the first approach wins, consider computing the
vertices of the metric polytope of the 7-wheel 
\begin{wrapfigure}{r}{0.3\textwidth}
\includegraphics[width=0.3\textwidth]{figs/w7.eps}
\end{wrapfigure}
(center vertex 1 attached to
each vertex of a cycle of length 6). We start with $mp7.ine$, the metric
polytope of $K_7$ and project onto the 12 edges of the wheel.
Using our usual vertex labelling this is the projection \\
$\project~12~~~1~2~3~4~5~6~7~11~12~16~19~21$ \\
The run in \fel mode takes less than a second giving the output
$w7.ine$ with 56 facets. 
\\
\href{https://ym28-it.github.io/lrs-web-app/lrs-common.html?mode=hybrid&version=v7.3&test=mp7.ine}{(run)}

Computing its vertices w7.ext also takes less
than a second.
\\
\href{https://ym28-it.github.io/lrs-web-app/lrs-common.html?mode=hybrid&version=v7.3&test=w7.ine}{(run)}

We see that, as predicted by the Barahouna-Mahjoub
theorem (see \hyperref[ex:pr]{Excursion \ref{ex:pr}}), 
they are precisely the 64 cut vectors of the 7-wheel.
Computing the \Vr of $mp7.ine$ directly is an extremely long computation.


\hyperlink{contents}{List of Excursions}

\section{Integer hull, more fun with cuts, metrics and the TSP}
\label{ex:ih}

under construction

\hyperlink{contents}{List of Excursions}
\printindex
\end{document}
