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

Large-Scale binary quadratic optimization Using SemidefiniteRelaxation and Applications

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2017年第3期39卷 470-485页

作者： Wang, Peng Shen, Chunhua van den Hengel, Anton Torr, Philip H. S. Univ Adelaide Adelaide SA Australia Univ Adelaide Sch Comp Sci Adelaide SA Australia Univ Adelaide Australian Ctr Visual Technol Adelaide SA Australia Univ Oxford Robot Res Grp Oxford England

In computer vision, many problems can be formulated as binary quadratic programs (BQPs), which are in general NP hard. Finding a solution when the problem is of large size to be of practical interest typically requires relaxation. Semidefinite relaxation usually yields tight bounds, but its computational complexity is high. In this work, we present a semidefinite programming (SDP) formulation for BQPs, with two desirable properties. First, it produces similar bounds to the standard SDP formulation. Second, compared with the conventional SDP formulation, the proposed SDP formulation leads to a considerably more efficient and scalable dual optimization approach. We then propose two solvers, namely, quasi-Newton and smoothing Newton methods, for the simplified dual problem. Both of them are significantly more efficient than standard interior-point methods. Empirically the smoothing Newton solver is faster than the quasi-Newton solver for dense or medium-sized problems, while the quasi-Newton solver is preferable for large sparse/structured problems.

关键词： binary quadratic optimization semidefinite programming Markov random fields

来源：评论

学校读者我要写书评

暂无评论

Exact Facetial Odd-Cycle Separation for Maximum Cut and binary quadratic optimization

引用

INFORMS JOURNAL ON COMPUTING 2021年第4期33卷 1419-1430页

作者： Juenger, Michael Mallach, Sven Univ Cologne Dept Math & Comp Sci D-50932 Cologne Germany Univ Bonn High Performance Comp & Analyt Lab D-53115 Bonn Germany

The exact solution of the NP-hard (nondeterministic polynomial-time hard) maximum cut problem is important in many applications across, for example, physics, chemistry, neuroscience, and circuit layout-which is also due to its equivalence to the unconstrained binary quadratic optimization problem. Leading solution methods are based on linear or semidefinite programming and require the separation of the so-called odd-cycle inequalities. In their groundbreaking research, F. Barahona and A. R. Mahjoub have given an informal description of a polynomial-time algorithm for this problem. As pointed out recently, however, additional effort is necessary to guarantee that the inequalities obtained correspond to facets of the cut polytope. In this paper, we shed more light on a so enhanced separation procedure and investigate experimentally how it performs in comparison with an ideal setting where one could even employ the sparsest, most violated, or geometrically most promising facet-defining odd-cycle inequalities. Summary of Contribution: This paper aims at a better capability to solve binary quadratic optimization or maximum cut problems and their various applications using integer programming techniques. To this end, the paper describes enhancements to a well-known algorithm for the central separation problem arising in this context;it is demonstrated experimentally that these enhancements are worthwhile from a computational point of view. The linear relaxations of the aforementioned problems are typically solved using fewer iterations and cutting planes than with a nonenhanced approach. It is also shown that the enhanced procedure is only slightly inferior to an ideal, enumerative, and, in practice, intractable global cutting-plane selection.

关键词： maximum cut binary quadratic optimization integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Multistart tabu search strategies for the unconstrained binary quadratic optimization problem

引用

ANNALS OF OPERATIONS RESEARCH 2004年第1-4期131卷 259-282页

作者： Palubeckis, G Kaunas Univ Technol Dept Pract Informat LT-3031 Kaunas Lithuania

This paper describes and experimentally compares five rather different multistart tabu search strategies for the unconstrained binary quadratic optimization problem: a random restart procedure, an application of a deterministic heuristic to specially constructed subproblems, an application of a randomized procedure to the full problem, a constructive procedure using tabu search adaptive memory, and an approach based on solving perturbed problems. In the solution improvement phase a modification of a standard tabu search implementation is used. A computational trick applied to this modification-mapping of the current solution to the zero vector-allowed to significantly reduce the time complexity of the search. Computational results are provided for the 25 largest problem instances from the OR-Library and, in addition, for the 18 randomly generated larger and more dense problems. For 9 instances from the OR-Library new best solutions were found.

