Management Science: The Art of Modeling with Spreadsheets, 4th Edition

11 Integer Optimization

11.1 INTRODUCTION

One of the basic assumptions in linear programming models relates to divisibility of the decision variables: Fractional values of decision variables make sense either literally (12.6 tons of steel can be produced) or as a modeling approximation (in practical terms, 1,776.2 trucks is the same as 1,776). The optimal solution of a linear program may therefore contain fractional decision variables, and this is appropriate—or at least tolerable—in most applications. In some cases, however, it may be necessary to ensure that some or all of the decision variables take on integer values. Accommodating the requirement that variables must be integers is the subject of integer programming. In this chapter, we examine the formulation and solution of integer programs.

Before we discuss how to handle the integer requirement with Solver, we review what we have already covered that relates to the subject of fractional values for decision variables. There are, for example, some problem types where the occurrence of fractional decision variables can be avoided entirely. In transportation, assignment, and transshipment models, which were covered in the previous chapter, integer solutions are always produced (provided the supply and demand parameters are integers) without an explicit requirement. As those examples might suggest, there are categories of linear programs that can guarantee integer solutions, but a comprehensive treatment of those special cases ...