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

Revisiting the linear programming relaxation Approach to Gibbs Energy Minimization and Weighted Constraint Satisfaction

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2010年第8期32卷 1474-1488页

作者： Werner, Tomas Czech Tech Univ Dept Cybernet Prague 12135 Czech Republic

We present a number of contributions to the LP relaxation approach to weighted constraint satisfaction (= Gibbs energy minimization). We link this approach to many works from constraint programming, which relation has so far been ignored in machine vision and learning. While the approach has been mostly considered only for binary constraints, we generalize it to n-ary constraints in a simple and natural way. This includes a simple algorithm to minimize the LP-based upper bound, n-ary max-sum diffusion-however, we consider using other bound-optimizing algorithms as well. The diffusion iteration is tractable for a certain class of high-arity constraints represented as a black box, which is analogical to propagators for global constraints CSP. Diffusion exactly solves permuted n-ary supermodular problems. A hierarchy of gradually tighter LP relaxations is obtained simply by adding various zero constraints and coupling them in various ways to existing constraints. Zero constraints can be added incrementally, which leads to a cutting-plane algorithm. The separation problem is formulated as finding an unsatisfiable subproblem of a CSP.

关键词： Weighted constraint satisfaction Gibbs distribution graphical model Markov random field linear programming relaxation marginal polytope cut polytope cutting-plane algorithm global constraint supermodularity tree-reweighted max-product

来源：评论

学校读者我要写书评

暂无评论

Piecewise linear Valued CSPs Solvable by linear programming relaxation

引用

ACM TRANSACTIONS ON COMPUTATIONAL LOGIC 2022年第1期23卷 1-35页

作者： Bodirsky, Manuel Mamino, Marcello Viola, Caterina Tech Univ Dresden Inst Algebra D-01062 Dresden Germany Univ Pisa Dipartimento Matemat I-56127 Pisa Italy Univ Oxford Dept Comp Sci Oxford OX1 3QD England

Valued constraint satisfaction problems (VCSPs) are a large class of combinatorial optimisation problems. The computational complexity of VCSPs depends on the set of allowed cost functions in the input. Recently, the computational complexity of all VCSPs for finite sets of cost functions over finite domains has been classified. Many natural optimisation problems, however, cannot be formulated as VCSPs over a finite domain. We initiate the systematic investigation of the complexity of infinite-domain VCSPs with piecewise linear homogeneous cost functions. Such VCSPs can be solved in polynomial time if the cost functions are improved by fully symmetric fractional operations of all arities. We showthis by reducing the problem to a finite-domain VCSP which can be solved using the basic linear program relaxation. It follows that VCSPs for submodular PLH cost functions can be solved in polynomial time;in fact, we show that submodular PLH functions form a maximally tractable class of PLH cost functions.

关键词： Valued constraint satisfaction rational domain linear programming relaxation piecewise linear functions submodularity

来源：评论

学校读者我要写书评

暂无评论

A linear programming relaxation Based Approach for Generating Barrier Certificates of Hybrid Systems 21st

A Linear Programming Relaxation Based Approach for Generatin...

引用

21st International Symposium on Formal Methods (FM)

作者： Yang, Zhengfeng Huang, Chao Chen, Xin Lin, Wang Liu, Zhiming East China Normal Univ Shanghai Key Lab Trustworthy Comp Shanghai Peoples R China Nanjing Univ State Key Lab Novel Software Technol Nanjing Jiangsu Peoples R China Chinese Acad Sci AMSS Key Lab Math Mech Beijing Peoples R China Southwest Univ Ctr Res & Innovat Software Engn Chongqing Peoples R China

ISBN: (纸本)9783319489896;9783319489889

This paper presents a linear programming (LP) relaxation based approach for generating polynomial barrier certificates for safety verification of semi-algebraic hybrid systems. The key idea is to introduce an LP relaxation to encode the set of nonnegativity constraints derived from the conditions of the associated barrier certificates and then resort to LP solvers to find the solutions. The most important benefit of the LP relaxation based approach is that it possesses a much lower computational complexity and hence can be solved very efficiently, which is demonstrated by the theoretical analysis on complexity as well as the experiment on a set of examples gathered from the literature. As far as we know, it is the first method that enables LP relaxation based polynomial barrier certificate generation.

关键词： Formal verification Hybrid systems Barrier certificates linear programming relaxation

来源：评论

学校读者我要写书评

暂无评论

Fast Koopman Surrogate Falsification Using linear relaxations and Weights 22nd

Fast Koopman Surrogate Falsification Using Linear Relaxation...

引用

22nd International Symposium on Automated Technology for Verification and Analysis

作者： Bak, Stanley Hekal, Abdelrahman Kochdumper, Niklas Lew, Ethan Mata, Andrew Rahmati, Amir SUNY Stony Brook Dept Comp Sci Stony Brook NY USA Newcastle Univ Sch Comp Newcastle Upon Tyne Tyne & Wear England Newcastle Univ Sch Comp Newcastle Upon Tyne Tyne & Wear England Univ Paris Cite CNRS IRIF F-75013 Paris France Galois Inc Portland OR USA

