Rounding to the nearest power of two times is monotone and lands within a factor
ProvedInventoryControl.pot_round_monotoneinventory-controllot-sizingoperations-researchpowers-of-two
Fix a basic quantity and round each positive to with the integer nearest to . Then for positive ,
- , so nested batch quantities round to nested powers of two, which is Roundy's constraint (9.16) with ;
- , the window of Eq. (7.5).
The first property is the one sentence of the book's proof that concerns the constraints: because the relaxed solution satisfies (9.18), its rounding satisfies (9.16). The second is what the powers-of-two analysis of Sect. 7.1 needs of the rounding, and it is why the cost bounds of Propositions 7.1 and 7.2 apply to it.
Preamble
import Definitions.Def_InventoryControl_serial
Formal statement
namespace InventoryControl
theorem pot_round_monotone (q Q Q' : ℝ) (hq : 0 < q) (hQ : 0 < Q) (hQ' : 0 < Q') (hle : Q ≤ Q') :
potRound q Q ≤ potRound q Q'
∧ Real.sqrt 2 / 2 * Q ≤ (2 : ℝ) ^ potRound q Q * q
∧ (2 : ℝ) ^ potRound q Q * q ≤ Real.sqrt 2 * Q := by sorry
end InventoryControl
Source
Sven Axsäter, Inventory Control, 3rd ed., Springer 2015, DOI 10.1007/978-3-319-15729-0, p. 180, Sect. 9.2.2, Eq. (9.22) and the sentence after: 'Due to (9.18), we know that mi >= mi-1 and the batch quantities obtained must consequently satisfy (9.16)'; the factor sqrt 2 is Eq. (7.5) p. 123
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.