OPTIMIZATION

Question 1

Assignment problem

Answer 1

Network optimization model with two sets of nodes, that finds the best way to assign each node in one set to each node in the other set.

Question 2

Bellman’s equation

Answer 2

Equation used in dynamic programming that ensures optimality of a solution.

Question 3

Clique

Answer 3

A set of nodes where each pair is connected by an arc.

Question 4

Concave function

Answer 4

A function f() where for every two points 𝑥𝑥 and 𝑦𝑦, 𝑓𝑓(𝑐𝑐𝑐𝑐 + (1 −𝑐𝑐)𝑦𝑦) ≥ 𝑐𝑐𝑐𝑐(𝑥𝑥) + (1 − 𝑐𝑐)𝑓𝑓(𝑦𝑦) for all 𝑐𝑐 between 0 and 1. In two dimensions, this means if the points (𝑥𝑥, 𝑓𝑓(𝑥𝑥)) and (𝑦𝑦, 𝑓𝑓(𝑦𝑦)) are connected with a straight line, the line is always below [or equal to]
the function’s curve between those two points. If 𝑓𝑓() is concave, then −𝑓𝑓() is convex.

Question 5

Convex function

Answer 5

A function f() where for every two points 𝑥𝑥 and 𝑦𝑦, 𝑓𝑓(𝑐𝑐𝑐𝑐 + (1 −𝑐𝑐)𝑦𝑦) ≤ 𝑐𝑐𝑐𝑐(𝑥𝑥) + (1 − 𝑐𝑐)𝑓𝑓(𝑦𝑦) for all 𝑐𝑐 between 0 and 1. In two dimensions, this means if the points (𝑥𝑥, 𝑓𝑓(𝑥𝑥)) and (𝑦𝑦, 𝑓𝑓(𝑦𝑦)) are connected with a straight line, the line is always above [or equal to] the function’s curve between those two points. If 𝑓𝑓() is convex, then −𝑓𝑓() is concave.

Question 6

Convex set

Answer 6

A set of points for which a straight line drawn between any two points in the set, stays inside the set. A circle is a convex set. A set shaped like the letter “U” is not convex; the line between the two points on top goes outside of the set.

Question 7

Dynamic programming

Answer 7

Optimization approach that involves making a sequence of decisions over time, based on the current state of a system.

Question 8

Greedy algorithm

Answer 8

Algorithm that makes the immediately-best choice at each step.

Question 9

Linear equation

Answer 9

Equation where a linear function is set equal to a constant or another linear function.

Question 10

Linear function

Answer 10

Weighted sum of variables, plus a constant: 𝑎𝑎0 + ∑ 𝑎𝑎𝑖𝑖𝑥𝑥𝑖𝑖 𝑚𝑚 𝑖𝑖=1 .