DRL*: A hierarchy of strong block-decomposable linear relaxations for 0-1 MIPs

In this paper we introduce DRL*, a new hierarchy of linear relaxations for 0-1 mixed integer linear programs (MIPs), based on the idea of Reformulation-Linearization, and explore its links with the Lift-and-Project (L&P) hierarchy and the Sherali-Adams (RLT) hierarchy. The relaxations of the new hierarchy are shown to be intermediate in strength between L&P and RLT relaxations, and examples are shown for which it leads to significantly stronger bounds than those obtained from Lift-and-Project relaxations. On the other hand, as opposed to the RLT relaxations, a key advantage of the DRL* relaxations is that they feature a decomposable structure when formulated in extended space, therefore lending themselves to more efficient solution algorithms by properly exploiting decomposition. Links between DRL* and both the L&P and RLT hierarchies are further explored, and those constraints which should be added to the rank d L&P relaxation (resp to the rank d RLT relaxation) to make it coincide with the rank d DRL* relaxation (resp: to the rank d RLT relaxation) are identified. Furthermore, a full characterization of those 0-1 MIPs for which the DRL* and RLT relaxations coincide is obtained. As an application, we show that both the RLT and DRL* relaxations are the same up to rank d for the problem of optimizing a pseudoboolean function of degree d over a polyhedron. We report computational results comparing the strengths of the rank 2 L&P, DRL* and RLT relaxations. Impact on possible improved efficiency in computing some bounds for the quadratic assignment problem and other directions for future research are suggested in the conclusions.     

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.     

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.     

Enumeration Approach for Linear Complementarity Problems Based on a Reformulation-Linearization Technique

In this paper, we consider the linear complementarity problem (LCP) and present a global optimization algorithm based on an application of the reformulation-linearization technique (RLT). The matrix M associated with the LCP is not assumed to possess any special structure. In this approach, the LCP is formulated first as a mixed-integer 0–1 bilinear programming problem. The RLT scheme is then used to derive a new equivalent mixed-integer linear programming formulation of the LCP. An implicit enumeration scheme is developed that uses Lagrangian relaxation, strongest surrogate and strengthened cutting planes, and a heuristic, designed to exploit the strength of the resulting linearization. Computational experience on various test problems is presented.     

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.     

A Reformulation-Linearization Technique (RLT) for semi-infinite and convex programs under mixed 0-1 and general discrete restrictions

The Reformulation-Linearization Technique (RLT) provides a hierarchy of relaxations spanning the spectrum from the continuous relaxation to the convex hull representation for linear 0-1 mixed-integer and general mixed-discrete programs. We show in this paper that this result holds identically for semi-infinite programs of this type. As a consequence, we extend the RLT methodology to describe a construct for generating a hierarchy of relaxations leading to the convex hull representation for bounded 0-1 mixed-integer and general mixed-discrete convex programs, using an equivalent semi-infinite linearized representation for such problems as an intermediate stepping stone in the analysis. For particular use in practice, we provide specialized forms of the resulting first-level RLT formulation for such mixed 0-1 and discrete convex programs, and illustrate these forms through two examples.     

RLT-POS: Reformulation-Linearization Technique-based optimization software for solving polynomial programming problems

In this paper, we introduce a Reformulation-Linearization Technique-based open-source optimization software for solving polynomial programming problems (RLT-POS). We present algorithms and mechanisms that form the backbone of RLT-POS, including constraint filtering techniques, reduced RLT representations, and semidefinite cuts. When implemented individually, each model enhancement has been shown in previous papers to significantly improve the performance of the standard RLT procedure. However, the coordination between different model enhancement techniques becomes critical for an improved overall performance since special structures in the original formulation that work in favor of a particular technique might be lost after implementing some other model enhancement. More specifically, we discuss the coordination between (1) constraint elimination via filtering techniques and reduced RLT representations, and (2) semidefinite cuts for sparse problems. We present computational results using instances from the literature as well as randomly generated problems to demonstrate the improvement over a standard RLT implementation and to compare the performances of the software packages BARON, COUENNE, and SparsePOP with RLT-POS.     

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 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.     

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.     

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.     

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.     

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.     

Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming

We consider relaxations for nonconvex quadratically constrained quadratic programming (QCQP) based on semidefinite programming (SDP) and the reformulation-linearization technique (RLT). From a theoretical standpoint we show that the addition of a semidefiniteness condition removes a substantial portion of the feasible region corresponding to product terms in the RLT relaxation. On test problems we show that the use of SDP and RLT constraints together can produce bounds that are substantially better than either technique used alone. For highly symmetric problems we also consider the effect of symmetry-breaking based on tightened bounds on variables and/or order constraints.     

Surrogate-RLT cuts for zero–one integer programs

In this paper, we consider the class of 0–1 integer problems and develop an effective cutting plane algorithm that gives valid inequalities called surrogate-RLT cuts (SR cuts). Here we implement the surrogate constraint analysis along with the reformulation–linearization technique (RLT) to generate strong valid inequalities. In this approach, we construct a tighter linear relaxation by augmenting SR cuts to the problem. The level-\(d\) SR closure of a 0–1 integer program is the polyhedron obtained by intersecting all the SR cuts obtained from RLT polyhedron formed over each set of \(d\) variables with its initial formulation. We present an algorithm for approximately optimizing over the SR closure. Finally, we present the computational result of SR cuts for solving 0–1 integer programming problems of well-known benchmark instances from MIPLIB 3.0.     

Theoretical filtering of RLT bound-factor constraints for solving polynomial programming problems to global optimality

In this paper, we propose two sets of theoretically filtered bound-factor constraints for constructing reformulation-linearization technique (RLT)-based linear programming (LP) relaxations for solving polynomial programming problems. We establish related theoretical results for convergence to a global optimum for these reduced sized relaxations, and provide insights into their relative sizes and tightness. Extensive computational results are provided to demonstrate the relative effectiveness of the proposed theoretical filtering strategies in comparison to the standard RLT and a prior heuristic filtering technique using problems from the literature as well as randomly generated test cases.     

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.     

Optimal designing of orthotropic cylindrical shells fastened to elastic filler

Conclusions A method has been proposed for optimally designing an orthotropic cylindrical shell rigidly fastened to an elastic and isotropic filler of finite dimensions. The design takes into account simultaneous action of pressure, body forces, and heat on the structure. The optimum design has been calculated for the case of temperature-dependent elastic properties and strength characteristics of the tape. The method allows also for limitation on the strength of the filler. The convergence of the iteration process schematically shown in Fig. 2 is quite fast. Indeed, for the given design variant, the condition of manufacturability (1) is satisfied with a sixfold margin in the third approximation (n=3) already.Translated from Mekhanika Kompozitnykh Materialov, No. 1, pp. 91–94, January–February, 1984.     

Inventory and investment in setup and quality operations under Return On Investment maximization

In this paper, we construct and analyze a Return On Investment (ROI) maximization model for inventory and capital investment in setup and quality operations under an investment budget constraint. Specifically, we show how such an ROI maximization model can be formulated and derive analytical results such as the conditions under which the inventory is reduced and for the determination of the unique global optimal solution. In addition, by applying the Reformulation-Linearization Technique (RLT), we show via numerical examples how this nonconvex optimization model can be solved effectively and how RLT may produce superior results to those from the conventional Cut Across the Board Rule (CABR). Various managerial insights are provided throughout the paper. For example, as the investment budget increases (or decreases), a fundamental shift of investment strategies (setup cost reduction vs. quality improvement) may be necessary so as to maximize ROI.