Def and Proofs

Question 1

Convex Combination

Question 2

Convex Set

Question 2

Convex Function

Question 3

Check Convexity + P

Question 3

Local optimal solution is also global optimal solution + P

Question 4

Polyhedron

Question 5

Polytope

Question 6

Optimal vertex + P

Question 7

Basic Feasible Solution

Question 8

Equivalence of verticies and BFS + P

Question 9

Reduced Cost Vector

Question 10

Optimality test for Simplex method + P

Question 11

Bland’s rule + P

Question 12

Farkas Lemma + P

Question 13

Dual of dual + P

Question 14

Strong duality

Question 15

Weak duality + P

Question 16

Optimality conditions in duality

Question 17

Convex Hull

Question 18

Unimodular

Question 19

TUM

Question 20

Sufficients conditions TUM + P

Question 21

Cutting Plane

Question 22

Chvatal’s inequalities

Question 23

Chvatal’s Closure

Question 24

Gomory cuts

Question 25

B&B

Question 26

B&C

Question 27

Incumbent

Question 28

Fathoming criteria (Pruning)

Question 29

When an edge belongs to MST + P

Question 30

Prim-Dijkstra algorithm

Question 30

Kruskal’s algorithm

Question 31

Dijkstra’s algorithm + P

Question 32

Floyd-Warshall’s algorithm correctness + P

Question 33

Feasible flow

Question 34

Network Cut

Question 35

Cut capacity

Question 36

Flow through Cut

Question 37

Flow through every cut constant + P

Question 38

Flow and Capacity + P

Question 39

Max-Flow/Min-cut optimal

Question 40

Saturated arc

Question 41

Residual Network

Question 42

Optimal flow for MAX-FLOW problem + P