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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Solving Clique Partitioning Problems: A Comparison of Models and Commercial Solvers

引用

INTERNATIONAL JOURNAL OF INFORMATION TECHNOLOGY & DECISION MAKING 2022年第1期21卷 59-81页

作者： Du, Yu Kochenberger, Gary Glover, Fred Wang, Haibo Lewis, Mark Xie, Weihong Tsuyuguchi, Takeshi Univ Colorado Denver Denver CO 80204 USA Univ Colorado Boulder Boulder CO USA Texas A&M Int Univ Laredo TX USA Missouri State Univ Springfield MO USA Guangdong Univ Technol Guangzhou Peoples R China

Finding good solutions to clique partitioning problems remains a computational challenge. With rare exceptions, finding optimal solutions for all but small instances is not practically possible. However, choosing the most appropriate modeling structure can have a huge impact on what is practical to obtain from exact solvers within a reasonable amount of run time. Commercial solvers have improved tremendously in recent years and the combination of the right solver and the right model can significantly increase our ability to compute acceptable solutions to modest-sized problems with solvers like CPLEX, GUROBI and XPRESS. In this paper, we explore and compare the use of three commercial solvers on modest sized test problems for clique partitioning. For each problem instance, a conventional linear model from the literature and a relatively new quadratic model are compared. Extensive computational experience indicates that the quadratic model outperforms the classic linear model as problem size grows.

关键词： Clique partitioning combinatorial optimization quadratic integer programming

来源：评论

学校读者我要写书评

暂无评论

Global optimum economic designing of grid-connected photovoltaic systems with multiple inverters using binary linear programming

引用

SOLAR ENERGY 2019年第May期183卷 842-850页

作者： Bakhshi-Jafarabadi, Reza Sadeh, Javad Soheili, Adel Ferdowsi Univ Mashhad Elect Engn Dept Fac Engn Mashhad Razavi Khorasan Iran

Nowadays, grid-connected photovoltaic (GCPV) system is known as a top leading technology among all resources. However, it still suffers from drastic investment costs. Detailed economic studies should be conducted in this regard to make this technology as gainful as possible. A practical approach is the "optimum economic design", trying to find an electrically possible layout, i.e. number of series modules and parallel strings as well as the inverter number with the highest profit. This problem is inherently an quadratic integer programming owing to the multiplication of two integer variables in its objective function and some technical constraints. This nonlinear problem should be solved by exhaustive search methods, including comparative and evolutionary algorithms (EAs) such as particle swarm optimization (PSO) and genetic algorithm (GA). In this paper, a new formulation based on the definition of new binary variables has been proposed to convert this problem to the binary linear programming (BLP). The provided method finds the global optimum solution in a scale of seconds while EAs have to be run numerous times in a scale of hours to reach a sufficiently good answer. Moreover, although current methodologies are rarely covered GCPV systems with multiple inverter types, this formulation can be easily developed for systems with several inverter types. The simulations of a 1.1 MW power plant system endorse that the output design provided by the proposed method assures 95,000 $ (1.94%) higher profit compared with those presented by GA. The sensitivity analysis, provided for the prototype system by the efficient new algorithm, also unveils it is economically viable for even 52% of the current feed-in tariff, 40% energy generation lower than the estimated value and 1.1 $/W price rise for the initial investment.

关键词： Grid-connected photovoltaic system Optimum economic design quadratic integer programming Binary linear programming Global optimum solution

来源：评论

学校读者我要写书评

暂无评论

SDP-based branch-and-bound for non-convex quadratic integer optimization

引用

JOURNAL OF GLOBAL OPTIMIZATION 2019年第3期73卷 485-514页

作者： Buchheim, Christoph Montenegro, Maribel Wiegele, Angelika TU Dortmund Fak Math Vogelpothsweg 87 D-44227 Dortmund Germany Alpen Adria Univ Klagenfurt Univ Str 65-67 A-9020 Klagenfurt Austria

Semidefinite programming (SDP) relaxations have been intensively used for solving discrete quadratic optimization problems, in particular in the binary case. For the general non-convex integer case with box constraints, the branch-and-bound algorithm Q-MIST has been proposed by Buchheim and Wiegele (Math Program 141(1-2):435-452, 2013), which is based on an extension of the well-known SDP-relaxation for max-cut. For solving the resulting SDPs, Q-MIST uses an off-the-shelf interior point algorithm. In this paper, we present a tailored coordinate ascent algorithm for solving the dual problems of these SDPs. Building on related ideas of Dong(SIAM J Optim 26(3):1962-1985, 2016), it exploits the particular structure of the SDPs, most importantly a small rank of the constraint matrices. The latter allows both an exact line search and a fast incremental update of the inverse matrices involved, so that the entire algorithm can be implemented to run in quadratic time per iteration. Moreover, we describe how to extend this approach to a certain two-dimensional coordinate update. Finally, we explain how to include arbitrary linear constraints into this framework, and evaluate our algorithm experimentally.

关键词： quadratic integer programming Semidefinite programming Coordinate-wise optimization

来源：评论

学校读者我要写书评

暂无评论

Energy-optimal configuration selection for manycore chips with variation

引用

INTERNATIONAL JOURNAL OF HIGH PERFORMANCE COMPUTING APPLICATIONS 2017年第5期31卷 451-466页

