A hierarchy of relaxations for nonlinear convex generalized disjunctive programming

We propose a framework to generate alternative mixed-integer nonlinear programming formulations for disjunctive convex programs that lead to stronger relaxations. We extend the concept of “basic steps” defined for disjunctive linear programs to the nonlinear case. A basic step is an operation that takes a disjunctive set to another with fewer number of conjuncts. We show that the strength of the relaxations increases as the number of conjuncts decreases, leading to a hierarchy of relaxations. We prove that the tightest of these relaxations, allows in theory the solution of the disjunctive convex program as a nonlinear programming problem. We present a methodology to guide the generation of strong relaxations without incurring an exponential increase of the size of the reformulated mixed-integer program. Finally, we apply the theory developed to improve the computational efficiency of solution methods for nonlinear convex generalized disjunctive programs (GDP). This methodology is validated through a set of numerical examples.     

Experimenting with parallelism for the instantiation of ASP programs

In the last few years, microprocessor technologies have been moving towards multi-core architectures, in order to improve performance as well as reduce power consumption. This makes real Symmetric MultiProcessing (SMP) available even on non-dedicated machines, and paves the way to the development of better performing software. Notably, the recent application of Answer Set Programming (ASP) in different emerging areas, such as knowledge management or information extraction/integration, shows that performance is a crucial issue also for ASP systems. Among the tasks performed by such systems, the instantiation process, which consists of generating a variable-free program equivalent to the input one, is one of the most expensive from a computational viewpoint, especially in the case of huge input data. In this paper a new strategy exploiting parallelism for the instantiation of ASP programs is proposed. An implementation of this strategy and its integration with the grounding module of the DLV system is discussed. The results of an experimental analysis are also presented, which confirm that the strategy is effective in making ASP instantiation more efficient.     

Disjunctive Optimization: Critical Point Theory

In this paper, we introduce the concepts of (nondegenerate) stationary points and stationary index for disjunctive optimization problems. Two basic theorems from Morse theory, which imply the validity of the (standard) Morse relations, are proved. The first one is a deformation theorem which applies outside the stationary point set. The second one is a cell-attachment theorem which applies at nondegenerate stationary points. The dimension of the cell to be attached equals the stationary index. Here, the stationary index depends on both the restricted Hessian of the Lagrangian and the set of active inequality constraints. In standard optimization problems, the latter contribution vanishes.     

The C 3 Theorem and a D 2 Algorithm for Large Scale Stochastic Mixed-Integer Programming: Set Convexification

This paper considers the two-stage stochastic integer programming problem, with an emphasis on instances in which integer variables appear in the second stage. Drawing heavily on the theory of disjunctive programming, we characterize convexifications of the second stage problem and develop a decomposition-based algorithm for the solution of such problems. In particular, we verify that problems with fixed recourse are characterized by scenario-dependent second stage convexifications that have a great deal in common. We refer to this characterization as the C³ (Common Cut Coefficients) Theorem. Based on the C³ Theorem, we develop a decomposition algorithm which we refer to as Disjunctive Decomposition (D²). In this new class of algorithms, we work with master and subproblems that result from convexifications of two coupled disjunctive programs. We show that when the second stage consists of 0-1 MILP problems, we can obtain accurate second stage objective function estimates after finitely many steps. This result implies the convergence of the D² algorithm.This research was funded by NSF grants DMII 9978780 and CISE 9975050.     

三角模族T_(q,p)-LGN与逻辑系统LGN

首先, 给出一种新的带两个参数的左连续三角模族T(q,p)-LGN((q,p)∈[-1,1]×(-∞,0))及其伴随蕴涵算子族R(q,p)-LGN((q,p)∈[-1,1]×(-∞,0)), 分别简称它们为左连续三角模族T(p,q)-LGN及伴随蕴涵算子族R(q,p)-LGN;然后,定义了LGN三角模族的概念(基于此族的模糊逻辑系统等价于系统L,G与L*(或NM) 的所有定理的交LGN);最后,证明了左连续三角模族T(q,p)-LGN是LGN三角模族的一个子族.     

Sequential convexification in reverse convex and disjunctive programming

This paper is about a property of certain combinatorial structures, called sequential convexifiability, shown by Balas (1974, 1979) to hold for facial disjunctive programs. Sequential convexifiability means that the convex hull of a nonconvex set defined by a collection of constraints can be generated by imposing the constraints one by one, sequentially, and generating each time the convex hull of the resulting set. Here we extend the class of problems considered to disjunctive programs with infinitely many terms, also known as reverse convex programs, and give necessary and sufficient conditions for the solution sets of such problems to be sequentially convexifiable. We point out important classes of problems in addition to facial disjunctive programs (for instance, reverse convex programs with equations only) for which the conditions are always satisfied. Finally, we give examples of disjunctive programs for which the conditions are violated, and so the procedure breaks down.The research underlying this report was supported by Grant ECS-8601660 of The National Science Foundation and Contract N00014-85-K-0198 with the Office of Naval Research. Reproduction in whole or in part is permitted for any purpose of the U.S. Government.On leave from the University of Aarhus, Denmark.     

Duality in disjunctive programming via vector optimization

In this paper, we develop a new duality theory for families of linear programs with an emphasis on disjunctive linear optimization by proposing a vector optimization problem as dual problem. We establish that the well-known relations between primal and dual problems hold in this context. We show that our method generalizes the duality results of Borwein on families of linear programs, of Balas on disjunctive programs, and of Patkar and Stancu-Minasian on disjunctive linear fractional programs. Moreover, we can derive some duality results for integer and for fractional programs where the denominator is not assumed (as usual) to be greater than zero for each feasible point.     

A geometric way to build strong mixed-integer programming formulations

We give an explicit geometric way to build mixed-integer programming (MIP) formulations for unions of polyhedra. The construction is simply described in terms of spanning hyperplanes in an $r$-dimensional linear space. The resulting MIP formulation is ideal, and uses exactly $r$ integer variables and $2\times \left(\#\text{of spanning hyperplanes}\right)$ general inequality constraints. We use this result to derive novel logarithmic-sized ideal MIP formulations for discontinuous piecewise linear functions and structures appearing in robotics and power systems problems.     

Boole–De Morgan Algebras and Quasi-De Morgan Functions

In this paper we establish a Stone-type and a Birkhoff-type representation theorems for Boole–De Morgan algebras and prove that the free Boole–De Morgan algebra on n free generators is isomorphic to the Boole–De Morgan algebra of quasi-De Morgan functions of n variables. Also we introduce the concept of Zhegalkin polynomials for quasi-De Morgan functions and consider the representation problem of those functions by polynomials.