检索结果-内蒙古大学图书馆

quadratic integer programming with application to the chaotic mappings of complete multipartite graphs

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2001年第3期110卷 545-556页

作者： Fu, HL Shiue, CL Cheng, X Du, DZ Kim, JM Natl Chiao Thung Univ Dept Appl Math Hsinchu Taiwan Natl Tsing Hua Univ Natl Ctr Theoret Sci Div Math Hsinchu Taiwan Univ Minnesota Dept Comp Sci & Engn Minneapolis MN USA Chinese Acad Sci Inst Appl Math Beijing Peoples R China

Let a be a permutation of the vertex set V(G) of a connected graph G. Define the total relative displacement of alpha in G by [GRAPHIC] where d(G) (x, y) is the length of the shortest path between x and y in G. Let pi*(G) be the maximum value of delta (alpha)(G) among all permutations of V(G). The permutation which realizes pi*(G) is called a chaotic mapping of G. In this paper, we study the chaotic mappings of complete multipartite graphs. The problem is reduced to a quadratic integer programming problem. We characterize its optimal solution and present an algorithm running in O(n(5) log n) time, where n is the total number of vertices in a complete multipartite graph.

关键词： chaotic mapping complete multipartite graph quadratic integer programming optimal solution

来源：评论

学校读者我要写书评

暂无评论

ELLIPSOID BOUNDS FOR CONVEX quadratic integer programming

引用

SIAM JOURNAL ON OPTIMIZATION 2015年第2期25卷 741-769页

作者： Buchheim, Christoph Huebner, Ruth Schoebel, Anita Tech Univ Dortmund Fac Math D-44221 Dortmund Germany Univ Gottingen Insitute Numer & Appl Math D-37073 Gottingen Germany

Solving convex quadratic integer minimization problems by a branch-and-bound algorithm requires tight lower bounds on the optimal objective value. To obtain such dual bounds, we follow the approach of [C. Buchheim, A. Caprara, and A. Lodi, Math. Program., 135 (2012), pp. 369-395] and underestimate the objective function by another convex quadratic function that can be minimized over the integers by simply rounding its continuous minimizer. In geometric terms, we approximate the sublevel sets of the original objective function by auxiliary ellipsoids having the strong rounding property, introduced by [R. Hubner and A. Schobel, European J. Oper. Res., 237 (2014), pp. 404-410]. We first consider axisparallel ellipsoids (corresponding to separable convex quadratic functions) and show how to efficiently compute an axisparallel ellipsoid yielding the tightest lower bound, both in the situation where the location of the continuous minimizer is given and in the situation where it varies, as it happens in a branch-and-bound approach. In the latter case, we compute both worst-case and average-case optimal ellipsoids. Moreover, we consider the class of quasi-round ellipsoids (from Hubner and Schobel). In this case, we do not know whether optimal auxiliary ellipsoids can be computed efficiently. However, we present a heuristic for computing an appropriate quasi-round ellipsoid that still yields valid dual bounds;it turns out that using this approach within a branch-and-bound scheme outperforms the approaches based on axisparallel ellipsoid in terms of running times. We finally combine both approaches by introducing the concept of quasi-axisparallel ellipsoids and present a corresponding extension of the heuristic bound computation.

关键词： quadratic integer programming ellipsoidal approximation branch-and-bound

来源：评论

学校读者我要写书评

暂无评论

On the gap between the quadratic integer programming problem and its semidefinite relaxation

引用

MATHEMATICAL programming 2006年第3期107卷 505-515页

作者： Malik, U Jaimoukha, IM Halikias, GD Gungah, SK Univ London Imperial Coll Sci Technol & Med Dept Elect & Elect Engn Control & Power Grp London SW7 2BT England City Univ London Sch Engn & Math Sci London EC1V 0HB England

Consider the semidefinite relaxation (SDR) of the quadratic integer program (QIP): gamma := max {x(T) Qx : x is an element of {-1, 1}(n)} . Thus we show that 'breaching' the SDR gap for the QIP problem is as d... 详细信息

