Show that all Chv´atal functions are subadditive, homogeneous, and nondecreasing. 4.25. Consider the integer programming problem min 3x1 + 4x2 −x1 + 3x2 ≥ 0 2x1 + x2 − 5 ≥ 0 x1, x2 ≥ {0, 1, 2, 3}...

Show that all Chv´atal functions are subadditive, homogeneous, and

nondecreasing.

4.25.

Consider the integer programming problem

min 3x1 + 4x2

−x1 + 3x2 ≥ 0

2x1 + x2 − 5 ≥ 0

x1, x2 ≥ {0, 1, 2, 3}

which has optimal value 10. The bound 3x1 + 4x2 ≥ 10 can be obtained by

first taking a linear combination of the constraints with multipliers 2

7 and 1

7

and rounding up to obtain a new inequality, then taking a linear combination

of the second constraint and the new inequality with multipliers 3

2 and 5

2 .

Write the corresponding Chv´atal function in the form h(d) = u

M d

. Write

an expression for a lower bound on the optimal value if the right-hand side

is perturbed to (0 + Δ1, 5 + Δ2).