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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A multi-objective sustainable closed-loop supply chain network problem with hybrid facilities

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2025年第6期32卷 3497-3527页

作者： Rodriguez-Escoto, Joel-Novi Olivares-Benitez, Elias Nucamendi-Guillen, Samuel Drzymalski, Julie Univ Panamericana Fac Ingn Alvaro Portillo 49 Zapopan 45010 Jalisco Mexico Temple Univ Coll Engn Philadelphia PA 19122 USA

A sustainable closed-loop supply chain network requires conjunctive implementation of reverse logistics in the supply chain, with decisions that consider economic, environmental, and social factors. In real life, the problem needs to be addressed by prioritizing targets or interacting between them to give a range of solutions to the decision maker. In this context, this work proposes a novel multi-objective sustainable closed-loop supply chain network problem based on the revised network design model with hybrid recovery centers minimizing (1) the total economic cost, (2) the CO2 emission of vehicles used, and (3) the total obnoxious distance. The latter objective is a novel implementation of the social dimension of a sustainable model. A sensitivity analysis of the multi-objective model is developed through ANOVA. A dataset of instances was generated to test the model and the solution methods, which are configured with AUGMECON2, a linear programming relaxation implemented to improve the CPU time, and AUGMECON2-EXTENDED to obtain more solutions to avoid exploring all space of the solution. The results show that an AUGMECON2-EXTENDED implementation outperforms all the selected performance metrics. These performance metrics include NPS, CPU time, RPOS, QM, and HV. The results show an improvement on average of at least 50%$50\%$, 60%$60\%$, 90%$90\%$, 60%$60\%$, and 5.7%$5.7\%$, respectively, in those metrics, in comparison to other implementations.

关键词： sustainable closed-loop supply chain network multi-objective optimization linear programming relaxation augmented epsilon constraint 2 multi-objective ANOVA obnoxious facility

来源：评论

学校读者我要写书评

暂无评论

Rank-One Boolean Tensor Factorization and the Multilinear Polytope

引用

MATHEMATICS OF OPERATIONS RESEARCH 2025年第2期50卷 783-1583, C2页

作者： Del Pia, Alberto Khajavirad, Aida Univ Wisconsin Madison Dept Ind & Syst Engn Madison WI 53715 USA Univ Wisconsin Madison Wisconsin Inst Discovery Madison WI 53715 USA Lehigh Univ Dept Ind & Syst Engn Bethlehem PA 18015 USA

We consider the NP-hard problem of finding the closest rank-one binary tensor to a given binary tensor, which we refer to as the rank-one Boolean tensor factorization (BTF) problem. This optimization problem can be used to recover a planted rankone tensor from noisy observations. We formulate rank-one BTF as the problem of minimizing a linear function over a highly structured multilinear set. Leveraging on our prior results regarding the facial structure of multilinear polytopes, we propose novel linear programming relaxations for rank-one BTF. We then establish deterministic sufficient conditions under which our proposed linear programs recover a planted rank-one tensor. To analyze the effectiveness of these deterministic conditions, we consider a semirandom model for the noisy tensor and obtain high probability recovery guarantees for the linear programs. Our theoretical results as well as numerical simulations indicate that certain facets of the multilinear polytope significantly improve the recovery properties of linear programming relaxations for rank-one BTF.

关键词： rank-one Boolean tensor factorization multilinear polytope linear programming relaxation recovery guarantee semirandom models

来源：评论

学校读者我要写书评

暂无评论

Fractional Decomposition Tree Algorithm: A tool for studying the integrality gap of Integer Programs

引用

DISCRETE OPTIMIZATION 2023年 47卷

作者： Carr, Robert Haddadan, Arash Phillips, Cynthia A. Univ New Mexico Albuquerque NM USA Amazon Inc Bellevue WA 98170 USA Sandia Natl Labs Albuquerque NM USA

We present a new algorithm, Fractional Decomposition Tree (FDT), for finding a feasible solution for an integer program (IP) where all variables are binary. FDT runs in polynomial time and is guaranteed to find a feasible integer solution provided the integrality gap of an instance's polyhedron, independent of objective function, is bounded. The algorithm gives a construction for Carr and Vempala's theorem that any feasible solution to the IP's linear-programming relaxation, when scaled by the instance integrality gap, dominates a convex combination of feasible solutions. FDT is also a tool for studying the integrality gap of IP formulations. The upper bound on the integrality gap of an FDT solution can be exponentially large. However our experiments demonstrate that FDT can be effective in practice. We study the integrality gap of two problems: optimally augmenting a tree to a 2-edge-connected graph and finding a minimum-cost 2-edge-connected multi-subgraph (2EC). We also give a simplified algorithm, DomToIP, that finds a feasible solution to an IP instance, or concludes that it has unbounded integrality gap. We show that FDT's speed and approximation quality compare well to that of the original feasibility pump heuristic on moderate-sized instances of the vertex cover problem. For a particular set of hard-to-decompose fractional 2EC solutions, FDT always gave a better integer solution than the Best-of-Many Christofides Algorithm (BOMC).(c) 2022 Elsevier B.V. All rights reserved.

