Having introduced mixed-integer linear programming (MILP)models in Chapter 6 using somewhat intuitive arguments, this chapter shows that MILP models can be systematically derived using concepts of propositional logic.The chapter introduces the conjunctive normal form (CNF) as a logic form that can be used as a basis to readily formulate linear constraints with 0-1 variables. Steps are described that are required to transform logic propositions into CNF form. Next the concept of disjunctions is introduced, showing that these can be formulated as MILP constraints either with big-M formulation or with the hull reformulation. It is also shown that the latter leads to strong LP relaxations.
Review the options below to login to check your access.
Log in with your Cambridge Higher Education account to check access.
If you believe you should have access to this content, please contact your institutional librarian or consult our FAQ page for further information about accessing our content.