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 Global Optimization Approach to a Water Distribution Network Design Problem

In this paper, we address a global optimization approach to a waterdistribution network design problem. Traditionally, a variety of localoptimization schemes have been developed for such problems, each new methoddiscovering improved solutions for some standard test problems, with noknown lower bound to test the quality of the solutions obtained. A notableexception is a recent paper by Eiger et al. (1994) who present a firstglobal optimization approach for a loop and path-based formulation of thisproblem, using a semi-infinite linear program to derive lower bounds. Incontrast, we employ an arc-based formulation that is linear except forcertain complicating head-loss constraints and develop a first globaloptimization scheme for this model. Our lower bounds are derived through thedesign of a suitable Reformulation-Linearization Technique (RLT) thatconstructs a tight linear programming relaxation for the given problem, andthis is embedded within a branch-and-bound algorithm. Convergence to anoptimal solution is induced by coordinating this process with an appropriatepartitioning scheme. Some preliminary computational experience is providedon two versions of a particular standard test problem for the literature forwhich an even further improved solution is discovered, but one that isverified for the first time to be an optimum, without any assumed boundson the flows. Two other variants of this problem are also solved exactly forillustrative purposes and to provide researchers with additional test caseshaving known optimal solutions. Suggestions on a more elaborate study involving several algorithmic enhancements are presented for futureresearch.     

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.     

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.     

Improved compact linearizations for the unconstrained quadratic 0-1 minimization problem

We present and compare three new compact linearizations for the quadratic 0-1 minimization problem, two of which achieve the same lower bound as does the “standard linearization”. Two of the linearizations require the same number of constraints with respect to Glover’s one, while the last one requires n additional constraints where n is the number of variables in the quadratic 0-1 problem. All three linearizations require the same number of additional variables as does Glover’s linearization. This is an improvement on the linearization of Adams, Forrester and Glover (2004) which requires n additional variables and 2n additional constraints to reach the same lower bound as does the standard linearization. Computational results show however that linearizations achieving a weaker lower bound at the root node have better global performances than stronger linearizations when solved by Cplex.     

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

混合 0-1 线性规划问题的一个代理约束定界方法

本文给出混合０－１线性规划问题的一个代理约束定界方法,利用代理约束构造一个定界函数,计算量较小,并提出一个分支定界算法,数值计算表明算法是有效的．     

求解0-1线性整数规划问题的有界单纯形法

提出了一种求解0-1线性整数规划问题的有界单纯形法, 不仅通过数学论证, 讨论了该方法的合理性, 奠定了其数学理论基础, 而且通过求解无容量设施选址问题, 验证了该方法的可行性. 在此基础上, 就该有界单纯形法的不足和存在的问题, 给出了进一步改进的途径和手段.     

Reoptimizing the 0-1 knapsack problem

In this paper we study the problem where an optimal solution of a knapsack problem on n items is known and a very small number k of new items arrive. The objective is to find an optimal solution of the knapsack problem with n+k items, given an optimal solution on the n items (reoptimization of the knapsack problem). We show that this problem, even in the case k=1, is NP-hard and that, in order to have effective heuristics, it is necessary to consider not only the items included in the previously optimal solution and the new items, but also the discarded items. Then, we design a general algorithm that makes use, for the solution of a subproblem, of an α-approximation algorithm known for the knapsack problem. We prove that this algorithm has a worst-case performance bound of , which is always greater than α, and therefore that this algorithm always outperforms the corresponding α-approximation algorithm applied from scratch on the n+k items. We show that this bound is tight when the classical Ext-Greedy algorithm and the algorithm are used to solve the subproblem. We also show that there exist classes of instances on which the running time of the reoptimization algorithm is smaller than the running time of an equivalent PTAS and FPTAS.     

与0-1二次规划问题等价的连续问题(英)

在较一般的条件下，证明了线性约束0-1二次规划问题等价于一个凹二次规划问题，改进了已有的结果．     

Untersuchungen zu speziellen linearen gemischt-ganzzahligen 0-1-optimierungsaufgaben

