ABSTRACT
Overview An integer linear optimization model (notation: ILO-model) is a linear optimization model in which the values of the decision variables are restricted to be integers. The reason for investigating integer optimization models is that many practical problems require integervalued solutions. Solving practical integer optimization models is usually very complicated, and solution techniques usually require excessive amounts of (computer) calculations. We give several examples of ILO-models, and we introduce binary variables, which can be used to model certain nonlinear constraints and objective functions, and logical if-then constraints.
The most widely used solution technique for solving ILO-models is the so-called branchand-bound algorithm: a solution procedure that creates a ‘tree’ of (noninteger) LO-models whose solutions ‘grow’ to an optimal integer solution of the initial model. The branch-andbound algorithm is applied to a knapsack problem, a machine scheduling problem (traveling salesman problem), and a decentralization problem. We also discuss the cutting plane algorithm discovered by Ralph E. Gomory (born 1929) for solving mixed integer linear optimization models (MILO-models), in which some of the decision variables are constrained to be integervalued and the others are allowed to take arbitrary (nonnegative real) values.
