Comparisons and enhancement strategies for linearizing mixed 0-1 quadratic programs

We present a linearization strategy for mixed 0-1 quadratic programs that produces small formulations with tight relaxations. It combines constructs from a classical method of Glover and a more recent reformulation-linearization technique (RLT). By using binary identities to rewrite the objective, a variant of the first method results in a concise formulation with the level-1 RLT strength. This variant is achieved as a modified surrogate dual of a Lagrangian subproblem to the RLT. Special structures can be exploited to obtain reductions in problem size, without forfeiting strength. Preliminary computational experience demonstrates the potential of the new representations.     

A duality theorem for semi-infinite convex programs and their finite subprograms

In this paper, we first establish a general recession condition under which a semi-infinite convex program and its formal lagrangian dual have the same value. We go on to show that, under this condition, the following hold. First, every finite subprogram, with ‘enough’ of the given constraints, has the same value as its Lagrangian dual. Second, the weak value of the primal program is equal to the optimal value of the primal. The first draft of this work, entitled ‘Asymptotic Convex Programming’ was completed while the author was a member of the Department of Mathematical Sciences at the University of Delaware, Newark, DE 19711.     

A recursive procedure to generate all cuts for 0–1 mixed integer programs

We study several ways of obtaining valid inequalities for mixed integer programs. We show how inequalities obtained from a disjunctive argument can be represented by superadditive functions and we show how the superadditive inequalities relate to Gomory's mixed integer cuts. We also show how all valid inequalities for mixed 0–1 programs can be generated recursively from a simple subclass of the disjunctive inequalities.The research of this author was supported by NSF Contract No. ECS-8540898.     

A new linearization technique for multi-quadratic 0-1 programming problems

We consider the reduction of multi-quadratic 0-1 programming problems to linear mixed 0-1 programming problems. In this reduction, the number of additional continuous variables is O(kn) (n is the number of initial 0-1 variables and k is the number of quadratic constraints). The number of 0-1 variables remains the same.     

An efficient linearization technique for mixed 0-1 polynomial problem

This paper addresses a new and efficient linearization technique to solve mixed 0-1 polynomial problems to achieve a global optimal solution. Given a mixed 0-1 polynomial term z=c_tx₁x₂…x_ny, where x₁,x₂,…,x_n are binary (0-1) variables and y is a continuous variable. Also, c_t can be either a positive or a negative parameter. We transform z into a set of auxiliary constraints which are linear and can be solved by exact methods such as branch and bound algorithms. For this purpose, we will introduce a method in which the number of additional constraints is decreased significantly rather than the previous methods proposed in the literature. As is known in any operations research problem decreasing the number of constraints leads to decreasing the mathematical computations, extensively. Thus, research on the reducing number of constraints in mathematical problems in complicated situations have high priority for decision makers. In this method, each n-auxiliary constraints proposed in the last method in the literature for the linearization problem will be replaced by only 3 novel constraints. In other words, previous methods were dependent on the number of 0-1 variables and therefore, one auxiliary constraint was considered per 0-1 variable, but this method is completely independent of the number of 0-1 variables and this illustrates the high performance of this method in computation considerations. The analysis of this method illustrates the efficiency of the proposed algorithm.     

A linearization framework for unconstrained quadratic (0-1) problems

In this paper, we are interested in linearization techniques for the exact solution of the Unconstrained Quadratic (0-1) Problem. Our purpose is to propose “economical” linear formulations. We first extend current techniques in a general linearization framework containing many other schemes and propose a new linear formulation. Numerical results comparing classical, Glover’s and the new linearization are reported.     

A lift-and-project cutting plane algorithm for mixed 0–1 programs

We propose a cutting plane algorithm for mixed 0–1 programs based on a family of polyhedra which strengthen the usual LP relaxation. We show how to generate a facet of a polyhedron in this family which is most violated by the current fractional point. This cut is found through the solution of a linear program that has about twice the size of the usual LP relaxation. A lifting step is used to reduce the size of the LP's needed to generate the cuts. An additional strengthening step suggested by Balas and Jeroslow is then applied. We report our computational experience with a preliminary version of the algorithm. This approach is related to the work of Balas on disjunctive programming, the matrix cone relaxations of Lovász and Schrijver and the hierarchy of relaxations of Sherali and Adams.The research underlying this report was supported by National Science Foundation Grant #DDM-8901495 and Office of Naval Research Contract N00014-85-K-0198.     

