Special ordered sets and an application to gas supply operations planning

Special Ordered Sets provide a powerful means of modeling nonconvex functions and discrete requirements, though there has been a tendency to think of them only in terms of multiple-choice zero-one programming. This paper emphasizes the origins and generality of the special ordered set concept, and describes an application in which type 2 sets are used in several forms to model both logical conditions and nonlinear functions.Now at IBM Almaden Research Center, San Jose, CA 95120.     

Global optimization using special ordered sets

The task of finding global optima to general classes of nonconvex optimization problem is attracting increasing attention. McCormick [4] points out that many such problems can conveniently be expressed in separable form, when they can be tackled by the special methods of Falk and Soland [2] or Soland [6], or by Special Ordered Sets. Special Ordered Sets, introduced by Beale and Tomlin [1], have lived up to their early promise of being useful for a wide range of practical problems. Forrest, Hirst and Tomlin [3] show how they have benefitted from the vast improvements in branch and bound integer programming capabilities over the last few years, as a result of being incorporated in a general mathematical programming system.Nevertheless, Special Ordered Sets in their original form require that any continuous functions arising in the problem be approximated by piecewise linear functions at the start of the analysis. The motivation for the new work described in this paper is the relaxation of this requirement by allowing automatic interpolation of additional relevant points in the course of the analysis.This is similar to an interpolation scheme as used in separable programming, but its incorporation in a branch and bound method for global optimization is not entirely straightforward. Two by-products of the work are of interest. One is an improved branching strategy for general special-ordered-set problems. The other is a method for finding a global minimum of a function of a scalar variable in a finite interval, assuming that one can calculate function values and first derivatives, and also bounds on the second derivatives within any subinterval.The paper describes these methods, their implementation in the UMPIRE system, and preliminary computational experience.     

S3 sets. An extension of the Beale-Tomlin special ordered sets

In this work an extension of the Beale-Tomlin special ordered sets is introduced that has proved to be efficient for solving certain types of open shop scheduling problems. Besides their usual characteristics, exclusivity constraints in the jobs are allowed, more general than tree-like precedence structures are considered, and semi-active schedules that cannot be labeled as non-optimal solutions may occur. The problem is formulated as a large-scale 0–1 model. Computational experience on some real-life problems is reported.     

A note of the knapsack problem with special ordered sets

The knapsack problem with special ordered sets and arbitrarily signed coefficients is shown to be equivalent to a standard problem of the same type but having all coefficients positive. Two propositions are proven which define an algorithm for the linear programming relaxation of the standard problem that is a natural generalization of the Dantzig solution to the problem without special ordered sets/ Several properties of the corvex hull of the associated zero-one polytope are derived.     

Methods of Chebyshev points of convex sets and their applications

Chebyshev points of bounded convex sets, search algorithms for them, and various applications to convex programming are considered for simple approximations of reachable sets, optimal control, global optimization of additive functions on convex polyhedra, and integer programming. The problem of searching for Chebyshev points in multicriteria models of development and operation of electric power systems is considered.     

Interactive decision software and computer graphics for architectural and space planning

We describe the development and successful implementation of a decision support system now being used by several leading firms in the architecture and space planning industries. The system, which we call SPDS (spatial programming design system) has the following characteristics: (i) user-friendly convenience features permitting architects and space planners to operate the system without being experienced programmers; (ii) interactive capabilities allowing the user to control and to manipulate relevant parameters, orchestrating conditions to which his or her intuition provides valuable input; (iii) informative and understandable graphics, providing visual displays of interconnections that the computer itself treats in a more abstract methematical form; (iv) convenient ways to change configurations, and to carry out ‘what if’ analyses calling on the system’s decision support capabilities; (v) a collection of new methods, invisible to the user, capable of generating good solutions to the mathematical programming problems that underlie each major design component. These new methods succeed in generating high quality solutions to a collection of complex discrete, highly nonlinear problems. While these problems could only be solved in hours, or not at all, with previously existing software, the new methods obtain answers in seconds to minutes on a minicomputer. Major users, including Dalton, Dalton, Newport, and Marshal Erdwin, report numerous advantages of the system over traditional architectural design methods.     

Interactive decision software and computer graphics for architectural and space planning

