Solving Problems with Min-Type Functions by Disjunctive Programming

We consider applications of disjunctive programming to global optimization and problems with equilibrium constraints. We propose a modification of the algorithm of F. Beaumont for disjunctive programming problems and show its numerical efficiency.     

Lift-and-project for general two-term disjunctions

In this paper we generalize the cut strengthening method of Balas and Perregaard for 0/1 mixed-integer programming to disjunctive programs with general two-term disjunctions. We apply our results to linear programs with complementarity constraints.     

Projective DNF formulae and their revision

Combinatorial and learnability results are proven for projective disjunctive normal forms, a class of DNF expressions introduced by Valiant.     

Nondifferentiable reverse convex programs and facetial convexity cuts via a disjunctive characterization

Disjunctive Programs can often be transcribed as reverse convex constrained problems with nondifferentiable constraints and unbounded feasible regions. We consider this general class of nonconvex programs, called Reverse Convex Programs (RCP), and show that under quite general conditions, the closure of the convex hull of the feasible region is polyhedral. This development is then pursued from a more constructive standpoint, in that, for certain special reverse convex sets, we specify a finite linear disjunction whose closed convex hull coincides with that of the special reverse convex set. When interpreted in the context of convexity/intersection cuts, this provides the capability of generating any (negative edge extension) facet cut. Although this characterization is more clarifying than computationally oriented, our development shows that if certain bounds are available, then convexity/intersection cuts can be strengthened relatively inexpensively.     

Facet inequalities from simple disjunctions in cutting plane theory

The duality between facets of the convex hull of disjunctive sets and the extreme points of reverse polars of these sets is utilized to establish simple rules for the derivation of all facet cuts for simple disjunctions, namely, elementary disjunctions in nonnegative variables. These rules generalize the cut generation procedure underlying polyhedral convexity cuts with negative edge extensions. The latter are also shown to possess some interesting properties with respect to a biextremal problem that maximizes the distance, from the origin, of the nearest point feasible to the cut. A computationally inexpensive procedure is given to generate facet cuts for simple disjunctions which are dominant with respect to any specified preemptive ordering of variables.     

Disjunctive cuts for continuous linear bilevel programming

This work shows how disjunctive cuts can be generated for a bilevel linear programming problem (BLP) with continuous variables. First, a brief summary on disjunctive programming and bilevel programming is presented. Then duality theory is used to reformulate BLP as a disjunctive program and, from there, disjunctive programming results are applied to derive valid cuts. These cuts tighten the domain of the linear relaxation of BLP. An example is given to illustrate this idea, and a discussion follows on how these cuts may be incorporated in an algorithm for solving BLP.     

A complete characterization of disjunctive conic cuts for mixed integer second order cone optimization

We study the convex hull of the intersection of a disjunctive set defined by parallel hyperplanes and the feasible set of a mixed integer second order cone optimization (MISOCO) problem. We extend our prior work on disjunctive conic cuts (DCCs), which has thus far been restricted to the case in which the intersection of the hyperplanes and the feasible set is bounded. Using a similar technique, we show that one can extend our previous results to the case in which that intersection is unbounded. We provide a complete characterization in closed form of the conic inequalities required to describe the convex hull when the hyperplanes defining the disjunction are parallel.     

Note on: N.E. Aguilera, M.S. Escalante, G.L. Nasini, “The disjunctive procedure and blocker duality”

Aguilera et al. [Discrete Appl. Math. 121 (2002) 1–13] give a generalization of a theorem of Lehman through an extension of the disjunctive procedure defined by Balas, Ceria and Cornuéjols. This generalization can be formulated as(A) For every clutter , the disjunctive index of its set covering polyhedron coincides with the disjunctive index of the set covering polyhedron of its blocker, .In Aguilera et al. [Discrete Appl. Math. 121 (2002) 1–3], (A) is indeed a corollary of the stronger result(B) .Motivated by the work of Gerards et al. [Math. Oper. Res. 28 (2003) 884–885] we propose a simpler proof of (B) as well as an alternative proof of (A), independent of (B). Both of them are based on the relationship between the “disjunctive relaxations” obtained by and the set covering polyhedra associated with some particular minors of .     

A finitely convergent algorithm for bilinear programming problems using polar cuts and disjunctive face cuts

A finite algorithm is presented in this study for solving Bilinear programs. This is accomplished by developing a suitable cutting plane which deletes at least a face of a polyhedral set. At an extreme point, a polar cut using negative edge extensions is used. At other points, disjunctive cuts are adopted. Computational experience on test problems in the literature is provided.This paper is based upon work supported by the National Science Foundation under Grant No. ENG-77-23683.     

An integrated approach for scheduling health care activities in a hospital

To effectively utilise hospital beds, operating rooms (OR) and other treatment spaces, it is necessary to precisely plan patient admissions and treatments in advance. As patient treatment and recovery times are unequal and uncertain, this is not easy. In response, a sophisticated flexible job-shop scheduling (FJSS) model is introduced, whereby patients, beds, hospital wards and health care activities are respectively treated as jobs, single machines, parallel machines and operations. Our approach is novel because an entire hospital is describable and schedulable in one integrated approach. The scheduling model can be used to recompute timings after deviations, delays, postponements and cancellations. It also includes advanced conditions such as activity and machine setup times, transfer times between activities, blocking limitations and no wait conditions, timing and occupancy restrictions, buffering for robustness, fixed activities and sequences, release times and strict deadlines. To solve the FJSS problem, constructive algorithms and hybrid meta-heuristics have been developed. Our numerical testing shows that the proposed solution techniques are capable of solving problems of real world size. This outcome further highlights the value of the scheduling model and its potential for integration into actual hospital information systems.