The value function of a mixed integer program: I

AbstractWe study the function G(b) = inf{cx + dy ∣ Ax + By = b, x, y ⩾ 0 and x integer} under the assumptions that G(0) = 0 and A and B are matrices of rationals. G is defined for b ∈ Rm feasible, i.e., b for which the constraining conditions are consistent. We show that: 1.(1) There are constants C, D ⩾ 0 such that for any b, b' feasible and (x, y) with Ax + By = b; x,y⩾0 and x integer, there exist (x′, y′) with Ax′ + By′ = b′;x′,y′⩾0 and x′ integer, for which ∣(x, y) − (x′, y′)∣ ⩽ C∣b−b′∣ + D holds. In a pure integer program (i.e., for B empty) we can take D = 0.2.(2) G is piecewise polyhedral, with finitely many regions in any bounded set. In fact, we obtain a “normal form” for G which reveals the fact just cited as a consequence.3.(3) For any new discrete 'lsactivity’ a0 ∈ Rm, is a suitable “price” c0 ∈ R to set for it such that the new activity will no be employed for any previously attainable requirements, I.e., upon setting G′(b) =inf{c0x0 + cx + dy ∣a0x0 + Ax + By =b,x0, x, y⩾0 and x0,x integer}, we have G′(b) = G(b) for b feasible.4.(4) G has an extension Gm to all of Rm, such that Gm is also the value function of a mixed integer program