Optimization Modeling with Spreadsheets, 3rd Edition

6 INTEGER PROGRAMMING: BINARY-CHOICE MODELS

An integer programming model is a linear program with the requirement that some or all of the decision variables must be integers. In principle, we could distinguish between linear programs with integer variables and nonlinear programs with integer variables, but the latter are extremely difficult to optimize and generally beyond the capability of Solver. Therefore, we focus on the role of integer variables in what would otherwise be linear programming models. Thus far, we have paid limited attention to whether the decision variables take on integer values. In Chapter 3, we pointed out that in special network models, integer solutions are guaranteed. In other cases, we encountered integer solutions without explicitly requiring integers, so there seemed to be no need to discuss integrality. In still other cases, we seemed to be content with fractional solutions, especially when the decision variables were scaled. In this chapter, the role of integer values takes center stage.

This chapter first describes how Solver handles integer programs. Next, we explore the basic capital budgeting model as a way of introducing binary variables and developing some intuition for the effects of integer requirements on decision variables. Then, in the remainder of the chapter, we look at models characterized by binary choice. In these optimization models, all decisions are of a yes/no variety. Other uses of binary variables are covered in the next ...