% 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{amsmath}
\usepackage{mathrsfs}
\usepackage{url}
\newcommand{\transpose}[1]{{#1}^{\top}}

\begin{document}
\setcounter{page}{21}
\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{On the convergence of feasibility based bounds
  tightening}\thanks{Financial support by grants System@tic ``EDONA'',
  ANR 07-JCJC-0151 ``Ars'', ANR 08-SEGI-023 ``Asopt'', Digiteo
  Emergence ``Paso'' is gratefully acknowledged.}

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

\author{Pietro Belotti}
\ead{\url{belotti@lehigh.edu}}
\address{Dept.~of Industrial and Systems Engineering, Lehigh
  University, Bethlehem, PA, USA}
\author{Sonia Cafieri}
\ead{\url{sonia.cafieri@enac.fr}}
\address{Dept.~Math\'ematiques et Informatique, ENAC, 7 av.~E.~Belin,
  31055 Toulouse, France}
\author{Jon Lee} 
\ead{\url{jonlee@us.ibm.com}}
\address{Dept.~of Mathematical Sciences, IBM T.J.~Watson Research
  Center, PO Box 218, Yorktown Heights, NY 10598, USA}
\author{Leo Liberti\corauthref{cor1}}
\ead{\url{liberti@lix.polytechnique.fr}}
\corauth[cor1]{Corresponding author.}
\address{LIX, \'Ecole Polytechnique, 91128 Palaiseau, France}

\begin{keyword}
spatial Branch-and-Bound, range reduction, lattice, fixed point, MINLP,
global optimization, constraint programming.
\end{keyword}

\end{frontmatter}

% main text
\section{Introduction}
\label{s:intro}

Global Optimization and Mixed-Integer Nonlinear Programming problems
such as $\min\{f(x)\;|\;g^L\le g(x)\le g^U\land x^L\le x\le x^U\land
\forall j\in Z\;(x_j\in\mathbb{Z})\}$, where
$f:\mathbb{R}^n\to\mathbb{R}$, $g:\mathbb{R}^n\to\mathbb{R}^m$,
$g^L,g^U\in\mathbb{R}^m$, $x^L,x,x^U\in\mathbb{R}^n$ and
$Z\subseteq\{1,\ldots,n\}$, are usually solved to
$\varepsilon$-guaranteed approximation by the spatial Branch-and-Bound
(sBB) algorithm \cite{couenne}, a variant of the usual
Branch-and-Bound for dealing with nonlinear, possibly nonconvex
$f,g$. Since the gap between the original problem $P$ and its convex
relaxation $\bar{P}$ is due both to integral variable restrictions
being lifted as well as nonconvex functions being replaced by a convex
relaxation, sBB is able to branch at continuous variables as well as
integer ones. If $\bar{x}$ solves $\bar{P}$, the standard disjunction
used at a node in the sBB search tree is $x_j\le\bar{x}_j\vee
x_j\ge\bar{x}_j$, the more usual one
$x_j\le\lfloor\bar{x}_j\rfloor\vee x_j\ge\lceil\bar{x}_j\rceil$ being
used only if $j\in Z$.

At any sBB node, it is important to make sure that the variable ranges
$x^L\le x\le x^U$ for that node are as tight as the constraint
restrictions $g^L\le g(x)\le g^U$ allow. Letting $\mathcal{F}(P)$ be
the feasible region of $P$, we would wish to replace $X^0=[x^L,x^U]$
with $\tilde{X}=[\tilde{x}^L,\tilde{x}^U]$ such that
$\tilde{x}^L_i=\min_{x\in\mathcal{F}(P)} x_i$ and
$\tilde{x}^U_i=\max_{x\in\mathcal{F}(P)} x_i$ for all $i\le n$. Since
these $2n$ problems are as hard as $P$, we relax these
requirements. There are two standards relaxations: Optimization Based
Bounds Tightening (OBBT) \cite{obbt,couenne} and Feasibility Based
Bounds Tightening (FBBT) \cite{andersen,couenne}. The former consists
in replacing $\mathcal{F}(P)$ with $\mathcal{F}(\bar{P})$. The latter,
whose convergence properties are the object of this paper, is also
known in Constraints Programming as a range reduction device. FBBT
relies on interval arithmetic to derive the constraint ranges
$\bar{G}=[\bar{g}^L,\bar{g}^U]$ implied by the variable ranges $X^0$
at a given sBB node; if $\bar{G}\supsetneq G^0=[g^L,g^U]$, FBBT uses
inverse interval arithmetic to propagate $G^0$ back to tightened
variable ranges $X'$. This basic FBBT step is iterated until
convergence, generating an interval sequence $X^0,X^1,\ldots$. Since
OBBT is usually slower than FBBT, OBBT is only applied at the root sBB
node and FBBT is applied at each node. Furthermore, to simplify
inverse interval arithmetic, FBBT often only considers a subset of
linear constraints in $g$. We shall therefore make the assumption ---
without excessive loss of generality --- that the symbol $g$ denotes
the linear constraints of $P$, which we denote as $g^L\le Ax\le g^U$
for some $m\times n$ matrix $A$.

The main trouble with FBBT is that its worst-case running time is
infinite in the size of its input $(m,n,X^0,A,G^0)$. For example, on the
instance
$(2,2,([0,1],[0,1]),({\scriptsize \begin{array}{cc}a&-1\\ [-0.8em]
    1&-a\end{array}}),([0,0],[0,0]))$, FBBT yields the infinite
interval sequence $([0,1/a^{2k-1}],[0,1/a^{2k}])$ whenever $a>1$.
Enforcing finite convergence by terminating at the first iteration $k$
such that $\mathscr{L}(X^{k-1}\triangle X^k)\le\varepsilon$, where
$\varepsilon>0$ is given and $\mathscr{L}$ is the Lebesgue measure in
$\mathbb{R}$, yields a finite but unbounded worst-case time
complexity: given a fixed iteration bound $K$ there are always
instances where the FBBT takes longer than $K$ iterations to reach the
$\varepsilon$ termination condition (it suffices to decrease the value
$a$ appropriately). In practice, such occurrences are far from rare,
specially when the coefficients of $Ax$ are obtained by previous
floating point operations, which might cause a small but positive
$|a_i-a_j|$ even if $a_i,a_j$ are supposed to be equal.

In this paper we propose a new method for finding the limit point of
the FBBT sequence in polynomial time, based solving a Linear Program
(LP) modelling the greatest fixed point of the FBBT in the interval
lattice. 

\vspace*{-0.7cm}

\section{Fixed points in the interval lattice}

\vspace*{-0.5cm}

A {\it lattice} is a set $\Lambda$ partially ordered by the relation
$\sqsubseteq$ endowed with two operations $\sqcup$ ({\it join}),
$\sqcap$ ({\it meet}) such that $x\sqsubseteq x\sqcup y$,
$y\sqsubseteq x\sqcup y$ and $x\sqcap y\sqsubseteq x$, $x\sqcap
y\sqsubseteq y$. A lattice is {\it complete} if there exist elements
$\bot,\top$ such that $\bot\sqsubseteq x\sqsubseteq \top$ for all
$x\in\Lambda$. An operator $F:\Lambda\to\Lambda$ is {\it monotone} if
$x\sqsubseteq y$ implies $F(x)\sqsubseteq f(y)$ and {\it deflationary}
if $F(x)\sqsubseteq x$ for all $x\in\Lambda$. The set of all real
intervals forms a lattice $\mathscr{I}$ under set inclusion
$\subseteq$, with set intersection $\cap$ as meet and interval union
(smallest interval including two intervals) $\cup$ as join. The
lattice structure is extended to arrays of intervals in the standard
way. In the rest of the paper, we let $X$ be the interval vector
$(X_1,\ldots,X_n)\in\mathscr{I}^n$ and
$G=(G_1,\ldots,G_m)\in\mathscr{I}^m$. 

FBBT consists of two phases: upwards and downwards propagation. We
define $\mbox{\sf up}:\mathscr{I}^n\to\mathscr{I}^m$ and $\mbox{\sf
  down}:\mathscr{I}^m\to\mathscr{I}^n$ as:
\begin{eqnarray}
  \mbox{\sf up}(X) &=& (G_i^0\cap \sum_{j\le n}a_{ij} X_j\;|\;i\le
    m) \label{upeq} \\
  \mbox{\sf down}(G)&=&\bigcap_{i\le
    m}(X_j\cap\frac{1}{a_{ij}}(G_i-\sum_{\ell\not=j}a_{i\ell}X_\ell)\;|\;j\le
    n), \label{downeq} 
\end{eqnarray}
where all arithmetic operators have interval semantics
\cite{moore2}. We now define the FBBT iteration as an operator
$\mbox{\sf fbbt}:\mathscr{I}^n\to\mathscr{I}^n$ by $\mbox{\sf
  fbbt}(X)=\mbox{\sf down}(\mbox{\sf up}(X\cap X^0))$ (we remark that
our definition of $\mbox{\sf fbbt}$ depends on the initial interval
vector $X^0$). Because all linear interval arithmetic and lattice
operators are monotone \cite{moore2} and the composition of monotone
operators is monotone \cite{roman}, $\mbox{\sf fbbt}$ is a monotone
operator. Furthermore, because of the intersections, intervals are
changed only if the $\mbox{\sf up}$ and $\mbox{\sf down}$ actions make
them smaller. Again, the composition of deflationary operators is
deflationary \cite{roman}: hence $\mbox{\sf fbbt}$ is deflationary.
By applying Thm.~12.9 in \cite{roman} to the dual lattice obtained by
inverting $\top$ and $\bot$, $\sqsubseteq$ and $\sqsupseteq$, meet and
join, we have that the sequence $(\mbox{\sf fbbt}^k(X)\;|\;k\ge 0)$
converges to the greatest fixed point (gfp) of $\mbox{\sf fbbt}$,
i.e.~the largest (in the lattice order) interval vector $X$ such that
$\mbox{\sf fbbt}(X)=X$. In other words $\mbox{gfp}(\mbox{\sf fbbt}) =
\mbox{sup}\{X\;|\;X=\mbox{\sf fbbt}(X)\}$. By Tarski's Fixed Point
Theorem \cite{tarski}, equality can be replaced with
$\subseteq$. Furthermore, the operator
$|\cdot|:\mathscr{I}^n\to\mathbb{R}$ given by $|X|=\sum_{j\le
  n}(x^U_j-x^L_j)$ is monotone with the lattice order; since the
lattice is complete, we obtain:
\begin{equation}
  \mbox{gfp}(\mbox{\sf fbbt}) =
  \mbox{argmax}\{|X|\;|\;X\subseteq\mbox{\sf fbbt}(X)\},
  \label{fpeq}
\end{equation}
which we state as the following ``interval linear problem'' with parameters
$(m,n,X^0,A,G^0)$ and interval decision variable arrays $X,G$:
\begin{equation}
  \max \{|X| \;|\; X\subseteq X^0\land G\subseteq \mbox{\sf up}(X)
    \land X \subseteq \mbox{\sf down}(G)\}, \label{fpeq1}
\end{equation}
It is possible to write an ordinary LP whose optimal solution is the
same as \eqref{fpeq1}.

\vspace*{-0.7cm}

\section{Computational validation}

\vspace*{-0.5cm}

By way of preliminary computational validation of our approach, we
solved four significant instances using CPLEX 11.0 \cite{cplex11} on
an Intel Core 2 Duo 1.4GHz with 3GB RAM running Linux. For each
instance we record the gfp, the seconds of user CPU time to solution
with either method, the absolute error $E=\sum_{j\le
  n}\mathscr{L}(X^\ast\triangle \mbox{gfp}(\mbox{\sf fbbt}))$ where
$X^\ast$ is the output of either method ($\varepsilon_{\mbox{\tiny
    FBBT}}=10^{-6}$), and the relative error $R$ of the FBBT obtained
by letting it run only for as long as the LP method takes to converge
to the (precise) gfp's. \\ [0.2em]
\hspace*{-0.5cm}\begin{minipage}{12cm}
{\scriptsize
\begin{tabular}{l||c|c|c|c} \hline
Instance & \begin{minipage}{2cm}
{\tiny
  $x_1-1.01x_2 = 0$ \\     [-0.3em] 
  $-1.01x_1+x_2= 0$ \\     [-0.3em] 
  $x_1,x_2\in[-1,1]$
}
\end{minipage} &
\begin{minipage}{2.5cm}
{\tiny
  $x_1-1.01x_2 = 1$ \\     [-0.3em] 
  $-1.01x_1+x_2= -1.01$ \\ [-0.3em] 
  $x_1,x_2\in[-1,1]$
}
\end{minipage} &
\begin{minipage}{3.5cm}
{\tiny
  $x_1-1.01x_2 = 0$ \\     [-0.3em]
  $-1.01x_1+x_2= 0$ \\     [-0.3em]
  $x_3+100x_1 \ge -100$ \\ [-0.3em]
  $x_1,x_2\in[-1,1]$, $x_3\in[-10,1]$
}
\end{minipage} &
\begin{minipage}{3.5cm}
{\tiny 
  $x_1-1.01x_2 = -1.01$ \\ [-0.3em]
  $-1.01x_1+x_2= 1$ \\     [-0.3em]
  $x_3+100x_1 \ge -100$ \\ [-0.3em]
  $x_1,x_2\in[-1,1]$, $x_3\in[-10,1]$ \\ [-1em]
}
\end{minipage} \\ \hline 
{gfp} & ([0,0],[0,0]) & ([1,1],[0,0]) &
   ([0,0],[0,0],[-10,0]) & ([0,0],[1,1],[-10,0]) \\ \hline \hline
CPU${}_{\mbox{\tiny FBBT}}$ & 0.04 & 0.04 & 0.06 & 0.06 \\ \hline
{\bf CPU${}_{\mbox{\tiny LP}}$} & {\bf 0} & {\bf 0} & {\bf 0.004} &
  {\bf 0.004} \\ \hline  \hline
$E_{\mbox{\tiny FBBT}}$ & 1e-4 & 5e-5 & 1.5e-6 & 5e-5 \\ \hline
{\bf $E_{\mbox{\tiny LP}}$} & {\bf 0} & {\bf 0} & {\bf 0} & {\bf 0}
  \\ \hline  \hline
$R_{\mbox{\tiny FBBT}}$ & 2.29 & 1.47 & 2.33 & 1.21 \\ \hline 
\end{tabular}
}
\end{minipage}

\vspace*{-0.2cm}

\bibliographystyle{plain} \bibliography{mdc}

\end{document}