关键词： binary quadratic optimization tabu search multistart strategies heuristics

来源：评论

学校读者我要写书评

暂无评论

A binary quadratic optimization Model for Three Level Supply Chain Design

A Binary Quadratic Optimization Model for Three Level Supply...

引用

47th CIRP Conference on Manufacturing Systems

作者： Ashtab, Sahand Caron, Richard J. Selvarajah, Esaignani Univ Windsor Dept Ind & Mfg Syst Engn Windsor ON N9B 3P4 Canada Univ Windsor Dept Math & Stat Windsor ON N9B 3P4 Canada Univ Windsor Dept Management Sci Windsor ON N9B 3P4 Canada

We present a binary quadratic optimization model for multi-capacitated three-level supply chain design including suppliers, distribution centers (DCs), and customer zones. Our model considers DC land, building and variable costs, and takes into account economies of scale. It is the inclusion of variable costs that makes the model quadratic. We present a series of model simplifications that allow for the solution of the model. We demonstrate the effectiveness of our model and model simplifications through the design of a real-world supply chain with 47 suppliers at fixed locations, 83 potential DCs and 2,976 fixed customer zones. (C) 2014 Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://***/licenses/by-nc-nd/3.0/).

关键词： Supply chain design binary quadratic optimization

来源：评论

学校读者我要写书评

暂无评论

Odd-Cycle Separation for Maximum Cut and binary quadratic optimization 27

Odd-Cycle Separation for Maximum Cut and Binary Quadratic Op...

引用

27th Annual European Symposium on Algorithms (ESA)

作者： Juenger, Michael Mallach, Sven Univ Cologne Cologne Germany

ISBN: (纸本)9783959771245

Solving the NP-hard Maximum Cut or binary quadratic optimization Problem to optimality is important in many applications including Physics, Chemistry, Neuroscience, and Circuit Layout. The leading approaches based on linear/semidefinite programming require the separation of so-called odd-cycle inequalities for solving relaxations within their associated branch-and-cut frameworks. In their groundbreaking work, F. Barahona and A.R. Mahjoub have given an informal description of a polynomial-time separation procedure for the odd-cycle inequalities. Since then, the odd-cycle separation problem has broadly been considered solved. However, as we reveal, a straightforward implementation is likely to generate inequalities that are not facet-defining and have further undesired properties. Here, we present a more detailed analysis, along with enhancements to overcome the associated issues efficiently. In a corresponding experimental study, it turns out that these are worthwhile, and may speed up the solution process significantly.

关键词： Maximum cut binary quadratic optimization Integer linear programming

来源：评论

学校读者我要写书评

暂无评论

A binary quadratic optimization Model for Three Level Supply Chain Design

引用

Procedia CIRP 2014年 17卷 635-638页

作者： Sahand Ashtab Richard J. Caron Esaignani Selvarajah Department of Industrial and Manufacturing Systems Engineering University of Windsor Windsor Ontario N9B 3P4 Canada Department of Mathematics and Statistics University of Windsor Windsor Ontario N9B 3P4 Canada Department of Management Science University of Windsor Windsor Ontario N9B 3P4 Canada

关键词： Supply chain design binary quadratic optimization

来源：评论

学校读者我要写书评

暂无评论

quadratic Unconstrained binary optimization Problem Preprocessing: Theory and Empirical Analysis

引用

NETWORKS 2017年第2期70卷 79-97页

作者： Lewis, Mark Glover, Fred Missouri Western State Univ Sch Business St Joseph MO 64507 USA Univ Colorado Sch Sci & Engn Boulder CO 80309 USA

