§2.1, p. 1427 — under (10) or (11) the PCPSP-C has an optimal solution whenever it is feasible
ProvedOpenPitMIP.UltPit.exists_optimalexistence-of-optimummixed-integer-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1production-scheduling
Consider an instance of the PCPSP-C (formulation (1)–(7)) under the standing assumptions of §2.1, with either the full integrality condition (10) or the partial integrality condition (11). If the PCPSP-C has a feasible solution, then it has an optimal solution: a feasible with
for every feasible .
The paper derives this from the boundedness of the feasible set; it guarantees that the minimal optimal solutions of Theorem 1 are about a nonempty set of optima.
Formalization Note Boundedness of the feasible set relies on every cluster being nonempty (standing assumption), which forces .
Preamble
import Mathlib import Definitions.Def_OpenPitMIP_UltPit_Setting
Formal statement
namespace OpenPitMIP.UltPit
open PCPSPC
/-- §2.1, p. 1427: under either integrality condition (10) or (11) the PCPSP-C has a bounded
feasible set, so an optimal solution exists whenever the feasible set is nonempty. -/
theorem exists_optimal {B D C : Type} [Fintype B] [Fintype D] [Fintype C] {T m : ℕ}
(I : PCPSPC B D C T m) (hI : I.Standing) (κ : Integrality)
(hfeas : ∃ x y, I.Feasible κ x y) :
∃ x y, I.Optimal κ x y := by sorry
end OpenPitMIP.UltPit
Source
Oper. Res. 68(5), §2.1, p. 1427
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.