We describe the development and successful implementation of a decision support system now being used by several leading firms in the architecture and space planning industries. The system, which we call SPDS (spatialprogrammingdesignsystem) has the following characteristics: (i) user-friendly convenience features permitting architects and space planners to operate the system without being experienced programmers; (ii) interactive capabilities allowing the user to control and to manipulate relevant parameters, orchestrating conditions to which his or her intuition provides valuable input; (iii) informative and understandable graphics, providing visual displays of interconnections that the computer itself treats in a more abstract methematical form; (iv) convenient ways to change configurations, and to carry out what if analyses calling on the system's decision support capabilities; (v) a collection of new methods, invisible to the user, capable of generating good solutions to the mathematical programming problems that underlie each major design component. These new methods succeed in generating high quality solutions to a collection of complex discrete, highly nonlinear problems. While these problems could only be solved in hours, or not at all, with previously existing software, the new methods obtain answers in seconds to minutes on a minicomputer. Major users, including Dalton, Dalton, Newport, and Marshal Erdwin, report numerous advantages of the system over traditional architectural design methods.     

Ladders in ordered sets

An ordered set P is said to have the 2-cutset property if for every element x of P there is a subset S of P whose elements are noncomparable to x, such that |S|2 and such that every maximal chain in P meets {x}S. It is shown that if P has the 2-cutset property and has width n then P contains a ladder of length [1/2(n–3)].     

Holes in ordered sets

We pursue the technique of “holes” to study the retracts of an ordered set. This is applied to establish a close connection between the class of absolute retracts and the class of dismantlable ordered sets.     

Powers of ordered sets

Recently there has been significant progress in the study of powers of ordered sets. Much of this work has concerned cancellation laws for powers and uses these two steps. First, logarithmic operators are introduced to transform cancellation problems for powers into questions involving direct product decompositions. Second, refinement theorems for direct product decompositions are brought to bear. Here we present two results with the aim of highlighting these steps.Supported by NSF grant MCS 83-02054     

Solving nonlinear integer programs with large-scale optimization software

This paper describes recent experience in tackling large nonlinear integer programming problems using the MINOS large-scale optimization software. A technique is presented for extending the constrained search approach used in MINOS to exploring integer-feasible solutions once a continuous optimal solution is obtained. Computational experience with this approach is described for two classes of problems: quadratic assignment problems and pipeline network design problems.     

Homogeneity in finite ordered sets

A tower in an ordered set (X, ) is defined to be a subsetS ofX which has the property that for everysS there is a maximal chainC in {xX|xs} which is wholly contained inS. An ordered set (X, ) is called tower-homogeneous if every order isomorphism between towers in (X, ) can be extended to an automorphism of (X, ). It is shown that a finite ordered set is tower-homogeneous if and only if it can be built up from singletons stepwise by constructions of three different types.     

Solving nonlinear integer programs with large-scale optimization software

This paper describes recent experience in tackling large nonlinear integer programming problems using the MINOS large-scale optimization software. A technique is presented for extending the constrained search approach used in MINOS to exploring integer-feasible solutions once a continuous optimal solution is obtained. Computational experience with this approach is described for two classes of problems: quadratic assignment problems and pipeline network design problems.     

Pseudo-similar points in ordered sets

Two points l and h in an ordered set P are called pseudo-similar iff P?{l} is isomorphic to P?{h} and there is no automorphism of P that maps l to h. This paper provides a characterization of ordered sets with at least two pseudo-similar points. Special attention is given to ordered sets with pseudo-similar points l and h so that one of the points is minimal and the other is maximal. These sets will play a key role in the reconstruction of the rank of the removed element in a non-extremal card.     

An ideal column algorithm for integer programs with special ordered sets of variables

One of the most frequently occurring integer programming structures is the one which has special ordered sets of variables included in multiple choice constraints. For problems with this structure a set of ideal columns are defined from the linear programming relaxation of the integer program and a reduced integer program is formed by keeping only those columns within a specified distance from the ideal column. Conditions are established which guarantee when the optimal solution to the reduced problem is als optimal for the original problem. When these conditions are not satisfied, bounds on the optimal solution value are provided. Ideal columns are also used to establish weights for the special ordered set variables. This procedure has been implemented through a control program written by the authors for MPSX/370-MIP/370. Computational results are given.     

Relative polars in ordered sets

In the paper, the notion of relative polarity in ordered sets is introduced and the lattices of R-polars are studied. Connections between R-polars and prime ideals, especially in distributive sets, are found.     

Finite projective ordered sets

We show that quasiprojectivity and projectivity are equivalent properties for finite ordered sets of more than two elements.