-
Notifications
You must be signed in to change notification settings - Fork 4
/
or.tex
76 lines (53 loc) · 2.21 KB
/
or.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
\documentclass[english]{../spicker}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{tabularx, multirow}
\usepackage[style=numeric, backend=bibtex]{biblatex}
\addbibresource{or.bib}
\title{Operations Research}
\author{Patrick Gustav Blaneck}
\begin{document}
\maketitle
\tableofcontents
\newpage
%\setcounter{section}{1}
\section{Linear Programming}
\begin{defi}{Linear Programming}
\emph{Linear Programming} is the problem of optimizing (maximizing or minimizing) a \emph{linear objective function} subject to a set of \emph{linear functional constraints}.
\textbf{Given:} $A \in \R^{m\times n}, b \in \R^m, c\in R^n$
\textbf{Find:} $x^* \in \R^n$ where $x^* = \arg\max\{c^Tx \mid Ax \leq b\}$
\end{defi}
\begin{bonus}{Linear Programming Solvers}
Software that solves linear programs - \emph{linear programming solvers} - also generate lots of important auxiliary information (as well as the optimum):
\begin{itemize}
\item sensitivity analysis
\item shadow prices
\item alternative optima
\item \ldots
\end{itemize}
\end{bonus}
\begin{theo}{Ellipsoid Method}
A LP of dimension $n$ can be solved in $\bigo(L^2 \cdot n^6)$ time \cite{khachiyan1979}, where $L =$ \# bits in the input.
\end{theo}
\begin{theo}{Interior Point Method}
A LP of dimension $n$ can be solved in a \emph{numerically stable} way in $\bigo(L^2 \cdot n^{3.5})$ time \cite{karmarkar1984}.
\end{theo}
\begin{defi}{Integer Linear Programs (ILP)}
\textbf{Given:} $A \in \R^{m\times n}, b \in \R^m, c\in R^n$
\textbf{Find:} $\underline{x^*\in\Z^n}$ where $x^* = \arg\max\{c^Tx \mid Ax \leq b\}$
\end{defi}
\begin{example}{Integer Linear Program for \textsc{Vertex Cover}}
\fbox{
\parbox{0.95\textwidth}{
\underline{\textsc{Vertex Cover}}
\textbf{Given:} Graph $G = (V, E)$\\
\textbf{Find:} \textsc{Vertex Cover}, i.e. $V' \subseteq V$ such that every edge has at least one endpoint in $V'$.
}
}
\textbf{Integer Linear Program:}
For $v\in V$, let $x_v \in \{0, 1\}$.
Goal: minimize $\sum_{v\in V}x_v$.
Constraints: for every edge $uv \in E$, we require $x_u + x_v \geq 1$.
\end{example}
\printbibliography
\end{document}