Consider the semidefinite relaxation (SDR) of the quadratic integer program (QIP): gamma := max {x(T) Qx : x is an element of {-1, 1}(n)} <= min {trace(D) : D - Q greater than or similar to 0} =: (gamma) over bar where Q is a given symmetric matrix and D is diagonal. We consider the SDR gap (gamma) over bar gamma. We establish the uniqueness of the SDR solution and prove that gamma = (gamma) over bar if and only if gamma(r) := n(-1) max {x(T) VVT x : x is an element of {-1, 1}(n)} = 1 where V is an orthogonal matrix whose columns span the (r - dimensional) null space of D - Q and where D is the unique SDR solution. We also give a test for establishing whether gamma = (gamma) over bar that involves 2(r-1) function evaluations. In the case that gamma(r) < 1 we derive an upper bound on gamma which is tighter than <(gamma)over bar>. Thus we show that 'breaching' the SDR gap for the QIP problem is as difficult as the solution of a QIP with the rank of the cost function matrix equal to the dimension of the null space of D - Q. This reduced rank QIP problem has been recently shown to be solvable in polynomial time for fixed r.

关键词： quadratic integer programming semidefinite relaxation linear matrix inequalities zonotopes hyperplane arrangements

来源：评论

学校读者我要写书评

暂无评论

A new algorithm for quadratic integer programming problems with cardinality constraint

引用

JAPAN JOURNAL OF INDUSTRIAL AND APPLIED MATHEMATICS 2020年第2期37卷 449-460页

作者： Wang, Fenlan Cao, Liyuan Nanjing Univ Aeronaut & Astronaut Coll Sci 29 Yudao St Nanjing 210016 Peoples R China Lehigh Univ Ind & Syst Engn Dept Bethlehem PA 18015 USA

quadratic integer programming problems with cardinality constraint have many applications in real life. Portfolio selection is an important application in financial optimization. In this paper we develop an exact and efficient algorithm for quadratic integer programming problems with cardinality constraint. This iterative algorithm is actually a branch and bound method, which adopts a domain cut and partition scheme. Removing cardinality constraint and integrality constraints on variables, the relaxation problem is a quadratic programming problem. By solving the quadratic programming problem, we find a lower bound for the optimal objective function value of the primal problem. The domain cut technique is used to cut off some regions that do not contain any feasible solution better than the incumbent solution. Thus the optimality gap is reduced greatly. The finite number of iterations is clear from the fact that there are only a finite number of feasible integer solutions in the feasible region. Encouraging computational results are also reported in the paper.

关键词： quadratic integer programming Cardinality constraint Domain cut Optimality gap 90C10 90C20 90C30

来源：评论

学校读者我要写书评

暂无评论

Global optimization techniques for solving the general quadratic integer programming problem

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 1998年第2期10卷 149-163页

作者： Thoai, NV Univ Trier Dept Math D-54286 Trier Germany

We consider the problem of minimizing a general quadratic function over a polytope in the n-dimensional space with integrality restrictions on all of the variables. (This class of problems contains, e.g., the quadratic 0-1 program as a special case.) A finite branch and bound algorithm is established, in which the branching procedure is the so-called "integral rectangular partition", and the bound estimation is performed by solving a concave programming problem with a special structure. Three methods for solving this special concave program are proposed.

关键词： quadratic integer programming branch and bound algorithms concave minimization global optimization

来源：评论

学校读者我要写书评

暂无评论

New bounds on the unconstrained quadratic integer programming problem

引用

JOURNAL OF GLOBAL OPTIMIZATION 2007年第4期39卷 543-554页

作者： Halikias, G. D. Jaimoukha, I. M. Malik, U. Gungah, S. K. Univ London Imperial Coll Sci Technol & Med Dept Elect & Elect Engn Control & Power Grp London SW7 2BT England City Univ London Sch Engn & Math Sci London EC1V 0HB England

We consider the maximization T gamma = max{x(T)Ax : x. {- 1, 1}(n)} for a given symmetric A epsilon R-n x n. It was shown recently, using properties of zonotopes and hyperplane arrangements, that in the special case that A has a small rank, so that A = VVT where V epsilon R-nxm with m < n, then there exists a polynomial time algorithm ( polynomial in n for a given m) to solve the problem max{x(T)VV(T) x : x epsilon {-1,1}(n)}. In this paper, we use this result, as well as a spectral decomposition of A to obtain a sequence of non-increasing upper bounds on gamma with no constraints on the rank of A. We also give easily computable necessary and sufficient conditions for the absence of a gap between the solution and its upper bound. Finally, we incorporate the semidefinite relaxation upper bound into our scheme and give an illustrative example.

