ilp.tex 1.73 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
\section{Linear Programming} \raggedbottom
Linear programming is a technique to minimize linear functions. 
A linear programm (LP) consists of a objective function, which is minimized with respect to a set of linear inequalities. \\
\\
Linear programms can be expressed as 
\[min\{c^Tx : Ax \geq b, x \geq 0\}\]
$b \in \mathbb{R}^n$ and $c \in \mathbb{R}^n$ are constant vectors. $Ax \leq b$ denotes the inequalities which have to be respected. $A \in \mathbb{R}^{m \times n}$ is a matrix containing the coefficients of the $m$ inequalities. $c^Tx \in R$ is the objective function which is minimized. 
$x \in \mathbb{R}$ is a vector describing possible solutions. If $x \in \mathbb{R}$ obeys all inequalities it is called a feasible solution. A solution $x^*$ is optimal if respects all inequalities and is minimal. 
\\
\\
Integer linear programms (ILPs) are linear programms with the additional restriction that all variables have to be integers: $x \in \mathbb{Z}$. 
The decision variant of an ILP is NP-complete.
\\
msurl's avatar
msurl committed
14
In this thesis we use a more readable notation which does not completely sticks to this definition. We write down the inequalities(and the objective function?) in a sum notation. (Maybe an example?) But it is possible to transform them into the matrix notation. 
15
16
\\
\\
msurl's avatar
msurl committed
17
18
19
20
Decision problems(combinatorical optimisation problems?/ \textbf{Decisions}. Not Decision Problems) can be modelled with ILPs. Every variable $x_i \in \{0,1\}$ denotes a possible decision(To include or not?). In our case we assign a decision variable for each vertex to decide if it is included in a dominating set or not. 
\\
\\
(Maybe to "formal". Maybe introduce the used notation right away and try to find textbook or publication which also uses this notation to cite)
21
22
23

\pagebreak