Dynamic Lagrangian dual and reduced RLT constructs for solving 0–1 mixed-integer programs

In this paper, we consider a dynamic Lagrangian dual optimization procedure for solving mixed-integer 0–1 linear programming problems. Similarly to delayed relax-and-cut approaches, the procedure dynamically appends valid inequalities to the linear programming relaxation as induced by the Reformulation-Linearization Technique (RLT). A Lagrangian dual algorithm that is augmented with a primal solution recovery scheme is applied implicitly to a full or partial first-level RLT relaxation, where RLT constraints that are currently being violated by the primal estimate are dynamically generated within the Lagrangian dual problem, thus controlling the size of the dual space while effectively capturing the strength of the RLT-enhanced relaxation. We present a preliminary computational study to demonstrate the efficacy of this approach.     

A Hierarchy of Relaxations Leading to the Convex Hull Representation for General Discrete Optimization Problems

We consider linear mixed-integer programs where a subset of the variables are restricted to take on a finite number of general discrete values. For this class of problems, we develop a reformulation-linearization technique (RLT) to generate a hierarchy of linear programming relaxations that spans the spectrum from the continuous relaxation to the convex hull representation. This process involves a reformulation phase in which suitable products using a defined set of Lagrange interpolating polynomials (LIPs) are constructed, accompanied by the application of an identity that generalizes x(1−x) for the special case of a binary variable x. This is followed by a linearization phase that is based on variable substitutions. The constructs and arguments are distinct from those for the mixed 0-1 RLT, yet they encompass these earlier results. We illustrate the approach through some examples, emphasizing the polyhedral structure afforded by the linearized LIPs. We also consider polynomial mixed-integer programs, exploitation of structure, and conditional-logic enhancements, and provide insight into relationships with a special-structure RLT implementation.     

Tightening concise linear reformulations of 0-1 cubic programs

A common strategy for solving 0-1 cubic programs is to reformulate the non-linear problem into an equivalent linear representation, which can then be submitted directly to a standard mixed-integer programming solver. Both the size and the strength of the continuous relaxation of the reformulation determine the success of this method. One of the most compact linear representations of 0-1 cubic programs is based on a repeated application of the linearization technique for 0-1 quadratic programs introduced by Glover. In this paper, we develop a pre-processing step that serves to strengthen the linear programming bound provided by this concise linear form of a 0-1 cubic program. The proposed scheme involves using optimal dual multipliers of a partial level-2 RLT formulation to rewrite the objective function of the cubic program before applying the linearization. We perform extensive computational tests on the 0-1 cubic multidimensional knapsack problem to show the advantage of our approach.     

Partial convexification cuts for 0–1 mixed-integer programs

In this research, we propose a new cut generation scheme based on constructing a partial convex hull representation for a given 0–1 mixed-integer programming problem by using the reformulation–linearization technique (RLT). We derive a separation problem that projects the extended space of the RLT formulation into the original space, in order to generate a cut that deletes a current fractional solution. Naturally, the success of such a partial convexification based cutting plane scheme depends on the process used to tradeoff the strength of the cut derived and the effort expended. Accordingly, we investigate several variable selection rules for performing this convexification, along with restricted versions of the accompanying separation problems, so as to be able to derive strong cuts within a reasonable effort. We also develop a strengthening procedure that enhances the generated cut by considering the binariness of the remaining unselected 0–1 variables. Finally, we present some promising computational results that provide insights into implementing the proposed cutting plane methodology.     

Enhancing RLT relaxations via a new class of semidefinite cuts

In this paper, we propose a mechanism to tighten Reformulation-Linearization Technique (RLT) based relaxations for solving nonconvex programming problems by importing concepts from semidefinite programming (SDP), leading to a new class of semidefinite cutting planes. Given an RLT relaxation, the usual nonnegativity restrictions on the matrix of RLT product variables is replaced by a suitable positive semidefinite constraint. Instead of relying on specific SDP solvers, the positive semidefinite stipulation is re-written to develop a semi-infinite linear programming representation of the problem, and an approach is developed that can be implemented using traditional optimization software. Specifically, the infinite set of constraints is relaxed, and members of this set are generated as needed via a separation routine in polynomial time. In essence, this process yields an RLT relaxation that is augmented with valid inequalities, which are themselves classes of RLT constraints that we call semidefinite cuts. These semidefinite cuts comprise a relaxation of the underlying semidefinite constraint. We illustrate this strategy by applying it to the case of optimizing a nonconvex quadratic objective function over a simplex. The algorithm has been implemented in C++, using CPLEX callable routines, and two types of semidefinite restrictions are explored along with several implementation strategies. Several of the most promising lower bounding strategies have been implemented within a branch-and-bound framework. Computational results indicate that the cutting plane algorithm provides a significant tightening of the lower bound obtained by using RLT alone. Moreover, when used within a branch-and-bound framework, the proposed lower bound significantly reduces the effort required to obtain globally optimal solutions.     