Lifted inequalities for 0-1 mixed integer programming: Basic theory and algorithms

We study the mixed 0-1 knapsack polytope, which is defined by a single knapsack constraint that contains 0-1 and bounded continuous variables. We develop a lifting theory for the continuous variables. In particular, we present a pseudo-polynomial algorithm for the sequential lifting of the continuous variables and we discuss its practical use.This research was supported by NSF grants DMI-0100020 and DMI-0121495Mathematics Subject Classification (2000): 90C11, 90C27     

Lifted inequalities for 0-1 mixed integer programming: Superlinear lifting

We study the mixed 0-1 knapsack polytope, which is defined by a single knapsack constraint that contains 0-1 and bounded continuous variables, through the lifting of continuous variables fixed at their upper bounds. We introduce the concept of a superlinear inequality and show that, in this case, lifting is significantly simpler than for general inequalities. We use the superlinearity theory, together with the traditional lifting of 0-1 variables, to describe families of facets of the mixed 0-1 knapsack polytope. Finally, we show that superlinearity results can be extended to nonsuperlinear inequalities when the coefficients of the variables fixed at their upper bounds are large.This research was supported by NSF grants DMI-0100020 and DMI-0121495Mathematics Subject Classification (1991): 90C11, 90C27     

A Tabu Search Algorithm for Quadratic 0—1 Programming Problem

1.IntroductionThemathematicalmodelofaquaduatico-1programmingproblemisasfollows:MinimizesubjecttwhereI,AsfaraspaperL1'2Jcanseemedel(I)(fordu=O)isveryimPOrtantinthemarshallingofsinglegrouptrainbetweenmarshallingstationsinrailwaynetworkandthemarshallingoftraininnetw0rkwiththetw0types0fvehiclefl0w,butproblem(I)isNP-C.C0nsiderarelax-ationproblemasf0llows:MinimizeIngeneral,solvingrelaxati0nproblemiseasierthansolvingcombinatiorial0ptimalpr0b-lem,thesameaslinearpr0grammingproblemissolvableinPOly…     

Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem

In this paper, we consider problem (P) of minimizing a quadratic function q(x)=x ^t Qx+c ^t x of binary variables. Our main idea is to use the recent Mixed Integer Quadratic Programming (MIQP) solvers. But, for this, we have to first convexify the objective function q(x). A classical trick is to raise up the diagonal entries of Q by a vector u until (Q+diag(u)) is positive semidefinite. Then, using the fact that x _i ²=x _i, we can obtain an equivalent convex objective function, which can then be handled by an MIQP solver. Hence, computing a suitable vector u constitutes a preprocessing phase in this exact solution method. We devise two different preprocessing methods. The first one is straightforward and consists in computing the smallest eigenvalue of Q. In the second method, vector u is obtained once a classical SDP relaxation of (P) is solved. We carry out computational tests using the generator of (Pardalos and Rodgers, 1990) and we compare our two solution methods to several other exact solution methods. Furthermore, we report computational results for the max-cut problem.     

Decomposition and Linearization for 0-1 Quadratic Programming

This paper presents a general decomposition method to compute bounds for constrained 0-1 quadratic programming. The best decomposition is found by using a Lagrangian decomposition of the problem. Moreover, in its simplest version this method is proved to give at least the bound obtained by the LP-relaxation of a non-trivial linearization. To illustrate this point, some computational results are given for the 0-1 quadratic knapsack problem.     

A class of polynomially solvable 0-1 programming problems and an application

It is well known that general 0-1 programming problems are NP-Complete and their optimal solutions cannot be found with polynomial-time algorithms unless P=NP. In this paper, we identify a specific class of 0-1 programming problems that is polynomially solvable, and propose two polynomial-time algorithms to find its optimal solutions. This class of 0-1 programming problems commits to a wide range of real-world industrial applications. We provide an instance of representative in the field of supply chain man...     

A multi-level search strategy for the 0-1 Multidimensional Knapsack Problem

We propose an exact method based on a multi-level search strategy for solving the 0-1 Multidimensional Knapsack Problem. Our search strategy is primarily based on the reduced costs of the non-basic variables of the LP-relaxation solution. Considering that the variables are sorted in decreasing order of their absolute reduced cost value, the top level branches of the search tree are enumerated following Resolution Search strategy, the middle level branches are enumerated following Branch & Bound strategy and the lower level branches are enumerated according to a simple Depth First Search enumeration strategy. Experimentally, this cooperative scheme is able to solve optimally large-scale strongly correlated 0-1 Multidimensional Knapsack Problem instances. The optimal values of all the 10 constraint, 500 variable instances and some of the 30 constraint, 250 variable instances of the OR-Library were found. These values were previously unknown.     