In this paper criteria for solution of a linear mixed-integer 0-1-programming -problem with one restriction and any coefficients in the objective function respectively in the restriction are given. Under certain conditions the given problem can be reduced to a mixed-integer problem of a special structure. An algorithm to solve this problem is described concisely.     

求解多维0-1背包问题的人工鱼群算法

对于多维0-1背包问题,国内外学者提出了诸如模拟退火、遗传算法、蚁群算法以及其他启发式算法.给出一种新的智能寻优方法——人工鱼群算法.算法通过各人工鱼的局部寻优,从而在群体中体现出全局最优.描述了人工鱼群算法的具体步骤并编程实现,通过多维背包算例进行了求解测试,获得了满意的效果.     

Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts

A generalized Davenport-Schinzel sequence is one over a finite alphabet whose subsequences are not isomorphic to a forbidden subsequence σ. What is the maximum length of such a σ-free sequence, as a function of its alphabet size n? Is the extremal function linear or nonlinear? And what characteristics of σ determine the answers to these questions? It is known that such sequences have length at most n⋅²(α(n))^O(1), where α is the inverse-Ackermann function and the O(1) depends on σ.We resolve a number of open problems on the extremal properties of generalized Davenport-Schinzel sequences. Among our results:

1.

We give a nearly complete characterization of linear and nonlinear σ∈^?{a,b,c} over a three-letter alphabet. Specifically, the only repetition-free minimally nonlinear forbidden sequences are ababa and abcacbc.

2.

We prove there are at least four minimally nonlinear forbidden sequences.

3.

We prove that in many cases, doubling a forbidden sequence has no significant effect on its extremal function. For example, Nivasch?s upper bounds on alternating sequences of the form t(ab) and t(ab)a, for t?3, can be extended to forbidden sequences of the form t(aabb) and t(aabb)a.

4.

Finally, we show that the absence of simple subsequences in σ tells us nothing about σ?s extremal function. For example, for any t, there exists a σt avoiding ababa whose extremal function is Ω(n⋅²αt(n)).

Most of our results are obtained by translating questions about generalized Davenport-Schinzel sequences into questions about the density of 0-1 matrices avoiding certain forbidden submatrices. We give new and often tight bounds on the extremal functions of numerous forbidden 0-1 matrices.     

编组站调度计划0-1规划法

针对货车编组问题,采用半分离式两阶段0-1线性规划模型对各阶段联合求解,对局部最优解采用调度时序图可视化表述.首先,对无、有调车辆分离,无调车采用启发式安排.有调车推峰顺序可以转化为零件加工问题,以驼峰总工作量最大、等待时间最小为目标建立模型I.列车解体时间与解体方向数成正比增长,但在未确定具体解体方案时无法确定(即模型I的独立),通过在模型II中对解体时间模糊化来处理两步独立的缺陷,从而达到两步规划的连续特性.车辆新编,决策变量属于多维结构,通过将多维稀疏变量转化为一维序列,有效解除其稀疏特性,形成二维决策变量建立规划模型II直接求解.其次,通过仿真创建模拟数据,运用主模型求解,得到了驼峰是编组站主要瓶颈的结论.最后,我们还对铁路资源的紧缺性、编组效率建模给出了较详细改进措施.     

求解0-1背包问题的细菌觅食算法

0-1背包问题是组合优化中的一个典型NP难题,介于其具有广泛的实际应用,有效的解决该问题具有非常重要的意义.给出了一种新的群智能算法—细菌觅食算法,对0-1背包问题进行求解.经模拟仿真验证了该算法的有效性,并将其结果与其他方法进行对比分析.     

On trees with a maximum proper partial 0-1 coloring containing a maximum matching

I prove that in a tree in which the distance between any two endpoints is even, there is a maximum proper partial 0-1 coloring such that the edges colored by 0 form a maximum matching.     

Testing optimality for quadratic 0-1 problems

Received June 4, 1996 / Revised version received November 19, 1997 Published online November 24, 1998     

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.