AN ALGORITHM FOR DISJUNCTIVE PROGRAMS

A disjunctive program is a linear program complicated by disjunctions, that is, sets of constraints of which at least one must be true. The commonest example is the fixed cost problem in which either production of an item is zero or a fixed cost is incurred. The conventional solution technique is to re-express each disjunction in terms of binary variables and solve the resulting mixed integer program. This paper demonstrates that this re-expression is unnecessary: it is possible and usually advantageous to arbitrate on the logical relationships amongst constraints themselves. The advantages include easier matrix generation, smaller nodal problems and the availability of good arbitration criteria. An example is given and computational results are summarized.