基于DNA链置换与荧光标记的0-1规划问题的计算模型

DNA链置换技术和荧光标记是近年生物计算领域的新兴的方法,并且因为它们都有着操作简单的优势而成为DNA计算的常用方法.DNA自组装算法是以DNA分子作为数据存储和运算的一种新型计算模式.为了提高算法的特异性和检测的灵敏度,在自组装算法的基础上,首次将DNA链置换技术和荧光标记结合引入到自组装模型中,提出了一个解决0-1规划问题的DNA计算新模型.与以往DNA计算模型相比,该模型提高了运算的可靠性和准确性,而且可以逐步缩小解空间,降低运算的复杂度,同时也使检测的方法更加灵活,易于引入到其他自组装算法模型中.     

0-1线性规划的连续化及其遗传算法解法

将0-1离散规划通过一个非线性等式约束表示为[0,1]区间上等价的连续变量非线性规划列式.对非线性等式约束的问题进行了两种方法的处理.第一种方法使用乘子法,第二种方法将非线性的等式约束近似为一个非线性的不等式约束,均利用遗传算法程序GENOCOP进行了求解.对多个算例进行了计算,结果表明了该方法的可行性和有效性.     

Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method

Let be a 0-1 quadratic program which consists in minimizing a quadratic function subject to linear equality constraints. In this paper, we present QCR, a general method to reformulate into an equivalent 0-1 program with a convex quadratic objective function. The reformulated problem can then be efficiently solved by a classical branch-and-bound algorithm, based on continuous relaxation. This idea is already present in the literature and used in standard solvers such as CPLEX. Our objective in this work was to find a convex reformulation whose continuous relaxation bound is, moreover, as tight as possible. From this point of view, we show that QCR is optimal in a certain sense. State-of-the-art reformulation methods mainly operate a perturbation of the diagonal terms and are valid for any {0,1} vector. The innovation of QCR comes from the fact that the reformulation also uses the equality constraints and is valid on the feasible solution domain only. Hence, the superiority of QCR holds by construction. However, reformulation by QCR requires the solution of a semidefinite program which can be costly from the running time point of view. We carry out a computational experience on three different combinatorial optimization problems showing that the costly computational time of reformulation by QCR can however result in a drastically more efficient branch-and-bound phase. Moreover, our new approach is competitive with very specific methods applied to particular optimization problems.     

A theoretical and empirical investigation on the Lagrangian capacities of the 0-1 multidimensional knapsack problem

We present a novel Lagrangian method to find good feasible solutions in theoretical and empirical aspects. After investigating the concept of Lagrangian capacity, which is the value of the capacity constraint that Lagrangian relaxation can find an optimal solution, we formally reintroduce Lagrangian capacity suitable to the 0-1 multidimensional knapsack problem and present its new geometric equivalent condition including a new associated property. Based on the property, we propose a new Lagrangian heuristic that finds high-quality feasible solutions of the 0-1 multidimensional knapsack problem. We verify the advantage of the proposed heuristic by experiments. We make comparisons with existing Lagrangian approaches on benchmark data and show that the proposed method performs well on large-scale data.     

Finding general and explicit solutions (2 + 1) dimensional Broer-Kaup-Kupershmidt system nonlinear equation by exp-function method

In this work, we implement a relatively new analytical technique, the exp-function method, for solving nonlinear special form of generalized nonlinear (2 + 1) dimensional Broer-Kaup-Kupershmidt equation, which may contain high nonlinear terms. This method can be used as an alternative to obtain analytic and approximate solutions of different types of fractional differential equations which applied in engineering mathematics. Some numerical examples are presented to illustrate the efficiency and reliability of exp method. It is predicted that exp-function method can be found widely applicable in engineering.     

A generalized extended rational expansion method and its application to (1 + 1)-dimensional dispersive long wave equation

In this Letter, a generalized extended rational expansion method is used to construct exact solutions of the (1 + 1)-dimensional dispersive long wave equation. As a result, many new and more general exact solutions are obtained, the solutions obtained in this Letter include rational triangular periodic wave solutions, rational solitary wave solutions.