关键词： linear programming relaxation Integer programming Integrality Gap Convex combination

来源：评论

学校读者我要写书评

暂无评论

k-median: exact recovery in the extended stochastic ball model

引用

MATHEMATICAL programming 2023年第1期200卷 357-423页

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

We study exact recovery conditions for the linear programming relaxation of the k-median problem in the stochastic ball model (SBM). In Awasthi et al. (Relax, no need to round: integrality of clustering formulations. arXiv:1408.4045, 2015;in: Proceedings of the 2015 conference on innovations in theoretical computer science, pp 191-200, 2015), the authors give a tight result for the k-median LP in the SBM, saying that exact recovery can be achieved as long as the balls are pairwise disjoint. We give a counterexample to their result, thereby showing that the k-median LP is not tight in low dimension. Instead, we give a near optimal result showing that the k-median LP in the SBM is tight in high dimension. We also show that, if the probability measure satisfies some concentration assumptions, then the k-median LP in the SBM is tight in every dimension. Furthermore, we propose a new model of data called extended stochastic ball model (ESBM), which significantly generalizes the well-known SBM. We then show that exact recovery can still be achieved in the ESBM.

关键词： k-median Stochastic ball model linear programming relaxation Recovery guarantee

来源：评论

学校读者我要写书评

暂无评论

A matheuristic algorithm for the pollution and energy minimization traveling salesman problems

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2023年第2期30卷 655-687页

作者： Cacchiani, Valentina Contreras-Bolton, Carlos Escobar-Falcon, Luis Miguel Toth, Paolo Univ Bologna DEI Viale Risorgimento 2 I-40136 Bologna Italy Univ Concepcion Dept Ingn Ind Edmundo Larenas 219 Concepcion 4070409 Chile Univ Libre Program Syst Engn Belmonte Ave Amer Pereira 660001 Colombia

The pollution traveling salesman problem (PTSP) and the energy minimization traveling salesman problem (EMTSP) generalize the well-known asymmetric traveling salesman problem by including environmental issues and the goal of reducing carbon emissions. Both problems call for determining a Hamiltonian tour that, in the PTSP, minimizes a function of fuel consumption and driver cost (where the fuel consumption depends on the distance traveled, the vehicle speed, and the vehicle load), while, in the EMTSP, minimizes a function depending on the vehicle load and the traveled distances. For both PTSP and EMTSP, we propose a matheuristic algorithm that uses the solution of the linear programming relaxation of a mixed integer linear programming model for the considered problem to determine good initial feasible solutions, applies a multioperator genetic algorithm to improve these solutions, and refines the best solution found through an iterated local search procedure. In order to evaluate the performance of the proposed matheuristics, we compare them with exact and heuristic algorithms from the literature on benchmark instances of both problems.

关键词： pollution traveling salesman problem energy minimization traveling salesman problem matheuristic algorithm linear programming relaxation

来源：评论

学校读者我要写书评

暂无评论

A tight approximation algorithm for the cluster vertex deletion problem

引用

MATHEMATICAL programming 2023年第2期197卷 1069-1091页

作者： Aprile, Manuel Drescher, Matthew Fiorini, Samuel Huynh, Tony Univ Padua Dipartimento Matemat Padua Italy Univ Libre Bruxelles Dept Math Brussels Belgium Monash Univ Sch Math Melbourne Vic Australia

We give the first 2-approximation algorithm for the cluster vertex deletion problem. This approximation factor is tight, since approximating the problem within any constant factor smaller than 2 is UGC-hard. Our algorithm combines previous approaches, based on the local ratio technique and the management of twins, with a novel construction of a "good" cost function on the vertices at distance at most 2 from any vertex of the input graph. As an additional contribution, we also study cluster vertex deletion from the polyhedral perspective, where we prove almost matching upper and lower bounds on how well linear programming relaxations can approximate the problem.

关键词： Approximation algorithm Cluster vertex deletion linear programming relaxation Sherali-Adams hierarchy

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：