REQUIREMENTS FOR S IMPLE MIXED INTEGER PROGRAMMING SOLVERSt

Scope and Purpose--In the great majority of real-life mixed integer programming models most of integer variables represent some multiple choice requirements. A multiple choice requirement is usually modeled with a generalized upper bound on a set of zero one variables thus creating the so-called Special Ordered Set (SOS). During the past decade powerful microcomputers with friendly optimization software have become standard productivity ools for businessmen a d other decision makers. Unfortunately, the branch and bound algorithms implemented there, usually, do not support the special treatment ofSOS constraints. Therefore, one may face enormously ong computation time while solving quite small problems including several multiple choice requirements. To overcome these difficulties we propose another algebraic model of multiple choice requirements. While using the proposed modeling technique, the standard branch and bound algorithm generates a balanced branching on the set of options included in the multiple choice requirement. I results usually in a significant shortening of the solution process. Abstract--This note introduces the Special Ordered Inequalities (SOl) as a new technique for integer programming modeling of multiple choice requirements and piecewise linear functions. The standard modeling technique based on the use of Special Ordered Set (SOS) structure requires a branch and bound solver to be armed with the special tools for SOS processing. Otherwise, the standard branching rule applie