求非凸二次约束二次规划问题全局解的线性化方法

1引言 考虑如下非凸二次规划的全局优化问题: (QP):{min xTQox doTx,s.t.xTQix ditx≤bi,i=1,…,m,x∈S={x∈Rn:l≤x≤u}, 其中Qo,Qi是n阶实对称矩阵,do,di∈Rn,bi∈R,i=1,…,m;l=(l1,…,ln)T,u=(u1,…,un)T .     

一种新的二次约束二次规划问题的分支定界算法

本文为了获得二次约束二次规划(QCQP)问题的全局最优解,提出一种新的参数化线性松弛分支定界算法.该算法利用参数化线性松弛技术,得到(QCQP)的全局最小值的下界,并利用区域缩减技术以最大限度地删除不可行区域,加快该算法的收敛速度.数值实验表明,本文提出的算法是有效并且可行的.     

一种求解二次约束二次规划问题的自适应全局优化算法

为了更好地解决二次约束二次规划问题(QCQP), 本文基于分支定界算法框架提出了自适应线性松弛技术, 在理论上证明了这种新的定界技术对于解决(QCQP)是可观的。文中分支操作采用条件二分法便于对矩形进行有效剖分; 通过缩减技术删除不包含全局最优解的部分区域, 以加快算法的收敛速度。最后, 通过数值结果表明提出的算法是有效可行的。     

一种求解二次约束二次规划问题的自适应全局优化算法

为了更好地解决二次约束二次规划问题(QCQP), 本文基于分支定界算法框架提出了自适应线性松弛技术, 在理论上证明了这种新的定界技术对于解决(QCQP)是可观的。文中分支操作采用条件二分法便于对矩形进行有效剖分; 通过缩减技术删除不包含全局最优解的部分区域, 以加快算法的收敛速度。最后, 通过数值结果表明提出的算法是有效可行的。     

求0-1型整数规划的一种新方法

本文给出求 0 -1型整数规划的一种新方法 ,该方法利用对所有目标函数值排序的方法 ,求出最优解 .该方法简单易行且计算量较小     

混合整数二次规划问题的全局最优性条件

本文给出了混合整数二次规划问题的全局最优性条件,包括全局最优充分性条件和全局最优必要性条件.我们还给出了一个数值实例用以说明如何利用本文所给出的全局最优性条件来判定一个给定点是否是全局最优解.     

线性约束0-1二次规划的一个定界技术

本文给出确定线性约束0－1二次规划问题最优值下界的方法,该方法结合McBride和Yormark的思想和总体优化中定下界的方法,证明了所定的界较McBride和Yormark的要好．求解线性约束0－1二次规划问题的分支定界算法可以利用本文的定界技术．     

求解带二次约束的非凸二次规划的一种分支定界算法

本文提出了一种求解带二次约束和线性约束的二次规划的分支定界算法.在算法中,我们运用Lipschitz条件来确定目标函数和约束函数的在每个n矩形上的上下界,对于n矩形的分割,我们采用选择n矩形最长边的二分法,同时我们采用了一些矩形删除技术,在不大幅增加计算量的前提下,起到了加速算法收敛的效果.从理论上我们证明了算法的收敛性,同时数值实验表明该算法是有效的.     

二次规划的一种简易算法

本文对二次规划的单纯形算法，从算法到收敛条件均加以改进，得到更简易的程序和收敛准则。     

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.     

关于二层规划最优解新定义的几点注解

文献[2]提出了二层规划解的新定义,同时指出新定义能够解决更广泛的线性二层规划问题,并且如果线性二层规划的约束域为非空紧集,那么线性二层规划问题就存在Pareto最优解.本文用两个线性二层规划的例子说明文献[2]得出的结论是不可靠的,同时还分析了两种定义下的线性二层规划诱导域之间的关系.     

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     

一种基于协同信息的团队伙伴选择方法

针对基于协同信息的团队伙伴选择问题,提出了一种决策分析方法。首先,给出了伙伴间的协同关系及基于协同信息的团队伙伴选择问题的描述;然后,构建了基于协同信息的团队伙伴选择的数学模型,该模型属于0-1二次整数规划问题,也是NP-hard问题,为了求解该问题,简要阐述了将0-1二次整数规划问题转化为0-1线性整数规划问题的方法;最后,通过一个实例分析说明了本文提出方法的可行性和有效性。     

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.     

可再生能源系统的不确定性优化模型及求解

结合新提出的满意度方法和混合整数规划方法,给出了多态不确定性环境下可再生能源规划模型.该模型综合描述了多地区、多时期、多品种、多部门之间的可再生能源管理系统的复杂性、系统性、动态性和不确定性.最后的实例求解结果说明该模型能很好地反映能源安全性、系统可靠性与系统成本之间的关系,并能给出不同系统违反水平下的能源配置方式及增容计划,为决策者提供决策参考.     

On Two-Point Boundary Conditions in Optimal Control Problems

Let x=g(t,x(t),u(t)) be the governing equation of an optimal control problem with two-point boundary conditions h ₀(x(a))+h ₁(x(b)) = 0, where x: [a,b] ⁿ is continuous, u: [a,b] ^k-n is piecewise continuous and left continuous, h₀,h₁: ^{n q} are continuously differentiable, and g:[a,b]× ^{k n} is continuous. The paper finds functions _i C¹([a,b]× ⁿ ) such that (x(t),u(t)) is a solution of the governing equation if and only if

求解整数规划的单参数填充函数

本文给出了一个新的求解离散全局最优化问题的单参数填充函数,并给出了一个新的算法,同时给出了对几个测试问题的数据计算结果.     

Regulation of Overlaps in Technology Development Activities

In this paper, we present an algorithm for the solution of multiparametric mixed integer linear programming (mp-MILP) problems involving (i) 0-1 integer variables, and, (ii) more than one parameter, bounded between lower and upper bounds, present on the right hand side (RHS) of constraints. The solution is approached by decomposing the mp-MILP into two subproblems and then iterating between them. The first subproblem is obtained by fixing integer variables, resulting in a multiparametric linear programming (mp-LP) problem, whereas the second subproblem is formulated as a mixed integer linear programming (MILP) problem by relaxing the parameters as variables.