Reduced RLT representations for nonconvex polynomial programming problems

This paper explores equivalent, reduced size Reformulation-Linearization Technique (RLT)-based formulations for polynomial programming problems. Utilizing a basis partitioning scheme for an embedded linear equality subsystem, we show that a strict subset of RLT defining equalities imply the remaining ones. Applying this result, we derive significantly reduced RLT representations and develop certain coherent associated branching rules that assure convergence to a global optimum, along with static as well as dynamic basis selection strategies to implement the proposed procedure. In addition, we enhance the RLT relaxations with v-semidefinite cuts, which are empirically shown to further improve the relative performance of the reduced RLT method over the usual RLT approach. We present computational results for randomly generated instances to test the different proposed reduction strategies and to demonstrate the improvement in overall computational effort when such reduced RLT mechanisms are employed.     

Enhancing RLT-based relaxations for polynomial programming problems via a new class of v-semidefinite cuts

In this paper, we propose to enhance Reformulation-Linearization Technique (RLT)-based linear programming (LP) relaxations for polynomial programming problems by developing cutting plane strategies using concepts derived from semidefinite programming. Given an RLT relaxation, we impose positive semidefiniteness on suitable dyadic variable-product matrices, and correspondingly derive implied semidefinite cuts. In the case of polynomial programs, there are several possible variants for selecting such particular variable-product matrices on which positive semidefiniteness restrictions can be imposed in order to derive implied valid inequalities. This leads to a new class of cutting planes that we call v-semidefinite cuts. We explore various strategies for generating such cuts, and exhibit their relative effectiveness towards tightening the RLT relaxations and solving the underlying polynomial programming problems in conjunction with an RLT-based branch-and-cut scheme, using a test-bed of problems from the literature as well as randomly generated instances. Our results demonstrate that these cutting planes achieve a significant tightening of the lower bound in contrast with using RLT as a stand-alone approach, thereby enabling a more robust algorithm with an appreciable reduction in the overall computational effort, even in comparison with the commercial software BARON and the polynomial programming problem solver GloptiPoly.     

Global optimization of mixed-integer bilevel programming problems

Two approaches that solve the mixed-integer nonlinear bilevel programming problem to global optimality are introduced. The first addresses problems mixed-integer nonlinear in outer variables and C²-nonlinear in inner variables. The second adresses problems with general mixed-integer nonlinear functions in outer level. Inner level functions may be mixed-integer nonlinear in outer variables, linear, polynomial, or multilinear in inner integer variables, and linear in inner continuous variables. This second approach is based on reformulating the mixed-integer inner problem as continuous via its vertex polyheral convex hull representation and solving the resulting nonlinear bilevel optimization problem by a novel deterministic global optimization framework. Computational studies illustrate proposed approaches.     

Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems

The reformulation–linearization technique (RLT), introduced in [Sherali, H. D., Adams. W. P. (1990). A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM Journal on Discrete Mathematics 3(3), 411–430], provides a way to compute a hierarchy of linear programming bounds on the optimal values of NP-hard combinatorial optimization problems. In this paper we show that, in the presence of suitable algebraic symmetry in the original problem data, it is sometimes possible to compute level two RLT bounds with additional linear matrix inequality constraints. As an illustration of our methodology, we compute the best-known bounds for certain graph partitioning problems on strongly regular graphs.     

Combined bound-grid-factor constraints for enhancing RLT relaxations for polynomial programs

This paper studies the global optimization of polynomial programming problems using Reformulation-Linearization Technique (RLT)-based linear programming (LP) relaxations. We introduce a new class of bound-grid-factor constraints that can be judiciously used to augment the basic RLT relaxations in order to improve the quality of lower bounds and enhance the performance of global branch-and-bound algorithms. Certain theoretical properties are established that shed light on the effect of these valid inequalities in driving the discrepancies between RLT variables and their associated nonlinear products to zero. To preserve computational expediency while promoting efficiency, we propose certain concurrent and sequential cut generation routines and various grid-factor selection rules. The results indicate a significant tightening of lower bounds, which yields an overall reduction in computational effort for solving a test-bed of polynomial programming problems to global optimality in comparison with the basic RLT procedure as well as the commercial software BARON.     

A note on linear complementarity problems and multiple objective programming

