handout_bilevel.tex

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Programming/Coding Assignment
% LaTeX Template
%
% This template has been downloaded from:
% http://www.latextemplates.com
%
% Original author:
% Ted Pavlic (http://www.tedpavlic.com)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------------------------
%	PACKAGES AND OTHER DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------

\documentclass{article}
\usepackage{geometry}
\geometry{a4paper, top=35mm, left=35mm, right=35mm, bottom=30mm,
	headsep=10mm, footskip=12mm}
\usepackage[utf8]{inputenc} %unix-windows-compatible
\usepackage{commath}
\usepackage{fancyhdr} % Required for custom headers
\usepackage{lastpage} % Required to determine the last page for the footer
\usepackage{extramarks} % Required for headers and footers
%\usepackage[usenames,dvipsnames]{color} % Required for custom colors
\usepackage{graphicx} % Required to insert images
\usepackage{listings} % Required for insertion of code
\usepackage[section]{placeins}
\usepackage{caption} % to set figure captions in minipage
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{tikz}
\usepackage{algorithm}
\newcommand{\pushcode}[1][1]{\hskip\dimexpr#1\algorithmicindent\relax}
\usepackage[noend]{algpseudocode}

% Set up the header and footer
\pagestyle{fancy}

%\setlength\parindent{0pt} % Removes all indentation from paragraphs
\renewcommand\thesubsection{\thesection.\alph{subsection}}
\newcommand*\tageq{\refstepcounter{equation}\tag{\theequation}}


\newtheorem{mydef}{Definition}
\newtheorem{theo}{Theorem}
\newtheorem{cor}{Corollary}
%----------------------------------------------------------------------------------------
%	CODE INCLUSION CONFIGURATION
%----------------------------------------------------------------------------------------
% Default fixed font does not support bold face
\DeclareFixedFont{\ttb}{T1}{txtt}{bx}{n}{12} % for bold
\DeclareFixedFont{\ttm}{T1}{txtt}{m}{n}{12}  % for normal

\usepackage{color}
\definecolor{deepblue}{rgb}{0,0,0.5}
\definecolor{deepred}{rgb}{0.6,0,0}
\definecolor{deepgreen}{rgb}{0,0.5,0}
\lstset{language=Python, 
breaklines=true, 
tabsize=4,
basicstyle=\ttm,
otherkeywords={self},            
keywordstyle=\ttb\color{deepblue},
emph={MyClass,__init__},         
emphstyle=\ttb\color{deepred},   
stringstyle=\color{deepgreen},
frame=tb,                        
showstringspaces=false            
}% 
%\setcounter{secnumdepth}{0} % Removes default section numbers

%----------------------------------------------------------------------------------------
%	NAME AND CLASS SECTION
%----------------------------------------------------------------------------------------

\newcommand{\Title}{Enhanced Exact Algorithms for Discrete Bilevel Linear
	Problems} % Assignment title
\newcommand{\Seminar}{Seminar: Selected Topics in Bilevel Optimization} % Course/class
\newcommand{\Author}{Leon Eifler}
\newcommand{\fett}[1]{\mathbf #1}
\newcommand{\Real}{\mathbb{R}}
% Your name
%\newcommand{\ID}{327468} % Your name

\title{
	\centering
	{\huge\textbf{\Title}}\\ 
	\vspace{1cm}
	{\huge{\Seminar}\\}
	\vspace{0.6cm} 
	{\mdseries\large \Author }
	\vspace{1cm}
}


%----------------------------------------------------------------------------------------

\begin{document}
	
	\maketitle
	\vspace{1cm}
%----------------------------------------------------------------------------------------
%	TABLE OF CONTENTS
%----------------------------------------------------------------------------------------
\section{Overview}

We present the work of Caramia and Mari \cite{Caramia2015}, who introduced two new exact algorithms for solving bilevel linear problems in which all the variables are discrete. These Discrete Bilevel Linear Problems (DBLPs) can be defined as:

		\begin{alignat*}{2}
		\text{(DBLP)} \quad \min_{x,y} F(x,y) &= c_1^Tx +c_2^Ty&& \\
		\text{s.t.} \quad &Cx + Dy \le e&& \\
		&x \in \mathbb{Z}^n_+ \\
		&y \in \arg \min_y&& f(y) = d^T y \\
		&\text{s.t.} &&Ax+By \le b \\
		& &&y \in \mathbb{Z}^m_+
		\end{alignat*}
		
The first Algorithm is a cutting plane method, where each added inequality separates multiple bilevel-infeasible solutions. The second is a branch and cut method that exploits a geometric property of bilevel linear problems. 
The computational results are compared to the method proposed by DeNegre and Ralphs \cite{DeNegre2009}.
\newpage

\section{Preliminaries}

In this section, we introduce notation that we will need when discussing feasible solutions of (DBLP). 
First we define the \textit{constrained region}, where we omit integrality requirements on the variables.
\begin{equation*}
	S = \{(x,y) \ | \ x \in \mathbb{Z}^m_+, y \in \mathbb{Z}^m_+, Cx+Dy \le e, Ax + By \le b \}
\end{equation*}
For each possible value of the leader variables $x$ we define the \textit{followers feasible set}
\begin{equation*}
	\Omega_y(x) = \{y \ | \ y \in \mathbb{Z}^m_+, By \le b - Ax \}
\end{equation*}
and the set of all $y$ that minimize the followers objective, called the \textit{reaction set}
\begin{equation*}
	R_y(x) = \arg \min_y \{f(y) \ \text{s.t. } y \in \Omega_y(x).
\end{equation*}
Finally the set of all bilevel-feasible solutions, the \textit{inducible region}, is defined as
\begin{equation*}
	IR = \{(x,y) \ | \ x \in \mathbb{Z}^n_+, Cx+Dy \le e, y \in R_y(x)\}.
\end{equation*}
The relaxation that we will use to solve (DBLP) we call the Single Level linear Problem (SLP), defined as
\begin{align*}
\text{(SLP)} \quad &\min_{x,y} F(x,y) = c_1^Tx +c_2^Ty \\
&\text{s.t.} \quad (x,y) \in S.
\end{align*} 
Note that this is indeed a relaxation as every optimal solution of (SLP) is a lower bound to the optimal solution of (DBLP), since $IR \subseteq S$.

For the sake of simplicity, we assume from now on that there exist no upper-level constraints. However, both algorithms that we will present also work if there exist upper-level constraints.

\section{A cutting plane method}
\label{cp}

The basic idea of the cutting plane method can be described as follows
\begin{description}
	\item[Solve relaxation] Solve (SLP) and obtain an optimal solution $(\bar x, \bar y)$.
	If it is bilevel-feasible, then (DBLP) is solved.
	\item[Add inequality] If $(\bar x, \bar y)$ is not bilevel-feasible, add an inequality to (SLP) that cuts off all bilevel-infeasible solutions at $\bar x$. Then solve the new relaxation and repeat until (DBLP) is solved.
\end{description}

We will now give a detailed explanation of this inequality. Let $(\bar x, \bar y)$ be an optimal solution of (SLP) that is not bilevel-feasible. Then there exists a bilevel-feasible point $(\bar x, \hat y)$, such that $f(\hat y) < f(\bar y)$. Now we introduce a valid inequality that is only active at $x = \bar x$:
\begin{equation*}
		f(y) \le f(\hat y) + L \|x-\bar x\|_{\infty}.
\end{equation*}
This non-linear inequality can be reformulated as an optimization problem 
\begin{align*}
f(y) \le f(\hat y) + L \hat z, 
\end{align*}
where $\hat z$ is the optimal solution of 
\begin{align*}
(P_{\hat z}) \quad \min_{z} z \\
\text{s.t.} \quad z &\ge x_i - \bar x_i \quad i = 1,\dots,n \\
z &\ge \bar x_i - x_i \quad i = 1,\dots,n.
\end{align*}
Adding this to (SLP) turns it into a bilevel problem itself, but with continuous follower variables.
Note that bilevel problems with continuous follower variables can be transformed into a single level problem using KKT conditions, as described by Fortuny-Amat
and McCarl \cite{Fortuny-Amat1981}.
The advantage of this cutting plane method is that a large number of bilevel-infeasible solutions are cut off at each iteration. However, as each inequality adds a follower problem with $2n$ constraints the iterations are computationally expensive.

A possible modification to reduce the number of added follower problems is to remove added inequalities under certain conditions. If a bilevel-infeasible solution $(\bar x, \bar y)$ was cut off and the next bilevel-infeasible solution $(x',y')$ is far from  $(\bar x, \bar y)$ in $S$, then it is reasonable that the descent direction of the objective leads away from $(\bar x, \bar y)$.
Therefore the subproblem $P_{\bar z}$ that cut off $(\bar x, \bar y)$ is replaced by the inequality $F(x,y) \ge F(x',y')$. To avoid cycling, if $P_{\bar z}$ is reintroduced at some point, it will not be dropped again.

\section{A branch and cut algorithm}

The constrained region $S$ that is used as a relaxation to solve DBLP's usually contains a large amount of integer points that are not bilevel-feasible. The motivation behind the branch and cut algorithm presented here is to split the constrained region into two parts $S'$and $S''$, where $S'$ is likely to contain the optimal solution.
We first solve the max-min problem:
	\begin{align*}
	(BLP^{max}_{min}) \quad \max_{x,y} f(y) &= d^T y \\
	\text{s.t.} \quad &x \in \mathbb{R}^n_{+} \\
	&y \in \arg \min_{y} f(y) = d^Ty \\
	&\text{s.t.} \quad Ax + By \le b \\
	& \quad y \in \mathbb{R}^m_{+}
	\end{align*}
That means we take the maximum of the followers objective over the set of all continuous bilevel-feasible points. Let $(\hat x, \hat y)$ the the optimal solution of $BLP^{max}_{min}$. Then the inequality
\begin{equation*}
	f(y) \le \lceil f(\hat y) \rceil
\end{equation*}
is valid for bilevel linear problems. For the corresponding DBLP it might not be valid but it is likely that most discrete bilevel-feasible points fulfill $f(y) \le \lceil f(\hat y) \rceil$.
Therefore we split the constrained region $S$ into 
\begin{align*}
	S' &= \{(x,y) \in S \ | \ f(y) \le \lceil f(\hat y) \rceil \}, \\
	S'' &= \{(x,y) \in S \ | \ f(y) \ge \lceil f(\hat y) \rceil + 1\}.
\end{align*}
Then the framework for the branch and cut algorithm is the following
	\begin{itemize}
		\item[Step 0]Determine $S'$ and $S''$. Select Problem $DBLP'$, then go to Step 1.
		\item[Step 1]Set $k = 0$ and $UB$ to a sufficiently large number.
		\item[Step 2](Solve LP) Solve subproblem $k$. If subproblem $k$ is infeasible, prune the current node and
		go to Step 6, otherwise let $(x^k,y^k)$ be the optimal solution. If $F(x_k,y_k) \ge UB$ prune the current node and go to Step 6, otherwise go to Step 3.
		\item [Step 3] If $(x^k, y^k)$ is integer, go to Step 4 (bilevel-check), otherwise go to Step 5 (branching).
		\item [Step 4](Bilevel-feasiblity check) Solve the follower’s problem for $x = x_k$ and compute a bilevel–feasible solution $(x_k , \hat y_k )$. If $y_k \neq \hat y_k$, introduce a valid inequality to cut off this bilevel-infeasible solution. Otherwise,
		the solution is bilevel–feasible and if $F(x_k , y_k ) < U B$, let $U B = F(x_k , y_k )$.
		Go to Step 5.
		\item [Step 5](Branching) Select a fractional variable in the solution and use it as a branching variable. Generate two subproblems and select the next active subproblem $k$. Go to Step 2.
		\item [Step 6](Backtracking) Select a non-processed node as the next $k$ and go to Step 2.
		\item [Step 7](Consider $S''$) Compute $LB''$ for problem $(DBLP'')$ induced by $S''$. If this is lower than the $UB$ found before, stop.
		Otherwise solve $(DBLP'')$.
	\end{itemize}
	
		\begin{figure}
						\centering
			\input{inducible-handout.tikz}
			\caption{Example of splitting of $S$. Inducible region of linear problem is (A - B - C)}
		\end{figure}
Note that this is just a general framework that can be used with any cutting plane method and any branching rule. The authors use the valid inequality proposed by DeNegre and Ralphs \cite{DeNegre2009} to cut off bilevel-infeasible points in Step 4.
This general framework can be used to incorporate the cutting plane method from section 3 in a hybrid branch and cut algorithm. The authors propose to use branch and cut to solve $(DBLP')$ and then use the cutting plane method for $(DBLP'')$. In Step 7, we expect that we just have to find a decent lower bound for $(DBLP'')$ in order to prove optimality for the solution found for $(DBLP')$. The cutting plane method is efficient in finding tight lower bounds. 

\section{Computational Analysis}

The cutting plane method (CP) as well as the modified version, where used cuts are deleted, (MCP) are compared to the cutting plane method by DeNegre and Ralphs (DN\_CP).
In the same way the branch and cut algorithm (BC) as well as the hybrid variant (HBC) are compared to the branch and cut algorithm by DeNegre and Ralphs (DN\_BC).

The authors implemented all algorithms including (DN\_CP) and (DN\_BC) in C programming language and tested them on a PC Pentium Core 2 Duo with a 2 GHz processor and 1 GB RAM, with CPLEX 12.3 as the solver. 
Two sets of test instances were used: a set of random instances and a set of modified MIPLIB 2010 instances. 
The cutting plane methods need on average $90\%$ less computational time than (DN\_CP). For the branch and cut algorithms both (BC) and (HBC) were faster than (DN\_BC), where the difference in running time ranges from $-0.5\%$ to $-70.6\%$. The overall comparison on both sets can be seen in the following two diagrams. Overall, the cutting plane methods were the best-performing on all instances.


\begin{figure}[H]
	\centering
		\includegraphics[width = 0.8\textwidth]{run-times-random.pdf}
	\caption{Computational times on random set in seconds.}
\end{figure}
\begin{figure}[H]
	\centering
	\includegraphics[width = 0.8\textwidth]{run-times_miplib.pdf}
	\caption{Computational times on miplib set in seconds.}
\end{figure}
	\vspace{1cm}
	\bibliographystyle{abbrv}
	\bibliography{Bibliography}
\end{document}