关键词： quadratic integer programming semidefinite relaxation zonotope hyperplane arrangements

来源：评论

学校读者我要写书评

暂无评论

ON SIMULTANEOUS APPROXIMATION IN quadratic integer programming

引用

OPERATIONS RESEARCH LETTERS 1989年第5期8卷 251-255页

作者： GRANOT, F SKORINKAPOV, J SUNY STONY BROOK WA HARRIMAN SCH MANAGEMENT & POLICYSTONY BROOKNY 11794

It is shown how to replace the objective function of an integer quadratic programming problem by an integer objective function whose size is polynomially bounded by the number of variables and the size of the constraints, without changing the set of optimal solutions. The Frank and Tardos' algorithm [1] is used which in turn uses the simultaneous approximation algorithm of Lenstra et al. [4]. This preprocessing algorithm assures that the running time of any algorithm for solving integer quadratic programming problems can be made independent of the size of the objective function coefficients.

关键词： quadratic integer programming simultaneous approximation

来源：评论

学校读者我要写书评

暂无评论

Extensions on ellipsoid bounds for quadratic integer programming

引用

JOURNAL OF GLOBAL OPTIMIZATION 2018年第3期71卷 457-482页

作者： Fampa, Marcia Pinillos Nieto, Francisco Univ Fed Rio de Janeiro Rio De Janeiro Brazil

Ellipsoid bounds for strictly convex quadratic integer programs have been proposed in the literature. The idea is to underestimate the strictly convex quadratic objective function q of the problem by another convex quadratic function with the same continuous minimizer as q and for which an integer minimizer can be easily computed. We initially propose in this paper a different way of constructing the quadratic underestimator for the same problem and then extend the idea to other quadratic integer problems, where the objective function is convex (not strictly convex), and where the objective function is nonconvex and box constraints are introduced. The quality of the bounds proposed is evaluated experimentally and compared to the related existing methodologies.

关键词： quadratic integer programming Ellipsoid bound integer relaxation

来源：评论

学校读者我要写书评

暂无评论

Separable Relaxation for Nonconvex quadratic integer programming: integer Diagonalization Approach

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2010年第2期146卷 463-489页

作者： Zheng, X. J. Sun, X. L. Li, D. Chinese Univ Hong Kong Dept Syst Engn & Engn Management Shatin Hong Kong Peoples R China Shanghai Univ Dept Math Shanghai 200444 Peoples R China Fudan Univ Sch Management Dept Management Sci Shanghai 200433 Peoples R China

We present in this paper an integer diagonalization approach for deriving new lower bounds for general quadratic integer programming problems. More specifically, we introduce a semiunimodular transformation in order to diagonalize a symmetric matrix and preserve integral property of the feasible set at the same time. Via the semiunimodular transformation, the resulting separable quadratic integer program is a relaxation of the nonseparable quadratic integer program. We further define the integer diagonalization dual problem to identify the best semiunimodular transformation and analyze some basic properties of the set of semiunimodular transformations for a rational symmetric matrix. In particular, we present a complete characterization of the set of all semiunimodular transformations for a nonsingular 2x2 symmetric matrix. We finally discuss Lagrangian relaxation and convex relaxation schemes for the resulting separable quadratic integer programming problem and compare the tightness of different relaxation schemes.

关键词： quadratic integer programming Separable relaxation Semiunimodular congruence transformation Lagrangian relaxation Convex relaxation

来源：评论

学校读者我要写书评

暂无评论

AN IMPLICIT ENUMERATION ALGORITHM FOR quadratic integer programming

引用

MANAGEMENT SCIENCE 1980年第3期26卷 282-296页

作者： MCBRIDE, RD YORMARK, JS

We present an implicit enumeration algorithm for a nonseparable quadratic integer programming problem. We utilize fathoming criteria derived from Lemke's complementary pivot algorithm, and compare the use of pseud... 详细信息

关键词： quadratic integer programming

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：