ilp.tex 1.73 KB
 msurl committed May 22, 2020 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 committed Jun 03, 2020 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.  msurl committed May 22, 2020 15 16 \\ \\  msurl committed Jun 03, 2020 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)  msurl committed May 22, 2020 21 22 23  \pagebreak