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

Proximity in concave integer quadratic programming

MATHEMATICAL programming 2022年第1-2期194卷 871-900页

作者： Del Pia, Alberto Ma, Mingchen Univ Wisconsin Dept Ind & Syst Engn Madison WI USA Univ Wisconsin Wisconsin Inst Discovery Madison WI USA Univ Wisconsin Dept Comp Sci Madison WI 53706 USA

A classic result by Cook, Gerards, Schrijver, and Tardos provides an upper bound of n Delta on the proximity of optimal solutions of an integer Linear programming problem and its standard linear relaxation. In this bound, n is the number of variables and Delta denotes the maximum of the absolute values of the subdeterminants of the constraint matrix. Hochbaum and Shanthikumar, and Werman and Magagnosc showed that the same upper bound is valid if a more general convex function is minimized, instead of a linear function. No proximity result of this type is known when the objective function is nonconvex. In fact, if we minimize a concave quadratic, no upper bound can be given as a function of n and Delta. Our key observation is that, in this setting, proximity phenomena still occur, but only if we consider also approximate solutions instead of optimal solutions only. In our main result we provide upper bounds on the distance between approximate (resp., optimal) solutions to a Concave integer quadratic programming problem and optimal (resp., approximate) solutions of its continuous relaxation. Our bounds are functions of n, Delta, and a parameter epsilon that controls the quality of the approximation. Furthermore, we discuss how far from optimal are our proximity bounds.

关键词： integer quadratic programming quadratic programming Concave minimization Proximity Sensitivity subdeterminants

来源：评论

学校读者我要写书评

暂无评论

EXACT AUGMENTED LAGRANGIAN DUALITY FOR MIXED integer quadratic programming

引用

SIAM JOURNAL ON OPTIMIZATION 2020年第1期30卷 781-797页

作者： Gu, Xiaoyi Ahmed, Shabbir Dey, Santanu S. Georgia Inst Technol H Milton Stewart Sch Ind & Syst Engn Atlanta GA 30332 USA

Mixed integer quadratic programming (MIQP) is the problem of minimizing a quadratic function over mixed integer points in a rational polyhedron. This paper focuses on the augmented Lagrangian dual (ALD) for MIQP. ALD augments the usual Lagrangian dual with a weighted nonlinear penalty on the dualized constraints. We first prove that ALD will reach a zero duality gap asymptotically as the weight on the penalty goes to infinity under some mild conditions on the penalty function. We next show that a finite penalty weight is enough for a zero gap when we use any norm as the penalty function. Finally, we prove a polynomial bound on the weight on the penalty term to obtain a zero gap.

关键词： augmented Lagrangian integer quadratic programming strong dual

来源：评论

学校读者我要写书评

暂无评论

SUBDETERMINANTS AND CONCAVE integer quadratic programming

引用

SIAM JOURNAL ON OPTIMIZATION 2019年第4期29卷 3154-3173页

作者： Del Pia, Alberto Univ Wisconsin Dept Ind & Syst Engn Madison WI 53706 USA Univ Wisconsin Wisconsin Inst Discovery Madison WI 53706 USA

We consider the NP-hard problem of minimizing a separable concave quadratic function over the integral points in a polyhedron, and we denote by Delta the largest absolute value of the subdeterminants of the constraint matrix. In this paper we give an algorithm that finds an epsilon-approximate solution for this problem by solving a number of integer linear programs whose constraint matrices have subdeterminants bounded by Delta in absolute value. The number of these integer linear programs is polynomial in the dimension n, in Delta, and in 1/epsilon, provided that the number k of variables that appear nonlinearly in the objective is fixed. As a corollary, we obtain the first polynomial-time approximation algorithm for separable concave integer quadratic programming with Delta <= 2 and k fixed. In the totally unimodular case Delta = 1, we give an improved algorithm that only needs to solve a number of linear programs that is polynomial in 1/epsilon and is independent of n, provided that k is fixed.

关键词： integer quadratic programming approximation algorithm concave function subdeterminants total unimodularity total bimodularity

来源：评论

学校读者我要写书评

暂无评论

Computing efficient exact designs of experiments using integer quadratic programming

引用

COMPUTATIONAL STATISTICS & DATA ANALYSIS 2014年 71卷 1159-1167页

