Integer programming problem with m clauses prove np complete
Answers
Answered by
0
title{NP-completeness of 0-1 Integer Programming}
\author{Kurt McAlpine, 2004750}
\begin{document}
\frame{\titlepage}
\begin{frame}
\frametitle{Description}
Integer programming is defined as the following optimisation problem:
\begin{align}
max \{ c^\top x : Ax \leq b, x \in \mathbb{Z}^n\}
\end{align}
Where $A$ is an $m \times n$ integer matrix for $m,n \in \mathbb{N}$, $b \in
\mathbb{Z}^m$, $c \in \mathbb{Z}^n$\\
0-1 integer programming is a special case of integer programming where $x \in
\{0,1\}^n$
\end{frame}
\begin{frame}
\frametitle{Description}
Reformulating the integer programming optimisation problem into a decision
problem so that I can give a proof of NP-completeness.\\
``Given $A$ and $b$ does there exist an $x$ such that the following condition
is satisfied $Ax \geq b$''
\end{frame}
\begin{frame}
\frametitle{0-1 Integer Programming is in NP}
To show 0-1 integer programming is in NP we describe a Turing machine M that
can verify an instance in polynomial time.\\
$M = $``On input $(A, b, x)$\\
1. multiply matrix $A$ with vector $x$\\
2. for $i \in (1,\ldots,m)$\\
3. ~ if $(Ax)_i > b_i$ reject\\
4. accept
\author{Kurt McAlpine, 2004750}
\begin{document}
\frame{\titlepage}
\begin{frame}
\frametitle{Description}
Integer programming is defined as the following optimisation problem:
\begin{align}
max \{ c^\top x : Ax \leq b, x \in \mathbb{Z}^n\}
\end{align}
Where $A$ is an $m \times n$ integer matrix for $m,n \in \mathbb{N}$, $b \in
\mathbb{Z}^m$, $c \in \mathbb{Z}^n$\\
0-1 integer programming is a special case of integer programming where $x \in
\{0,1\}^n$
\end{frame}
\begin{frame}
\frametitle{Description}
Reformulating the integer programming optimisation problem into a decision
problem so that I can give a proof of NP-completeness.\\
``Given $A$ and $b$ does there exist an $x$ such that the following condition
is satisfied $Ax \geq b$''
\end{frame}
\begin{frame}
\frametitle{0-1 Integer Programming is in NP}
To show 0-1 integer programming is in NP we describe a Turing machine M that
can verify an instance in polynomial time.\\
$M = $``On input $(A, b, x)$\\
1. multiply matrix $A$ with vector $x$\\
2. for $i \in (1,\ldots,m)$\\
3. ~ if $(Ax)_i > b_i$ reject\\
4. accept
Similar questions