% Template article for preprint document class `elsart'
% SP 2001/01/05

% Modified 2007/01/09 for CTW 2010
% Please find the original file at http://www.elsevier.com/

\documentclass{ctwart}

% Use the option doublespacing or reviewcopy to obtain double line spacing
% \documentclass[doublespacing]{elsart}

% if you use PostScript figures in your article
% use the graphics package for simple commands
% \usepackage{graphics}
% or use the graphicx package for more complicated commands
% \usepackage{graphicx}
% or use the epsfig package if you prefer to use the old commands
\usepackage{epsfig}

% The amssymb package provides various useful mathematical symbols
\usepackage{amssymb}

% \usepackage{mathptmx}
% \usepackage{pstricks,pst-text,pst-node}
% \usepackage{epsfig,color}
 %\usepackage{amsmath,amsthm,amssymb}

  \newtheorem{example}{Example}
 \newtheorem{theorem}{Theorem}
 \newtheorem{lemma}{Lemma}
% \newtheorem{claim}{Claim}
 \newtheorem{observation}{Observation}
 \newtheorem{definition}{Definition}

\def\cL{{\mathcal L}}
\def\cF{{\mathcal F}}
\def\cD{{\mathcal D}}
\def\R{{\mathbb R}}
\def\P{{\mathbb P}}
\def\eq{{\quad\Longleftrightarrow\quad}}

\begin{document}
\setcounter{page}{55}
\begin{frontmatter}

% Title, authors and addresses

% use the thanksref command within \title, \author or \address for footnotes;
% use the corauthref command within \author for corresponding author footnotes;
% use the ead command for the email address,
% and the form \ead[url] for the home page:
% \title{Title\thanksref{label1}}
% \thanks[label1]{}
% \author{Name\corauthref{cor1}\thanksref{label2}}
% \ead{email address}
% \ead[url]{home page}
% \thanks[label2]{}
% \corauth[cor1]{}
% \address{Address\thanksref{label3}}
% \thanks[label3]{}

\title{Lattice Polyhedra and Submodular Flows}

% use optional labels to link authors explicitly to addresses:
% \author[label1,label2]{}
% \address[label1]{}
% \address[label2]{}

\author{Satoru Fujishige and Britta Peis}

\address{}

\begin{keyword}
distributive lattices \sep Edmonds-Giles polyhedra \sep submodularity
% keywords here, in the form: keyword \sep keyword
\end{keyword}

\end{frontmatter}

\small{
Lattice polyhedra were introduced by Hoffman and Schwartz as a common framework for various
discrete optimization problems. They are specified by a ternary matrix whose row set forms a 
\emph{consecutive, supermodular} lattice and some submodular rank function (the terms ``sub''-and ``supermodular'' can also be interchanged).
Though lattice polyhedra are known to be integral, so far no combinatorial algorithm could have been found for the corresponding
linear optimization problem.
We show that the important class of distributive lattice polyhedra in which the underlying lattice is both, sub-and supermodular can be reduced to Edmonds-Giles polyhedra. Thus, submodular flow algorithms can be applied to this class of lattice polyhedra.}


\section{Introduction}

A large class of discrete optimization problems allow a formulation as integer linear program with underlying ternary matrix: given a matrix $A\in \{-1,0,1\}^{L\times E}$, some weight function $w\in \R^E$, lower and upper bounds $c,d\in \R^E$ and 
some ``rank'' function $f\in \R^L$ find
an integral solution of 
$$(LP)\quad\max_{x\in \R^E}\{w^Tx \mid Ax\le f,~ c\le x\le d\}.$$

This problem is easily seen to be $\mathcal{NP}$-hard even if restricted to binary matrices. Therefore, we are looking for more special structures of the polyhedron
$$\P(A,f)=\{x\in \R^E\mid Ax\le f,~ c\le x\le d\}.$$
A promising class %%are
is that of 
\emph{lattice polyhedra} which were introduced by Hoffman and Schwartz~\cite{HS78}
and shown to be integral. The name comes from a certain, very general, lattice structure on $A$
on which $f$ is submodular.


\begin{definition}[Lattice polyhedra]\label{d.latticePolyhedra}
Let $A\in\{-1,0,1\}^{L\times E}$  be a matrix with entries $\chi(i,e)$ for $i\in L$ and $e\in E$, and let
$c,d\in \R^E$ and $f\in \R^L$. Then
the polyhedron
$$\P(A,f)=\{x\in \R^E\mid Ax\le f,~ c\le x\le d\}$$
is called a \emph{lattice polyhedron} if the row index set $L$ forms 
a  lattice $L=(L,\preceq, \wedge, \vee)$ on which 
$f$ is submodular, i.e., $f$ satisfies
$$f(i)+f(j) \ge f(i\wedge j) + f(i\vee j) \quad\forall i,j\in L,$$
and where for all $i,j,k\in L$ and all $e\in E$ %%holds
the following three hold:
\begin{itemize}
\item[{\rm (C1)}] if $i\prec j\prec k$ and $\chi(i,e)=\chi(k,e)=t\neq 0$, then $\chi(j,e)=t$,
\item[{\rm (C2)}] if $i\prec j$, then $\chi(i,e)\cdot \chi(j,e) \ge 0,$ and
\item[{\rm (C3)}] $\chi(i,e) + \chi(j,e) \le \chi(i \vee j,e) + \chi(i \wedge j,e)$.
\end{itemize}
\end{definition}

Analogously, if, in the above definition, function $f$ is supermodular and
(C3) is replaced by
\begin{itemize}
\item[{\rm (C3${}'$)}] $\chi(i,e) + \chi(j,e) \ge \chi(i \vee j,e) + \chi(i \wedge j,e)$,
\end{itemize}
the polyhedron
$$\P'(A,f)=\{x\in \R^E\mid Ax\ge f,~ c\le x\le d\}$$
is also called a lattice polyhedron.
The lattice $L$ is called \emph{consecutive} if properties (C1) and (C2) are satisfied.
If $L$ satisfies (C3) (or (C$3'$)), we call it \emph{supermodular} (or \emph{submodular}).

Lattice polyhedra 
 form a common framework for various combinatorial structures 
%%like, for example, 
such as polymatroids, the intersection of polymatroids, and Edmonds-Giles polyhedra. 
Several min-max results for combinatorial structures can be derived from 
the following theorem:

\begin{theorem}[\cite{HS78}, \cite{Hoffman}]
If $f,c$ and $d$ are integral, then
all vertices of lattice polyhedra are integral.
\end{theorem}

However, this integrality result is only a structural existence theorem without algorithmic foundation.
While several greedy-type algorithms have been developed for special instances of lattice polyhedra in the last decades
(see e.g.\ \cite{frank}, \cite {FP08}, \cite{FK1}, \cite{FK2}, \cite{K}, \cite{Edmonds}, \cite{QST}, \cite{DH}, up to now no combinatorial algorithm
could have been found for lattice polyhedra in its general form, even if the polyhedra are restricted to binary matrices.

\medskip
A very important class of lattice polyhedra %%are 
is that of %%so-called 
\emph{distributive lattice polyhedra}, in which 
the lattice $(L,\preceq,\wedge, \vee)$ is distributive and (C3) is satisfied with equality.

%\section{Distributive lattice polyhedra}\label{sec.DLP}
Let us first recall some basic facts about distributive lattices:
A lattice $(L,\preceq,\wedge,\vee)$ is called \emph{distributive} if the binary operators $\wedge, \vee$ satisfy the
distributive laws. Alternatively, distributive lattices can be characterized by the exclusion
of the sublattices $N_5$ and $M_3$.
By a theorem of Birkhoff,
a distributive lattice $L$ is isomorphic to the lattice $\cD(P)$ of all ideals\footnote{A subset $I\subseteq P$ is an \emph{ideal} of poset $(P,\preceq)$ if $i\preceq j$ and $j\in P$ implies $i\in P$} of poset $(P,\preceq)$ 
on the set $P$ of 
join-irreducible elements\footnote{An element $i\in L$ is \emph{join-irreducible} if $i=j\vee k$ implies
$i=j$ or $i=k$}  of $L$.
(For more details about lattices the reader is referred to \cite{birkhoff}.)

Beside classical examples of combinatorial structures such as polymatroids, the intersection of polymatroids, or submodular systems, distributive lattice polyhedra also cover Edmonds-Giles polyhedra (see below).
Furthermore, 
we show  in Theorem~\ref{obs.1} below that
a large class of lattice polyhedra is in fact distributive.
Finally, we show in Theorem~\ref{t1} that distributive lattice polyhedra can in fact be reduced to Edmonds-Giles polyhedra for which several efficient algorithms exist.


\begin{theorem}\label{obs.1}
Let $\P(A,f)$ be a lattice polyhedron in which any two rows of $A$ are distinct and property
(C3) is satisfied with equality. Then the underlying lattice
$(L,\preceq, \wedge, \vee)$ is distributive.
\end{theorem}

{\bf Proof:}
For the sake of contradiction, assume that $L$ is not distributive, i.e., that it contains %%either 
an $N_5$- or an $M_3$-sublattice.
Then there exist five distinct elements 
%%$\{i,j,k,l,m\}\subseteq L$
$i,j,k,l,m\in L$ such that
$$l=i\wedge j= i\wedge k\quad\mbox{and}\quad m=i\vee j= i\vee k.$$
Since $\chi(j)\neq \chi(k)$ by the assumption, 
choose some element $e\in E$ with $\chi(j,e)\neq \chi(k,e)$.
Since (C3) is satisfied with equality, it follows that
$$\chi(l,e)+\chi(m,e)=\chi(i,e)+\chi(j,e)=\chi(i,e)+\chi(k,e),$$
%%implying the contradiction $\chi(j,e)=\chi(k,e)$.
which implies $\chi(j,e)=\chi(k,e)$, a contradiction.
\qed












\paragraph*{Edmonds-Giles polyhedra.}
Let $G=(V,E)$ be a connected 
directed graph and
$\cF\subseteq 2^V$ be a ring family of subsets of vertex set $V$, (i.e., $\cF$ is  union-and intersection-closed).
Given a submodular function $f:\cF\to \R$ and lower and upper bounds on the edges
$c,d:E\to \R$, the Edmonds-Giles polyhedron is
$$\P(G,\cF,f)=\{x\in \R^E\mid x(\Delta^+(S))-x(\Delta^-(S)) \le r(S)~\forall S\in \cF, c\le x\le d\},$$
where $\Delta^+(S)$ and $\Delta^-(S)$ denote, respectively, the sets of arcs
leaving $S$ and of entering $S$.
(In the original definition, $\cF$ is a crossing family on which $f$ is crossing submodular.
However, it suffices to consider the case of ring families with submodular $f$, as the more general crossing case can be reduced to it using the Dilworth truncation (see e.g.~\cite{Fuj}).)
Edmonds and Giles~\cite{EG77} proved that $\P(G,\cF,f)$ is integral, 
and several algorithms  for the corresponding
linear optimization problem, called the \emph{submodular flow problem}, have been established (see e.g., the survey paper~\cite{FI}. Almost all submodular flow algorithms are based on generalizations of  different min-cost-flow algorithms).

Also Edmonds-Giles polyhedra turn out to be  distributive lattice polyhedra:
given an Edmonds-Giles polyhedron $\P(G,\cF,f)$ consider the collection of ordered pairs
$$L=\{(\Delta^+(S),\Delta^-(S))\mid S\in \cF\}\subseteq 3^E$$
partially ordered by
$$(\Delta^+(S),\Delta^-(S))\preceq (\Delta^+(T),\Delta^-(T)) \iff S\subseteq T$$
and with join- and meet-operations
\begin{eqnarray*}
(\Delta^+(S),\Delta^-(S)) \vee (\Delta^+(S),\Delta^-(S)) &=& (\Delta^+(S\cup T),\Delta^-(S\cup T))\\
 (\Delta^+(S),\Delta^-(S)) \wedge (\Delta^+(T),\Delta^-(T)) &=& (\Delta^+(S\cap T),\Delta^-(S\cap T)).
\end{eqnarray*}
Also for all $S\subseteq V$ and $e\in E$ define 
\[\chi(S,e)=\left\lbrace 
\begin{array}{rl}
 1   & e\in \Delta^+(S)\\
 -1  & e\in \Delta^-(S)\\
0 &  \mbox{otherwise}
\end{array}
\right.
\]
Then $(L,\preceq,\wedge,\vee)$ with such a $\chi$ 
is a consecutive, sub- and supermodular lattice.




While it seems that the Edmonds-Giles polyhedra form a special class of distributive lattice polyhedra, we
will see that they are in fact equivalent, i.e., we show that any distributive lattice polyhedron can be reduced
to some Edmonds-Giles polyhedron.
For this, we
construct an auxiliary digraph $G$ whose vertices correspond to the join-irreducible
elements  $P$ of $L$ and whose edges correspond to the elements in $E$.
We then show that the lattice polyhedron is equivalent to the Edmonds-Giles polyhedron
$\P(G,\cD(P), f),$ i.e., we show (in the appendix)

\begin{theorem}\label{t1}
If $\P(A,f)$ is a distributive lattice polyhedron, then there exists an auxilary digraph $G=(P,E)$ whose vertices correspond to the join-irreducible elements of $L$ such that 
\begin{eqnarray*}
 \P(A, f)&=&\{x\in \R^{E'}\mid \forall I\in \cD(P): x(\Delta^+(I))-x(\Delta^-(I))\le f(I),~c\le x\le d\}\\
         &=& \P(G,\mathcal{D}(P),f)
\end{eqnarray*}
\end{theorem}







\begin{thebibliography}{00}

% \bibitem{label}
% Text of bibliographic item

% notes:
% \bibitem{label} \note

% subbibitems:
% \begin{subbibitems}{label}
% \bibitem{label1}
% \bibitem{label2}
% If there is a note, it should come last:
% \bibitem{label3} \note
% \end{subbibitems}



\bibitem[B91]{birkhoff}
G.Birkhoff:
{\sl Lattice Theory}.
Amer.\ Math.\ Soc.\ {\bf 91} (1991).

\bibitem[DH03]{DH}
B.L. Dietrich and A.J. Hoffman:
{\sl On greedy algorithms, partially ordered sets, and submodular functions}.
IBM J. Res. \& Dev. 47 (2003), 25-30.

\bibitem[E70]{Edmonds}
J. Edmonds: {\sl Submodular functions, matroids, and certain
polyhedra}, in: {\sl Combinatorial Structures and Their
Applications}, R. Guy \emph{et al.} eds., Gordon and Breach, New
York, 1970, 69-87.

\bibitem[FK96]{FK1}
U. Faigle and W. Kern: {\sl Submodular linear programs on forests}.
Math. Programming 72 (1996), 195-206.

\bibitem[FK00]{FK2}
U. Faigle and W. Kern: {\sl On the core of ordered submodular cost
games}. Math. Programming 87 (2000), 483-489.

% \bibitem{FK3}
% U. Faigle and W. Kern: {\sl An order-theoretic framework for the
% greedy algorithm with applications to the core and Weber set of
% cooperative games}. Order 17 (2000), 353-375.

\bibitem[FP08]{FP08}
U.Faigle and B. Peis, \emph{Two-phase greedy algorithms for some classes of combinatorial linear programs}, In SODA,
2008, 161-166.


\bibitem{[F99]frank}
A. Frank: {\sl Increasing the rooted-connectivity of a digraph by
one}. Math. Programming 84 (1999), 565-576.


\bibitem[H82]{Hoffman}
A.J. Hoffman:
{\sl Ordered sets and linear programming}.
In: Ordered Sets (editor: I. Rival), D. Reidel Publishing company (1982), 619-654.

\bibitem[HS78]{HS78}
A.~Hoffman and D.E. Schwartz, \emph{On lattice polyhedra}, Proceedings of Fifth
  Hungarian Combinatorial Coll. (A.~Hajnal and V.T. Sos, eds.), North-Holland,
  Amsterdam, 1978, pp.~593--598.



\bibitem[EG77]{EG77}
J. Edmonds and R. Giles:
{\sl A min-max relation for submodular functions on graphs}.
Ann. Discrete Math., {\bf 1} (1977), 185-204.

\bibitem[FI00]{FI}
S. Fujishige and S. Iwata: 
{\sl Algorithms for submodular flows}.
Special Issue on Algorithm Engineering: Surveys.
IEICE Transactions  on Informations  and Systems, Vol.E83-D, No.3 (2000).

\bibitem[Fuj91]{Fuj}
S. Fujishige:
{\sl Submodular Functions and Optimization}.
Annals of Discrete Math., {\bf 47}, (1991).

\bibitem{K}
U. Kr\"uger: {\sl Structural aspects of ordered polymatroids}.
Discr. Appl. Math. 99 (2000), 125-148.


\bibitem{QST}
M. Queyranne, F. Spieksma, and F. Tardella: {\sl A general class of
greedily solvable linear programs}. Math. Oper. Res. 23 (1998),
892-908.

\end{thebibliography}








% \begin{example}(Model in~\cite{DH})
% todo
% \end{example}
% 
% \begin{example}(Model in~\cite{QST} )
% todo
% \end{example}



% The Appendices part is started with the command \appendix;
% appendix sections are then done as normal sections
% \appendix

% \section{}
% \label{}


\end{document}