作者： Harman, Radoslav Filova, Lenka Comenius Univ Fac Math Phys & Informat Dept Appl Math & Stat Bratislava 84248 Slovakia

A new method for computing exact experimental designs for linear regression models by integer quadratic programming is proposed. The key idea is to use the criterion of DQ-optimality, which is a quadratic approximation of the criterion of D-optimality in the neighbourhood of the approximate D-optimal information matrix. Several numerical examples are used to demonstrate that the D-efficiency of exact DQ-optimal designs is usually very high. An important advantage of this method is that it can be applied to situations with general linear constraints on permissible designs, including marginal and cost constraints. (C) 2013 Elsevier B.V. All rights reserved.

关键词： D-optimal design DQ-optimal design Exact design Marginal constraints Cost constraints integer quadratic programming

来源：评论

学校读者我要写书评

暂无评论

Alignment of Protein-Protein Interfaces by integer quadratic programming

Alignment of Protein-Protein Interfaces by Integer Quadratic...

引用

2012 International Conference on Convergence Computer Technology(IC3T 2012)

作者： Wen-Juan Zhang Lin Wang Department of Basic Courses Tianjin Foreign Studies University Tianjin China Computer Science and Information Engineering College Tianjin University of Science and Technology

Alignment of protein-protein interfaces plays a key role in the studies of protein function,signal transduction network and drug *** give a protein-protein interface alignment method which is based on an integer quadratic programming *** alignment method integrates sequence evolutionary information and structural information of proteins,and scores the aligned residues using the similarity of their evolutionary ***,we use the alignment method to identify evolutionally and structurally conserved *** the computational experiments,we show that those evolutionally and structurally conserved residues are likely to be the key residues for protein-protein interaction,*** spots.

关键词： Protein interface alignment Hot spot integer quadratic programming

来源：评论

学校读者我要写书评

暂无评论

Parameterized algorithms for minimum sum vertex cover

引用

THEORETICAL COMPUTER SCIENCE 2025年 1029卷

作者： Aute, Shubhada Panolan, Fahad Indian Inst Technol Hyderabad Sangareddy India Univ Leeds Sch Comp Sci Leeds England

A minimum sum vertex cover of an n-vertex graph G is a bijection : V(G)->[] that minimizes the cost ex) min ($(u). $()). Finding a minimum sum vertex cover of a graph (the MSVC problem) is NP-hard. MSVC is studied well in the realm of approximation algorithms. The best- known approximation factor in polynomial time for the problem is 16/9 [Bansal, Batra, Farhadi, and Tetali, SODA 2021]. Recently, Stankovic [APPROX/RANDOM 2022) proved that achieving an approximation ratio better than 1.014 for MSVC is NP-hard, assuming the Unique Games Conjecture. We study the MSVC problem from the perspective of parameterized algorithms. The parameters consider are the size of a minimum vertex cover and the size of a minimum clique modulator of the input graph. We obtain the following results. MSVC can be solved in 2000) time, where k is the size of a minimum vertex cover. MSVC can be solved in (k) time for some computable function, where k is the size of a minimum clique modulator.

关键词： FPT Vertex cover integer quadratic programming

来源：评论

学校读者我要写书评

暂无评论

The edge-preservation similarity for comparing rooted, unordered, node-labeled trees*

引用

PATTERN RECOGNITION LETTERS 2023年第1期167卷 189-195页

作者： Boria, Nicolas Kiederle, Jana Yger, Florian Blumenthal, David B. PSL Univ Univ Paris Dauphine LAMSADE CNRSUMR7243 Paris France Friedrich Alexander Univ Erlangen Nurnberg Dept Artificial Intelligence Biomed Engn Biomed Network Sci Lab Erlangen Germany Normandie Univ GREYC CNRS ENSICAENUMR 6072 Caen France

Rooted trees are ubiquitous data structures which are used to model hierarchical objects from a plethora of different application domains. For various downstream analysis tasks, measures are needed that quan-tify (dis-)similarity between rooted trees. Many such measures exist, e. g., the widely used tree edit dis-tance (TED). However, there are few algorithms to compute (dis-)similarity measures which are specifi-cally designed for rooted, unordered, node-labeled trees and support input trees of different orders. To close this gap in the literature, we introduce the edge-preservation similarity (EPS). We show how to exactly compute EPS via integer quadratic programming on small instances and present a scalable 4-approximation algorithm. An evaluation on tree representations of pseudoknotted RNA secondary struc-tures and acyclic molecular graphs shows that both exact and approximate (normalized) EPS better preserves functional similarities between the compared RNAs and molecules than the often-used TED. Python implementations of our algorithms and scripts to reproduce the results are available on GitHub: https://***/bionetslab/edge-preservation-similarity . (c) 2023 Elsevier B.V. All rights reserved.