作者： Langer, Akhil Totoni, Ehsan Palekar, Udatta Kale, Laxmikant V. Intel Fed 1906 Fox Dr Champaign IL 61820 USA Univ Illinois Coll Business Urbana IL 61801 USA Univ Illinois Dept Comp Sci 1304 W Springfield Ave Urbana IL 61801 USA

Operating chips at high energy efficiency is one of the major challenges for modern large-scale supercomputers. Low-voltage operation of transistors increases the energy efficiency but leads to frequency and power variation across cores on the same chip. Finding energy-optimal configurations for such chips is a hard problem. In this work, we study how integer linear programming techniques can be used to obtain energy-efficient configurations of chips that have heterogeneous cores. Our proposed methodologies give optimal configurations as compared with competent but sub-optimal heuristics while having negligible timing overhead. The proposed ParSearch method gives up to 13.2% and 7% savings in energy while causing only 2% increase in execution time of two HPC applications: miniMD and Jacobi, respectively. Our results show that integer linear programming can be a very powerful online method to obtain energy-optimal configurations.

关键词： energy power optimization multicore chips low-voltage computing near-threshold voltage computing process variation heterogeneity integer programming quadratic integer programming

来源：评论

学校读者我要写书评

暂无评论

quadratic cone cutting surfaces for quadratic programs with on-off constraints

引用

DISCRETE OPTIMIZATION 2017年 24卷 32-50页

作者： Jeon, Hyemin Linderoth, Jeff Miller, Andrew Univ Wisconsin Dept Ind & Syst Engn 1513 Univ Ave Madison WI 53706 USA UPS 55 Glenlake Pkwy Atlanta GA 30328 USA

We study the convex hull of a set arising as a relaxation of difficult convex mixed integer quadratic programs (MIQP). We characterize the extreme points of the convex hull of the set and the extreme points of its continuous relaxation. We derive four quadratic cutting surfaces that improve the strength of the continuous relaxation. Each of the cutting surfaces is second-order-cone representable. Via a shooting experiment, we provide empirical evidence as to the importance of each inequality type in improving the relaxation. Computational results that employ the new cutting surfaces to strengthen the relaxation for MIQPs arising from portfolio optimization applications are promising. (C) 2016 Elsevier B.V. All rights reserved.

关键词： quadratic integer programming Second-order cone relaxations Portfolio optimization

来源：评论

学校读者我要写书评

暂无评论

Matching Misaligned Two-Resolution Metrology Data

引用

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 2017年第1期14卷 222-237页

作者： Wang, Yaping Moreno-Centeno, Erick Ding, Yu Texas A&M Univ Dept Ind & Syst Engn College Stn TX 77843 USA

Multiresolution metrology devices coexist in today's manufacturing environment, producing coordinate measurements complementing each other. Typically, the high-resolution (HR) device produces a scarce but accurate data set, whereas the low-resolution (LR) one produces a dense but less accurate data set. Research has shown that combining the two data sets of different resolutions makes better predictions of the geometric features of a manufactured part. A challenge, however, is how to effectively match each HR data point to an LR counterpart that measures approximately the same physical location. A solution to this matching problem appears a prerequisite to a good final prediction. We solved this problem by formulating it as a quadratic integer program, aiming at minimizing the maximum interpoint distance difference among all potential correspondences. Due to the combinatorial nature of the optimization model, solving it to optimality is computationally prohibitive even for a small problem size. We therefore propose a two-stage matching framework capable of solving real-life-sized problems within a reasonable amount of time. This two-stage framework consists of downsampling the full-size problem, solving the downsampled problem to optimality, extending the solution of the downsampled problem to the full-size problem, and refining the solution using iterative local search. Numerical experiments show that the proposed approach outperforms two popular point set registration alternatives, the iterative closest point and coherent point drift methods, using different performance metrics. The numerical results also show that our approach scales much better as the instance size increases, and is robust to the changes in initial misalignment between the two data sets. Note to Practitioners-The central message of this paper is that aligning multiresolution data sets is important, but solving it turns out to be a nasty problem. If one throws it into an existing off-the-shelf op

关键词： Coherent point drift (CPD) coordinate measuring machine correspondences iterative closest point (ICP) quadratic integer programming rigid point set registration (RPSR) two-stage matching framework (TSMF)

来源：评论

学校读者我要写书评

暂无评论

A result on the Slope conjectures for 3-string Montesinos knots

引用

JOURNAL OF KNOT THEORY AND ITS RAMIFICATIONS 2018年第13期27卷

作者： Leng, Xudong Yang, Zhiqing Liu, Ximin Dalian Univ Technol Sch Math Sci Dalian 116024 Peoples R China

The Slope Conjecture and the Strong Slope Conjecture predict that the degree of the colored Jones polynomial of a knot is matched by the boundary slope and the Euler characteristic of some essential surfaces in the knot complement. By solving a problem of quadratic integer programming to find the maximal degree and using the Hatcher-Oertel edgepath system to find the corresponding essential surface, we verify the Slope Conjectures for a family of 3-string Montesinos knots satisfying certain conditions.

关键词： Slope conjecture colored Jones polynomial quadratic integer programming boundary slope incompressible surface

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：