ISBN: (纸本)9783031787492;9783031787508

Recent work demonstrated that using Koopman surrogate models to falsify black-box models against signal temporal logic specifications is highly effective. However, the bottleneck of this approach arises from the mixed-integer linear program optimization used to synthesize the falsifying trajectory. The complexity of mixed-integer linear programming can be prohibitive, increasing exponentially with the number of binary variables. In this work, we introduce a new weighted robustness encoding that eliminates the need for binary variables. We also propose a new weighting scheme for Koopman operator linearization that aims to compensate for inaccuracies in the learned model. We evaluate our approach using a set of benchmarks from the ARCH falsification competition. Our weighting methods significantly improve computational efficiency and reduce the number of simulations needed to find falsifying traces.

关键词： Cyber-physical systems signal temporal logic falsification Koopman operator linearization linear programming relaxation

来源：评论

学校读者我要写书评

暂无评论

linear programming relaxations and marginal productivity index policies for the buffer sharing problem

引用

QUEUEING SYSTEMS 2008年第3-4期60卷 247-269页

作者： Cao, Jianhua Nyberg, Christian Lund Univ Elect & Informat Technol Dept S-22100 Lund Sweden

We study the dynamic admission control for a finite shared buffer with support of multiclass traffic under Markovian assumptions. The problem is often referred to as buffer sharing in the literature. From the linear programming (LP) formulation of the continuous-time Markov decision process (MDP), we construct a hierarchy of increasingly stronger LP relaxations where the hierarchy levels equal the number of job classes. Each relaxation in the hierarchy is obtained by projecting the original achievable performance region onto a polytope of simpler structure. We propose a heuristic policy for admission control, which is based on the theory of Marginal Productivity Index (MPI) and the Lagrangian decomposition of the first order LP relaxation. The dual of the relaxed buffer space constraint in the first order LP relaxation is used as a proxy to the cost of buffer space. Given that each of the decomposed queueing admission control problems satisfies the indexability condition, the proposed heuristic accepts a new arrival if there is enough buffer space left and the MPI of the current job class is greater than the incurred cost of buffer usage. Our numerical examples for the cases of two and eight job classes show the near-optimal performance of the proposed MPI heuristic.

关键词： Buffer sharing problem Multi-class queueing system linear programming relaxation Marginal productivity index policy Markov decision process 60K25 60K30 68M20 90B05 90B22 90B18 90C08 90C40 90C59

来源：评论

学校读者我要写书评

暂无评论

Approximation Algorithms and linear programming relaxations for Scheduling Problems Related to Min-Sum Set Cover

引用

MATHEMATICS OF OPERATIONS RESEARCH 2024年第1期49卷 578-599页

作者： Happach, Felix Schulz, Andreas S. Tech Univ Munich Sch Computat Informat & Technol Operat Res Grp D-80333 Munich Germany Tech Univ Munich Sch Management Operat Res Grp D-80333 Munich Germany

We consider single-machine scheduling problems that are natural generalizations or variations of the min-sum set-cover problem. For these scheduling problems, we give new approximation algorithms. Some of these algorithms rely on time-indexed linear programming relaxations. We show how a variant of alpha-point scheduling leads to the best known approximation ratios, including a guarantee of four for an interesting special case of the so-called generalized min-sum set-cover problem. We also make explicit the connection between the greedy algorithm for min-sum set cover and the concept of Sidney decomposition for precedence-constrained single-machine scheduling and show how this leads to a 4-approximation algorithm for single-machine scheduling with so-called bipartite OR-precedence constraints.

关键词： scheduling precedence constraints min-sum set cover linear programming relaxation approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Iterative learning for optimal residential load scheduling in smart grid

引用

AD HOC NETWORKS 2016年第May期41卷 99-111页

作者： Chai, Bo Yang, Zaiyue Gao, Kunlun Zhao, Ting State Grid Smart Grid Res Inst Beijing 102211 Peoples R China Zhejiang Univ State Key Lab Ind Control Technol Hangzhou 310027 Zhejiang Peoples R China

In this paper, as a fundamental problem in smart grid, the residential load scheduling is studied in a comprehensive way. The main contributions lie in threefold. First, three indices, i.e., the power consumption expense, the robustness of schedule subject to uncertain electricity price and the satisfaction of customer, are taken into full consideration. We propose to optimize simultaneously the three indices via convex optimization. Second, iterative learning is utilized to setting parameters in the objective function, and keeps a proper tradeoff between the consumption expense and the satisfaction index. Third, in order to fully characterize the operation states of appliances, both binary and continuous variables are used, which results in a hybrid mixed-integer quadratic optimization problem. The relaxation technique is utilized to tackle the hybrid optimization problem. Theoretical analysis of the performance gap based on the proposed approach is provided as well. The performance of the proposed approach is illustrated by simulations. The parameter settings reflect actual preference and consumption manner of the consumer. In addition, both peak-to-average ratio of power load and variation of power load are reduced. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Smart grid Residential load scheduling Iterative learning Real time price Price uncertainty linear programming relaxation