Kostreva and Wiecek [3] introduced a problem called LCP-related weighted problem in connection with a multiple objective programming problem, and suggested that a given linear complementarity problem (LCP) can be solved by solving the LCP-related weighted problem associated with it. In this note we provide several clarifications of the claims made in [3]. Finally, we feel that solving any LCP by the approach given in [3] may not be as useful as it is claimed.Mathematics Subject Classification (2000): 90C33Received: October 1998 / Revised version: August 2003     

A global optimization algorithm for polynomial programming problems using a Reformulation-Linearization Technique

This paper is concerned with the development of an algorithm to solve continuous polynomial programming problems for which the objective function and the constraints are specified polynomials. A linear programming relaxation is derived for the problem based on a Reformulation Linearization Technique (RLT), which generates nonlinear (polynomial) implied constraints to be included in the original problem, and subsequently linearizes the resulting problem by defining new variables, one for each distinct polynomial term. This construct is then used to obtain lower bounds in the context of a proposed branch and bound scheme, which is proven to converge to a global optimal solution. A numerical example is presented to illustrate the proposed algorithm.     

Comparison of Two Reformulation-Linearization Technique Based Linear Programming Relaxations for Polynomial Programming Problems

In this paper, we compare two strategies for constructing linear programmingrelaxations for polynomial programming problems using aReformulation-Linearization Technique (RLT). RLT involves an automaticreformulation of the problem via the addition of certain nonlinear impliedconstraints that are generated by using the products of the simple boundingrestrictions (among other products), and a subsequent linearization based onvariable redefinitions. We prove that applying RLT directly to the originalpolynomial program produces a bound that dominates in the sense of being atleast as tight as the value obtained when RLT is applied to the jointcollection of all equivalent quadratic problems that could be constructed byrecursively defining additional variables as suggested by Shor.     

A mixed R&D projects and securities portfolio selection model

The business environment is full of uncertainty. Allocating the wealth among various asset classes may lower the risk of overall portfolio and increase the potential for more benefit over the long term. In this paper, we propose a mixed single-stage R&D projects and multi-stage securities portfolio selection model. Specifically, we present a bi-objective mixed-integer stochastic programming model. Moreover, we use semi-absolute deviation risk functions to measure the risk of mixed asset portfolio. Based on the idea of moments approximation method via linear programming, we propose a scenario generation approach for the mixed single-stage R&D projects and multi-stage securities portfolio selection problem. The bi-objective mixed-integer stochastic programming problem can be solved by transforming it into a single objective mixed-integer stochastic programming problem. A numerical example is given to illustrate the behavior of the proposed mixed single stage R&D projects and multi-stage securities portfolio selection model.     

On equivalent reformulations for absolute value equations

In this note we consider absolute value equations (AVE) of the type Ax+B|x|=c. We discuss unique solvability of AVE, and its relations with linear complementarity problem (LCP) and mixed integer programming.     

Reformulation of mathematical programming problems as linear complementarity problems and investigation of their solution methods

A family of complementarity problems is defined as extensions of the well-known linear complementarity problem (LCP). These are:

On the complexity of computing the handicap of a sufficient matrix

The class of sufficient matrices is important in the study of the linear complementarity problem (LCP)—some interior point methods (IPM’s) for LCP’s with sufficient data matrices have complexity polynomial in the bit size of the matrix and its handicap.In this paper we show that the handicap of a sufficient matrix may be exponential in its bit size, implying that the known complexity bounds of interior point methods are not polynomial in the input size of the LCP problem. We also introduce a semidefinite programming based heuristic, that provides a finite upper bond on the handicap, for the sub-class of P{\mathcal{P}} -matrices (where all principal minors are positive).     

Solution of the complex linear complementarity problem

In an earlier paper, it was shown that the linear and quadratic programming problems in complex space could be unified in the “complex linear complementarity problem” (complex LCP). An existence theory for this problem was provided. The present paper addresses the problem of actually solving the complex LCP and hence complex linear and quadratic programs as well. Two solution procedures are described and an example is given.     

On homogeneous and self-dual algorithms for LCP

We present some generalizations of a homogeneous and self-dual linear programming (LP) algorithm to solving the monotone linear complementarity problem (LCP). Again, while it achieves the best known interior-point iteration complexity, the algorithm does not need to use any “big-M” number, and it detects LCP infeasibility by generating a certificate. To our knowledge, this is the first interior-point and infeasible-starting algorithm for the LCP with these desired features. Research supported in part by NSF Grant DDM-9207347, the University of Iowa Oberman Fellowship and the Iowa College of Business Administration Summer Grant. Part of this work is done while the author is visiting the Delft Optimization Center at the University of Technology, Delft, Netherlands, supported by the Dutch Organization for Scientific Research (NWO).