Title: Theory / Unimportant / CS / Algo / Linear and integer programming / Schrijver{ / 3 Polyhedra, linear inequalities, and linear programming
Tags: fromMath mathToDef mathToSee EquivalentButNoIntermediate addIntermediateCard equivalentHand hasSeenConjDef multipartite

Name: A cone
Definition: A subset closed under multiplication by positive numbers and closed under addition.
Page: 87
Chapter: 7
Section: 2
Variables: \(V\) a \(\mathbb Q\)-vector space.

Name: A polyhedral
Definition: The solution of \(\{x\mid Ax\le 0\}\) for some matrix \(A\).
Page: 87
Chapter: 7
Section: 2
Variables: \(V\) a \(\mathbf Q\)-vector space

Name: The cone generated by \(x_1,\dots,x_m\)
Definition: The set \(\{\sum\lambda_i x_i\mid \lambda_i\ge 0\}\).
Page: 87
Chapter: 7
Section: 2
Variables: \(V\) a \(\mathbf Q\)-vector space and \(x_1,\dots,x_m\subseteq V\).
Notation: \(\text{cone}\{x_1,\dots,x_m\}\)

Smaller0: \(C\) is polyhedral
Greater0: \(C\) is finitely generated
Page: 87
Chapter: 7
Section: 2
Variables: \(V\) a \(\mathbb Q\)-vector space
\(C\subseteq V\) a convex cone
Index: 1a
Kind: Cor
Smaller to greater: iff
Name: Farkas-Minkowski-Weyl theorem

Name: A (convex) polyhedron
Definition: \(\{x\mid Ax\le b\}\) for some matrix \(A\) and vector \(b\).
Page: 87
Chapter: 7
Section: 2
Variables: \(V\) a \(\mathbf Q\)-vector space

Smaller0: (\(Ax\ge b\) has a solution)
Greater0: (\(y\ge 0\) and \(yA=0\) implies \(yb\ge0\))
Page: 89
Chapter: 7
Section: 3
Variables: \(A\) a matrix, \(b\) a vector.
Index: 1e
Kind: Cor
Smaller to greater: iff

Smaller0: \(Ax\ge b\) has a solution \(x\ge 0\)
Greater0: \(y\ge 0\) and \(yA\ge 0\) implies \(yb\ge0\)
Page: 89
Chapter: 7
Section: 3
Variables: \(A\) a matrix, \(b\) a vector.
Index: 1e
Kind: Cor
Smaller to greater: iff
Extra: rationnel ?

Smaller0: \(\max\{cx\mid Ax\le b\} \)
Greater0: \(\min\{yb\mid y\ge0, yA=c\} \)
Page: 90
Chapter: 7
Section: 3
Variables: \(A\) a matrix
\(b,c\) vectors
Index: 1g
Kind: Cor
Smaller to greater: =
Assuming: the sets are non-empty
Name: Duality theorem of linear programming

The following problems are P-equivalent:
-\(\max\{cx\mid Ax\le b\}\), \(\min\{cx\mid Ax\ge b\}\),
-\(\max\{cx\mid x\ge 0, Ax\le b\}\), \(\min\{cx\mid x\ge0, Ax\ge b\}\),
-\(\max\{cx\mid x\ge 0, Ax= b\}\), \(\min\{cx\mid x\ge0, Ax= b\}\).
Page: 91
Chapter: 7
Section: 3
Variables: \(A\) a matrix, \(b,c\) vectors.
Index: (17)

Name: A feasible solution
Definition: A vector \(x\) such that \(Ax\le b\).
Page: 92
Chapter: 7
Section: 3
Variables: \(A\) a matrix
\(b,c\) vectors
consider the equation \(Ax\le b\)

Name: Feasible region
Definition: The set of feasible solution.
Page: 92
Chapter: 7
Section: 3
Variables: \(A\) a matrix, \(b,c\) vectors.

Name: The cost function
Definition: \(x\mapsto cx\).
Page: 92
Chapter: 7
Section: 3
Variables: \(A\) a matrix,
\(b,c\) vectors
\(\{ca\mid Ax\le b\}\) a linear programing problem
Name2: The objective function

Name: The objective value of \(x\)
Definition: \(cx\).
Page: 92
Chapter: 7
Section: 3
Variables: \(A\) a matrix,
\(A,b,c\) vectors
\(\{cx\mid Ax\le b\}\) a linear programing problem
Name2: cost value of \(x\)

Smaller0: \(Ax\le b\) is satisfiable
Greater0: there exists \(\delta'\le \delta\) such that \(cx\le \delta'\) is a nonnegative linear combination of the inequalities in the system \(Ax\le b\)
Page: 93
Chapter: 7
Section: 6
Variables: \(A\) a matrix, \(b,c\) vectors and \(\delta\) a constant
Index: 1h
Kind: Cor
Smaller1: (\(Ax\le b\) implies \(cx\le \delta\))
Connect Smaller0: and

Smaller0: \(x\in\text{cone}(X)\)
Greater0: \(x\in\text{cone}(x_1,\dots,x_d)\) for some linearly/affinely independant vectors \(x_1,\dots,x_d\in X\)
Page: 94
Chapter: 7
Variables: \(X\subseteq\mathbb R^n\)
\(x\in\mathbb R^n\)
Index: 1i
Kind: Cor
Hide middle: yes
Name: Carathéodory's theorem

Smaller0: there exists \(x\) with \(Ax<b\) and \(Bx\le c\)
Greater0: for all row vectors \(y,z\ge0\),
-\(yA+zB=0\) then \(yb+zc\ge0\) and
-\(yA+zb=0\) and \(y\ne 0\) then \(yb+zc>0\)
Page: 94
Chapter: 7
Variables: \(A,B\) matrices, \(b,c\) column vectors.
Index: 1k
Kind: Cor
Smaller to greater: iff
Name: Motzkin's transposition theorem

Smaller0: \(x_0\) and \(y_0\) are optimum solutions
Greater0: \(cx_0=y_0b\)
Page: 95
Chapter: 7
Section: 9
Variables: \(A\) a matrix,
\(b, y_0\) column vectors,
\(c,x_0\) row vectors,
\(\max\{xc\mid Ax\le b\}=\min\{yb\mid y\ge 0,yA=c\}\) an equation
Smaller to greater: iff
Assuming: Both optima are finite, \(x_0,y_0\) are feasible solutions
Name: Complementary slackness
Intermediate: if a component of \(y_0\) is positive, the corresponding inequality in \(Ax\le b\) is satisfied by \(x_0\) with equality; i.e. \(y_0(b-Ax_0)=0\)

Smaller0: the maximum has an optimum solution \(x_0\) with \(a_ix_0<\beta_i\)
Greater0: the minimum has an optimum solution \(y_0\) with positive \(i\)th component
Page: 95
Chapter: 7
Section: 9
Variables: \(A\) a matrix,
\(b\) column vectors,
\(c\) row vectors,
\(\max\{xc\mid Ax\le b\}=\min\{yb\mid y\ge 0,yA=c\}\) an equation,
\(a_ix\le \beta_i\) an inequality of \(Ax\le b\)
Smaller to greater: or
Assuming: Both optima are finite, \(x_0,y_0\) are feasible solutions

Smaller0: the positive components of \(y\)
Greater0: linearly independant rows of \(A\)
Page: 96
Chapter: 7
Section: 9
Variables: \(A\) a matrix,
\(b,y\) column vectors,
\(c\) row vector,
\(\max\{xc\mid Ax\le b\}=\min\{yb\mid y\ge 0,yA=c\}\) an equation,
Index: 11
Kind: Cor
Smaller to greater: '???
Hide middle: yes
Assuming: Both optima are finite, \(y\) a minimum

Definition: The set of arcs leaving \(W\).
Page: 96
Chapter: 7
Section: 10
Variables: \(D=(V,A)\) a directed graph,
\(r,s\in V\),
\(c:A\to\mathbb R_+\),
\(W\subseteq V\)
Notation: \(\delta^+(W)\)

Definition: The set of arcs entering \(W\).
Page: 96
Chapter: 7
Section: 10
Variables: \(D=(V,A)\) a directed graph,
\(r,s\in V\),
\(c:A\to\mathbb R_+\),
\(W\subseteq V\)
Notation: \(\delta^-(W)\)

Q: How to state in linear programming [...]:
-[...].
A: that \((x_a)_{a\in A}\) is a flow satisfying the capacitance constraint; \(0\le x_a\le c_a\) for all \(a\in A\)
Page: 97
Chapter: 7
Section: 10
Variables: \(D=(V,A)\) a directed graph,
\(c:A\to\mathbb R_+\), capacity constraint,
\((x_a)_{a\in A}\) a flow

Name: A flow in \(D\)
Definition: A family \((x_a)_{a\in A}\) such that \(\sum_{a\in \delta^-(v)}x_a=\sum_{a\in \delta^+(v)}x_a\), for all \(v\in V\setminus\{r,s\}\).
Page: 97
Chapter: 7
Section: 10
Variables: \(D=(V,A)\) a directed graph,
\(r\) a source, \(s\) a sink

Q: How to state in linear programming that [...]:
-[...]
A: \((x_a)_{a\in A}\) is a flow; \(\sum_{a\in \delta^-(v)}x_a=\sum_{a\in \delta^+(v)}x_a\)
Page: 97
Chapter: 7
Section: 10
Variables: \(D=(V,A)\) a directed graph,
\(r\) a source, \(s\) a sink,
\((x_a)_{a\in A}\)

Smaller0: the maximum value of \(r-s\)-flow subject to capacity \(c\)
Greater0: the minimum capacity of an \(r-s-cut\)
Page: 97
Chapter: 7
Section: 10
Variables: \(D=(V,A)\) a directed graph,
\(r\) a source, \(s\) a sink,
Index: 2
Kind: Theo
Smaller to greater: is equal to
Name: Max-Flow min-cut theorem

Name: An implicit equality in \(Ax\le b\)
Definition: An inequality \(ax\le \beta\) in \(Ax\le b\) such that \(ax=\beta\) for all \(x\) satisfying \(Ax\le b\).
Page: 99
Chapter: 8
Section: 1
Variables: \(Ax\le b\) a set of linear inequations,

Name: The set of implicit equalities
Page: 99
Chapter: 8
Section: 1
Variables: \(Ax\le b\) a set of linear inequations,
Notation: \(A^=x\le b^=\)

Name: The set of inequalities which are not implicit equalities
Page: 99
Chapter: 8
Section: 1
Variables: \(Ax\le b\) a set of linear inequations,
Notation: \(A^+x\le b^+\)
Index: (2)

Question: If there exists a solution, there exists a solution such that
Answer: \(A^*x=b^=, A^+x<b^+\).
Page: 99
Chapter: 8
Section: 1
Variables: \(Ax\le b\) a set of linear inequations,
Index: (3)

Name: A redundant constraint
Definition: A constraint implied by the other constraints in the system.
Page: 100
Chapter: 8
Section: 1
Variables: \(Ax\le b\) a set of linear inequations,
Index: (3)

Name: An irredundant constraint
Definition: A constraint which is not redudant.
Page: 100
Chapter: 8
Section: 1
Variables: \(Ax\le b\) a set of linear inequations,
Index: (3)

Name: The characteristic cone of \(P\)
Definition: \(x+y\in P\) for all \(x\in P\)
Page: 100
Chapter: 8
Section: 2
Variables: \(Ax\le b\) a feasible set of linear inequations,
\(P=\{x\mid Ax\le b\}\)
Index: (4), (5)(i)
Definition2: \(Ay\le 0\)
Conjdef: The set of \(y\) such that
Definition3: \(x+\lambda y\in P\)
Name2: The recession cone of \(P\)
Abbreviation: \(\text{char.cone}P\)
DefType: A cone

Question: \(P+\text{char.cone}P=\)
Answer: \(P\).
Page: 100
Chapter: 8
Section: 2
Variables: \(Ax\le b\) a feasible set of linear inequations,
\(P=\{x\mid Ax\le b\}\)
Index: (5)(ii)

Smaller0: \(P\) is bounded
Greater0: equals 0
Page: 100
Chapter: 8
Section: 2
Variables: \(P\) a nonempty polyhedron
Index: (5)(iii)
Smaller to greater: iff
Hide middle: yes
Prefix Greater: \(\text{char.cone}P\)

Question: \(\text{char.cone}(Q+C)\)
Answer: equals \(C\).
Page: 100
Chapter: 8
Section: 2
Variables: \(Q\) a polytope,
\(C\) a polyhedral cone
Index: (5)(iv)

Name: The infinite directions of \(P\)
Definition: \(\text{char.cone}P\setminus\{0\}\).
Page: 100
Chapter: 8
Section: 2
Variables: \(P\) a nonempty polyhedron
Index: (6)

Name: The lineality space of \(P\)
Definition: \(\text{char.cone}P\cap -\text{char.cone}P\),
Page: 100
Chapter: 8
Section: 2
Variables: \(Ax\le b\) a feasible set of linear inequations,
\(P=\{x\mid Ax\le b\}\)
Index: (6)
Definition2: \(\{y\mid Ay=0\}\)
Conjdef: equivalenty
Abbreviation: \(\text{lin.space}P\)
DefType: Subspace of \(P\)

Name: A pointed non-empty polyhedron
Definition: A non-empty polyhedron whose lineality space's dimension is 0.
Page: 100
Chapter: 8
Section: 2
Index: (6)

Q: The number of such decompositions is [...].
A: 1
Page: 100
Chapter: 8
Section: 2
Variables: \(P\) a nonempty polyhedron
Index: (7)
Name: Decomposition of \(P\) as the sum of a linear space and a nonempty pointed polyhedron
Q: A decomposition: [...].
A: \(\text{lin.space}P+(H^\bot\cap P)\)

Name: A full dimensional polyhedron in \(\mathbb R^n\)
Definition: A polyhedron in \(\mathbb R^n\) whose dimension is \(n\).
Page: 101
Chapter: 8
Section: 2
Variables: \(n\in\mathbb N\)

Question: \(\text{dim}(\emptyset)\)
Answer: -1.
Page: 101
Chapter: 8
Section: 1

Name: Maximal flow as linear programming
Definition: \(\max(\sum_{a\in \delta^-(r)}x_a=\sum_{a\in \delta^+(r)}x_a)\),
subject to:
-\(x\) is a flow,
-\(x\) satisfies the capacitance.
Page: 97
Chapter: 7
Section: 10
Variables: \(D=(V,A)\) a directed graph,
\(r\) a source, \(s\) a sink,
\((x_a)_{a\in A}\) variables

Name: The dimension of \(P\)
Definition: The dimension of the affine space of \(P\)
Page: 100
Chapter: 8
Section: 2
Variables: \(n\in\mathbb N\),
\(Ax\le b\) a feasible set of linear inequations, \(A\) with \(n\) columns.
\(P=\{x\mid Ax\le b\}\)
Index: (9)
Definition2: \(n-\text{rank}A^=\)

Smaller0: there exists a vector \(x\ge 0\) with \(Ax=b\)
Greater0: (\(yA\ge0\) implies \(yb\ge0\))
Page: 89
Chapter: 7
Section: 3
Variables: \(A\) a matrix,
\(b\) a vector.
Index: 1d
Kind: Cor
Smaller to greater: iff
Name: Farkas' lemma

Name: A (convex) polytope
Definition: A convex hull of finitely many vectors of \(V\),
Page: 88, 89
Chapter: 7, 7
Section: 1,2
Variables: \(V\) a \(\mathbb Q\)-vector space
Definition2: a bounded polyhedron