来源：评论

学校读者我要写书评

暂无评论

Solving project scheduling problems by minimum cut computations

引用

MANAGEMENT SCIENCE 2003年第3期49卷 330-350页

作者： Möhring, RH Schulz, AS Stork, F Uetz, M Tech Univ Berlin Fak 2 Inst Math D-10623 Berlin Germany MIT Alfred P Sloan Sch Management Cambridge MA 02139 USA ILOG Deutschland GmbH D-61352 Bad Homburg Germany Univ Limburg Fac Econ & Business Adm NL-6200 MD Maastricht Netherlands

In project scheduling, a set of precedence-constrained jobs has to be scheduled so as to minimize a given objective. In resource-constrained project scheduling, the jobs additionally compete for scarce resources. Due to its universality, the latter problem has a variety of applications in manufacturing, production planning, project management, and elsewhere. It is one of the most intractable problems in operations research, and has therefore become a popular playground for the latest optimization techniques, including virtually all local search paradigms. We show that a somewhat more classical mathematical programming approach leads to both competitive feasible solutions and strong lower bounds, within reasonable computation times. The basic ingredients of our approach are the Lagrangian relaxation of a time-indexed integer programming formulation and relaxation-based list scheduling, enriched with a useful idea from recent approximation algorithms for machine scheduling problems. The efficiency of the algorithm results from the insight that the relaxed problem can be solved by computing a minimum cut in an appropriately defined directed graph. Our computational study covers different types of resource-constrained project scheduling problems, based on several notoriously hard test sets, including practical problem instances from chemical production planning.

关键词： project scheduling resource constraints linear programming relaxation Lagrangian relaxation minimum cut

来源：评论

学校读者我要写书评

暂无评论

INTEGRALITY RATIO FOR GROUP STEINER TREES AND DIRECTED STEINER TREES

引用

SIAM JOURNAL ON COMPUTING 2007年第5期36卷 1494-1511页

作者： Halperin, Eran Kortsarz, Guy Krauthgamer, Robert Srinivasan, Aravind Wang, Nan Int Comp Sci Inst Berkeley CA 94704 USA Univ Calif Berkeley Div Comp Sci Berkeley CA 94720 USA Rutgers State Univ Dept Comp Sci Camden NJ 08102 USA IBM Almaden Res Ctr San Jose CA 95120 USA Univ Maryland Dept Comp Sci College Pk MD 20742 USA Univ Maryland Inst Adv Comp Studies College Pk MD 20742 USA Morgan Stanley Inc New York NY 10020 USA

The natural relaxation for the group Steiner tree problem, as well as for its generalization, the directed Steiner tree problem, is a flow-based linear programming relaxation. We prove new lower bounds on the integrality ratio of this relaxation. For the group Steiner tree problem, we show that the integrality ratio is Omega(log(2) k), where k denotes the number of groups;this holds even for input graphs that are hierarchically well-separated trees, introduced by Bartal [in Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, 1996, pp. 184-193], in which case this lower bound is tight. This also applies for the directed Steiner tree problem. In terms of the number n of vertices, our results for the directed Steiner problem imply an Omega(log(2) n/(log log n)(2)) integrality ratio. For both problems, these are the first lower bounds on the integrality ratio that are superlogarithmic in the input size. This exhibits, for the first time, a relaxation of a natural optimization problem whose integrality ratio is known to be superlogarithmic but subpolynomial. Our results and techniques have been used by Halperin and Krauthgamer [in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 585-594] to show comparable inapproximability results, assuming that NP has no quasi-polynomial Las Vegas algorithms. We also show algorithmically that the integrality ratio for the group Steiner tree problem is much better for certain families of instances, which helps pinpoint the types of instances (parametrized by optimal solutions to their flow-based relaxations) that appear to be most difficult to approximate.

关键词： group Steiner tree directed Steiner tree flow-based relaxation linear programming relaxation integrality ratio approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

The multi-resource agent bottleneck generalised assignment problem

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2012年第2期50卷 309-324页

作者： Karsu, Ozlem Azizoglu, Meral Middle E Tech Univ Dept Ind Engn TR-06531 Ankara Turkey

In this study, we consider the multi resource agent bottleneck generalised assignment problem. Our aim is to minimise the maximum load over all agents. We take our motivation from an assignment problem faced in heating, ventilating and air conditioning sector. We study the linear programming (LP) relaxation of the problem. We use the optimal LP relaxation solutions in our branch and bound algorithm while defining bounding and branching schemes. We find that our branch and bound algorithm returns optimal solutions to the problems with up to 60 jobs when the number of agents is 5, and up to 30 jobs when the number of agents is 10, in less than 20 minutes. To find approximate solutions, we define a tabu search algorithm and alpha approximation algorithm. Our computational results have revealed that both algorithms can find high quality solutions to large sized instances very quickly. To the best of our knowledge our study is the first reported attempt to solve the problem. We hope our study fills an important gap in the literature.

关键词： bottleneck generalised assignment problem multi periods branch and bound algorithm linear programming relaxation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：