Title: Theory / Unimportant / CS / Algo / Linear and integer programming / Schrijver{ / 4 Integer linear programming
Tags: fromMath hasSeenConjDef mathToDef mathToSee

Name: Integer linear programming problem
Definition: Determine \(\max\{cx\mid Ax\le b; x\text{ integral}\}\)
Page: 229, 230
Chapter: 16
Section: 1
Definition2: Determine \(\max\{cx\mid x\ge 0; Ax=b; x\text{ integral}\}\).
Conjdef: Given rational matrix \(A\), and rational vectors \(b,c\)
Definition3: Decide if \(Ax\le b\) for some integral vector \(x\),
Definition4: Decide if \(Ax= b\) for some nonnegative integral vector \(x\)

Q: \[[...][...][\text{min/max of related some set}]\]
A: \max\{cx\mid Ax\le b; x\text{ integral}\}; \le; \min\{yb\mid y\ge 0;yA=c;y\text{ integral}\}
Page: 229
Chapter: 16
Section: 1
Variables: \(A\) a rational matrix, \(b,c\) rational vectors.
Name: Integer linear programming problem

Name: Integer hull of \(P\)
Definition: The convex hull of the integral vectors in \(P\).
Page: 230
Chapter: 16
Section: 3
Variables: \(P\) a polyhedron
Notation: \(P_1\)
Index: (8)

Smaller0: \(P\) is rational
Greater0: a polyhedron
Page: 231
Chapter: 16
Section: 3
Variables: \(P\) a polyhedron
Index: 1
Kind: Theo
Hide middle: yes
Prefix Greater: \(P_1\) is

Smaller0: \(P\) is rational
Greater0: the characteristic cones of \(P\) and \(P_1\) are equals
Page: 231
Chapter: 16
Section: 3
Variables: \(P\) a polyhedron
Index: 1
Kind: Theo
Hide middle: yes
Smaller1: \(P_1\) non-empty

Question: \(\text{max}\{cx\mid Ax\le b; x\in\mathbb Z^m\}\) is computable in
Answer: P.
Page: 231
Chapter: 16
Section: 3
Variables: \(A\in\mathbb Q^{m,n}\), \(b\in\mathbb Q^n\), \(c\in\mathbb Q^m\)

Name: An integral polyhedron
Definition: \(P=P_1\).
Page: 231, 232
Chapter: 16
Section: 3
Definition2: each face of \(P\) contains integral vectors,
Conjdef: A polyhedron \(P\) such that, equivalently
Definition3: each minimal face of \(P\) contains integral vectors,
Extra: c integral ?
Definition4: \(\text{max}\{cx\mid x\in P\}\) is attained by an integral vector, for each \(c\) for which the maximum is finite.