关键词： Tree similarity measures integer quadratic programming Approximation algorithms RNA secondary structures

来源：评论

学校读者我要写书评

暂无评论

Norm-optimal iterative learning control in an integer-valued control domain

引用

INTERNATIONAL JOURNAL OF CONTROL 2023年第1期96卷 170-181页

作者： Arnold, Florian King, Rudibert Tech Univ Berlin Chair Measurement & Control Dept Proc Engn Str 17 Juni 135 D-10623 Berlin Germany

Formulating a control design for integer-valued inputs might be advantageous over, for example, rounding strategies based on a real-valued solution. However, the speed of convergence, computational cost, and stability are challenges to be addressed. This is especially true for optimisation-based approaches such as the norm-optimal iterative learning control (ILC). In this contribution, the convergence properties of integer-valued ILC are derived and compared against the known real-valued ILC. After an evaluation of two recently presented solutions, a new optimal set controller synthesis method for integer-valued norm-optimal ILC is presented. The approach guarantees monotonic convergence and ensures that each iteration of the ILC will require a deterministic computational effort to find the suboptimal solution, with an upper bound for the objective function of the optimisation. This deterministic computational effort makes the setup applicable for real-time implementation. Finally, an example using the introduced new approach is given to highlight its advantages.

关键词： Iterative learning control constrained control integer quadratic programming

来源：评论

学校读者我要写书评

暂无评论

Parameterized Algorithms for Minimum Sum Vertex Cover 16th

Parameterized Algorithms for Minimum Sum Vertex Cover

引用

16th Latin American Symposium on Theoretical Informatics (LATIN)

作者： Aute, Shubhada Panolan, Fahad Indian Inst Technol Hyderabad Sangareddy India Univ Leeds Sch Comp Leeds W Yorkshire England

ISBN: (纸本)9783031556005;9783031556012

Minimum sum vertex cover of an n-vertex graph G is a bijection phi : V (G) -> [n] that minimizes the cost Sigma({u,v}is an element of E(G)) min{phi(u), phi(v)}. Finding a minimum sum vertex cover of a graph (the MSVC problem) is NP-hard. MSVC is studied well in the realm of approximation algorithms. The best-known approximation factor in polynomial time for the problem is 16/9 [Bansal, Batra, Farhadi, and Tetali, SODA 2021]. Recently, Stankovic [APPROX/RANDOM 2022] proved that achieving an approximation ratio better than 1.014 for MSVC is NP-hard, assuming the Unique Games Conjecture. We study the MSVC problem from the perspective of parameterized algorithms. The parameters we consider are the size of a minimum vertex cover and the size of a minimum clique modulator of the input graph. We obtain the following results. - MSVC can be solved in 2(2O(k)) n(O(1)) time, where k is the size of a minimum vertex cover. - MSVC can be solved in f(k) . n(O(1)) time for some computable function f, where k is the size of a minimum clique modulator.

关键词： FPT Vertex Cover integer quadratic programming

来源：评论

学校读者我要写书评

暂无评论

A semidefinite programming method for integer convex quadratic minimization

引用

OPTIMIZATION LETTERS 2018年第3期12卷 499-518页

作者： Park, Jaehyun Boyd, Stephen Stanford Univ Packard BldgRoom 243350 Serra Mall Stanford CA 94305 USA Stanford Univ Packard BldgRoom 254350 Serra Mall Stanford CA 94305 USA

We consider the NP-hard problem of minimizing a convex quadratic function over the integer lattice Zn. We present a simple semidefinite programming (SDP) relaxation for obtaining a nontrivial lower bound on the optimal value of the problem. By interpreting the solution to the SDP relaxation probabilistically, we obtain a randomized algorithm for finding good suboptimal solutions, and thus an upper bound on the optimal value. The effectiveness of the method is shown for numerical problem instances of various sizes.

关键词： Convex optimization integer quadratic programming Mixed-integer programming Semidefinite relaxation Branch-and-bound

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：