The quadratic Unconstrained binary optimization problem (QUBO) has become a unifying model for representing a wide range of combinatorial optimization problems, and for linking a variety of disciplines that face these problems. A new class of quantum annealing computer that maps QUBO onto a physical qubit network structure with specific size and edge density restrictions is generating a growing interest in ways to transform the underlying QUBO structure into an equivalent graph having fewer nodes and edges. In this article, we present rules for reducing the size of the QUBO matrix by identifying variables whose value at optimality can be predetermined. We verify that the reductions improve both solution quality and time to solution and, in the case of metaheuristic methods where optimal solutions cannot be guaranteed, the quality of solutions obtained within reasonable time limits. We discuss the general QUBO structural characteristics that can take advantage of these reduction techniques and perform careful experimental design and analysis to identify and quantify the specific characteristics most affecting reduction. The rules make it possible to dramatically improve solution times on a new set of problems using both the exact Cplex solver and a tabu search metaheuristic. (C) 2017 Wiley Periodicals, Inc.

关键词： quadratic unconstrained binary optimization binary quadratic optimization preprocessing network reduction Ising model quantum annealing

来源：评论

学校读者我要写书评

暂无评论

ON THE COMPLEXITY OF LOCAL SEARCH IN UNCONSTRAINED quadratic binary optimization

引用

SIAM JOURNAL ON optimization 2016年第2期26卷 1257-1261页

作者： Papp, David North Carolina State Univ Dept Math Box 8205 Raleigh NC 27695 USA

We consider the problem of finding a local minimum of a binary quadratic function and show by an elementary construction that every descending local search algorithm takes exponential time in the worst case.

关键词： local optimization binary quadratic optimization exponential complexity

来源：评论

学校读者我要写书评

暂无评论

Conic optimization: A survey with special focus on copositive optimization and binary quadratic problems

引用

EURO JOURNAL ON COMPUTATIONAL optimization 2021年 9卷

作者： Duer, Mirjam Rendl, Franz Augsburg Univ Dept Math D-86135 Augsburg Germany Alpen Adria Univ Klagenfurt Dept Math A-9020 Klagenfurt Austria

A conic optimization problem is a problem involving a constraint that the optimization variable be in some closed convex cone. Prominent examples are linear programs (LP), second order cone programs (SOCP), semidefinite problems (SDP), and copositive problems. We survey recent progress made in this area. In particular, we highlight the connections between nonconvex quadratic problems, binary quadratic problems, and copositive optimization. We review how tight bounds can be obtained by relaxing the copositivity constraint to semidefiniteness, and we discuss the effect that different modelling techniques have on the quality of the bounds. We also provide some new techniques for lifting linear constraints and show how these can be used for stable set and coloring relaxations.

关键词： Semidefinite programming Second order cone programming Copositive optimization binary quadratic optimization

来源：评论

学校读者我要写书评

暂无评论

quadratic Combinatorial optimization Using Separable Underestimators

引用

INFORMS JOURNAL ON COMPUTING 2018年第3期30卷 424-437页

作者： Buchheim, Christoph Traversi, Emiliano Tech Univ Dortmund Fak Math D-44227 Dortmund Germany Univ Paris 13 Lab Informat Paris Nord F-93430 Villetaneuse France

binary programs with a quadratic objective function are NP-hard in general, even if the linear optimization problem over the same feasible set is tractable. In this paper, we address such problems by computing quadratic global underestimators of the objective function that are separable but not necessarily convex. Exploiting the binary constraint on the variables, a minimizer of the separable underestimator over the feasible set can be computed by solving an appropriate linear minimization problem over the same feasible set. Embedding the resulting lower bounds into a branch-and-bound framework, we obtain an exact algorithm for the original quadratic binary program. The main practical challenge is the fast computation of an appropriate underestimator, which in our approach reduces to solving a series of semidefinite programs. We exploit the special structure of the resulting problems to obtain a tailored coordinate-descent method for their solution. Our extensive experimental results on various quadratic combinatorial optimization problems show that our approach outperforms both CPLEX and the related QCR method as well as the SDP-based software BiqCrunch on instances of the quadratic shortest path problem and the quadratic assignment problem.

关键词： binary quadratic optimization separable underestimators quadratic shortest path problem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：