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

An exact algorithm for the Blocks Relocation Problem with new lower bounds

COMPUTERS & OPERATIONS RESEARCH 2018年 99卷 206-217页

作者： Yucra Quispe, Kent E. Lintzmayer, Carla N. Xavier, Eduardo C. Univ Estadual Campinas Inst Comp Campinas SP Brazil Fed Univ ABC Ctr Math Computat & Cognit Santo Andre SP Brazil

The Blocks Relocation Problem is an important problem in storage systems. An input instance for it consists of a set of blocks distributed in stacks where each block is identified by a retrieval number and each stack has a same maximum height limit. The objective is to retrieve all the blocks respecting their retrieval order and performing the minimum number of relocations. Only blocks at the top of a stack can be moved: either a block is retrieved, if it has the highest retrieval priority among the stacked blocks, or it is relocated to the top of another stack. Solving this problem is critical in storage systems because it saves operational time and resources. In this paper, we present two new lower bounds for the number of relocations of an optimal solution. We implemented an exact iterative deepening A* algorithm using these new proposed lower bounds and other well-known lower bounds from the literature. We performed several computational experiments to show that the new lower bounds improve the performance of the exact algorithm, solving to optimality more instances than when using other lower bounds when given the same amount of time. (C) 2018 Elsevier Ltd. All rights reserved.

关键词： Blocks Relocation Problem Container Relocation Problem exact algorithms Lower bounds

来源：评论

学校读者我要写书评

暂无评论

Collusion in Atomic Splittable Routing Games

引用

THEORY OF COMPUTING SYSTEMS 2013年第4期52卷 763-801页

作者： Huang, Chien-Chung Humboldt Univ D-10099 Berlin Germany

We study how collusion affects the social cost in atomic splittable routing games. Suppose that players form coalitions and each coalition behaves as if it were a single player controlling all the flows of its participants. We investigate the following question: under what conditions would the social cost of the post-collusion equilibrium be bounded by the social cost of the pre-collusion equilibrium? We show that if (i) the network is "well-designed" (satisfying a natural condition), and (ii) the delay functions are affine, then collusion is always beneficial for the social cost in the equilibrium flows. On the other hand, if either of the above conditions is unsatisfied, collusion can worsen the social cost. Our main technique is a novel flow-augmenting algorithm to build equilibrium flows. Our positive result for collusion is obtained by applying this algorithm simultaneously to two different flow value profiles of players and observing the difference in the derivatives of their social costs. Moreover, for a non-trivial subclass of selfish routing games, this algorithm finds the exact equilibrium flows in polynomial time.

关键词： Selfish routing Collusion Social cost Nash equilibria exact algorithms

来源：评论

学校读者我要写书评

暂无评论

A multivariate complexity analysis of the material consumption scheduling problem

引用

JOURNAL OF SCHEDULING 2023年第4期26卷 369-382页

作者： Bentert, Matthias Bredereck, Robert Gyorgyi, Peter Kaczmarczyk, Andrzej Niedermeier, Rolf Tech Univ Berlin Fac Algorithm & Computat Complex 4 Berlin Germany Humboldt Univ Inst Informat Algorithm Engn Berlin Germany Tech Univ Clausthal Inst Informat Clausthal Zellerfeld Germany Eotvos Lorand Res Network Inst Comp Sci & Control Budapest Hungary AGH Univ Sci & Technol Krakow Poland

The NP-hard problem Material Consumption Scheduling and related problems have been thoroughly studied since the 1980's. Roughly speaking, the problem deals with scheduling jobs that consume non-renewable resources-each job has individual resource demands. The goal is to minimize the makespan. We focus on the single-machine case without preemption: from time to time, the resources of the machine are (partially) replenished, thus allowing for meeting a necessary precondition for processing further jobs. We initiate a systematic exploration of the parameterized computational complexity landscape of Material Consumption Scheduling, providing parameterized tractability as well as intractability results. Doing so, we mainly investigate how parameters related to the resource supplies influence the problem's computational complexity. This leads to a deepened understanding of this fundamental scheduling problem.

关键词： Non-renewable resources Makespan minimization Parameterized computational complexity Fine-grained complexity exact algorithms

来源：评论

学校读者我要写书评

暂无评论

A note on a model for quay crane scheduling with non-crossing constraints

引用

ENGINEERING OPTIMIZATION 2015年第6期47卷 860-865页

作者： Santini, Alberto Friberg, Henrik Alsing Ropke, Stefan Univ Bologna Dept Elect Elect & Informat Engn I-40126 Bologna Italy MOSEK Aps DK-2100 Copenhagen Denmark Tech Univ Denmark Dept Management Engn DK-2800 Lyngby Denmark

This article studies the quay crane scheduling problem with non-crossing constraints, which is an operational problem that arises in container terminals. An enhancement to a mixed integer programming model for the problem is proposed and a new class of valid inequalities is introduced. Computational results show the effectiveness of these enhancements in solving the problem to optimality.

关键词： non-crossing constraints exact algorithms quay crane scheduling container terminals mixed integer programming

来源：评论

学校读者我要写书评

暂无评论

Roundoff-Error-Free algorithms for Solving Linear Systems via Cholesky and LU Factorizations

引用

INFORMS JOURNAL ON COMPUTING 2015年第4期27卷 677-689页

作者： Escobedo, Adolfo R. Moreno-Centeno, Erick Texas A&M Univ Dept Ind & Syst Engn College Stn TX 77843 USA

LU and Cholesky factorizations are computational tools for efficiently solving linear systems that play a central role in solving linear programs and several other classes of mathematical programs. In many documented cases, however, the roundoff errors accrued during the construction and implementation of these factorizations lead to the misclassification of feasible problems as infeasible and vice versa. Hence, reducing these roundoff errors or eliminating them altogether is imperative to guarantee the correctness of the solutions provided by optimization solvers. To achieve this goal without having to use rational arithmetic, we introduce two roundoff-error-free factorizations that require storing the same number of individual elements and performing a similar number of operations as the traditional LU and Cholesky factorizations. Additionally, we present supplementary roundoff-error-free forward and backward substitution algorithms, thereby providing a complete tool set for solving systems of linear equations exactly and efficiently. An important property shared by the featured factorizations and substitution algorithms is that their individual coefficients' maximum word length-i.e., the maximum number of digits required for expression-is bounded polynomially. Unlike the rational arithmetic methods used in practice to solve linear systems exactly, however, the algorithms herein presented do not require any gcd calculations to bound the entries' word length. We also derive various other related theoretical results, including the total computational complexity of all the roundoff-error-free processes herein presented.

关键词： exact mathematical programming exact algorithms matrix factorizations roundoff errors solving linear systems

来源：评论

学校读者我要写书评

暂无评论

An exact Algorithm for a Rich Vehicle Routing Problem with Private Fleet and Common Carrier

引用

TRANSPORTATION SCIENCE 2019年第4期53卷 986-1000页

作者： Dabia, Said Lai, David Vigo, Daniele Vrije Univ Amsterdam Sch Business & Econ NL-1081 HV Amsterdam Netherlands Eyefreight BV NL-3981 AJ Bunnik Netherlands Univ Bologna Dept Elect Elect & Informat Engn I-40126 Bologna BO Italy

The vehicle routing problem with private fleet and common carrier (VRPPC) is a generalization of the classical vehicle routing problem in which the owner of a private fleet can either visit a customer with one of the owner's vehicles or assign the customer to a common carrier. The latter case occurs if the demand exceeds the total capacity of the private fleet or if it is more economically convenient to do so. The owner's objective is to minimize the variable and fixed costs for operating the owner's fleet plus the total cost charged by the common carrier. This family of problems has many practical applications, particularly in the design of last-mile distribution services and has received some attention in the literature, in which some heuristics were proposed. We extend here the VRPPC by considering more realistic cost structures that account for quantity discounts on outsourcing costs and by considering time windows resulting in a rich VRPPC (RVRPPC). We present an exact approach based on a branch-and-cut-and-price algorithm for the RVRPPC and test the algorithm on instances from the literature.

关键词： vehicle routing exact algorithms Private fleet and common carriers

来源：评论

学校读者我要写书评

暂无评论

The capacitated team orienteering problem with incomplete service

引用

OPTIMIZATION LETTERS 2013年第7期7卷 1405-1417页

作者： Archetti, Claudia Bianchessi, Nicola Speranza, M. Grazia Univ Brescia Dept Quantitat Methods Brescia Italy Univ Brescia Dept Informat Engn Brescia Italy

In this paper we study the capacitated version of the Team Orienteering Problem (TOP), that is the Capacitated TOP (CTOP) and the impact of relaxing the assumption that a customer, if served, must be completely served. We prove that the profit collected by the CTOP with Incomplete Service (CTOP-IS) may be as large as twice the profit collected by the CTOP. A computational study is also performed to evaluate the average increase of the profit due to allowing incomplete service. The results show that the increase of the profit strongly depends on the specific instance. On the tested instances the profit increase ranges between 0 and 50 %. We complete the computational study with the increase of the profit of the CTOP due to split deliveries, that is multiple visits to the same customer, and to split deliveries combined with incomplete service.

关键词： Capacitated Team Orienteering Problem Incomplete service Split deliveries exact algorithms

来源：评论

学校读者我要写书评

暂无评论

A Refined Branching Algorithm for the Maximum Satisfiability Problem

引用

ALGORITHMICA 2022年第4期84卷 982-1006页

作者： Li, Wenjun Xu, Chao Yang, Yongjie Chen, Jianer Wang, Jianxin Changsha Univ Sci & Technol Hunan Prov Key Lab Intelligent Proc Big Data Tran Changsha Peoples R China Saarland Univ Fac Human & Business Sci Chair Econ Theory Saarbrucken Germany Texas A&M Univ Dept Comp Sci & Engn College Stn TX USA Cent South Univ Sch Comp Sci & Engn Changsha Peoples R China

The MAXIMUM SATISFIABILITY problem (MAXSAT) is a fundamental NP-hard problem which has significant applications in many areas. Based on refined observations, we derive a branching algorithm of running time O*(1.2989(m)) for the MAXSAT problem, where m denotes the number of clauses in the given CNF formula. Our algorithm considerably improves the previous best result O*(1.3248(m)) published in 2004. For our purpose, we derive improved branching strategies for variables of degrees 3, 4, and 5. The worst case of our branching algorithm is at certain degree-4 variables. To serve the branching rules, we also propose a variety of reduction rules which can be exhaustively applied in polynomial time.

关键词： Maximum satisfiability Branching algorithms exact algorithms

来源：评论

学校读者我要写书评

暂无评论

On the empirical time complexity of finding optimal solutions vs proving optimality for Euclidean TSP instances

引用

OPTIMIZATION LETTERS 2015年第6期9卷 1247-1254页

作者： Hoos, Holger H. Stutzle, Thomas Univ British Columbia Dept Comp Sci Vancouver BC V6T 1W5 Canada Univ Libre Bruxelles IRIDIA CoDE Brussels Belgium

We investigate the empirical performance of the long-standing state-of-the-art exact TSP solver Concorde on various classes of Euclidean TSP instances and show that, surprisingly, the time spent until the first optimal solution is found accounts for a large fraction of Concorde's overall running time. This finding holds for the widely studied random uniform Euclidean (RUE) instances as well as for several other widely studied sets of Euclidean TSP instances. On RUE instances, the median fraction of Concorde's total running time spent until an optimal solution is found ranges from 0.77 for to 0.97 for;on TSPLIB, National and VLSI instances, we pegged it at 0.86, 0.74 and 0.61, respectively, with a tendency of even smaller values for larger instances.

关键词： TSP Empirical complexity exact algorithms

来源：评论

学校读者我要写书评

暂无评论

An exact approach for Complete Test Set Generation of Toffoli-Fredkin-Peres based Reversible Circuits

引用

JOURNAL OF ELECTRONIC TESTING-THEORY AND APPLICATIONS 2016年第2期32卷 175-196页

作者： Nagamani, A. N. Ashwin, S. Abhishek, B. Agrawal, V. K. PES Inst Technol Dept ECE PES Univ Campus Bangalore Karnataka India PES Inst Technol Dept Informat Sci & Engn PES Univ Campus Bangalore Karnataka India

Reversible logic has gained interest of researchers worldwide for its ultra-low power and high speed computing abilities in the future quantum information processing. Testing of these circuits is important for ensuring high reliability of their operation. In this work, we propose an ATPG algorithm for reversible circuits using an exact approach to generate CTS (Complete Test Set) which can detect single stuck-at faults, multiple stuck-at faults, repeated gate fault, partial and complete missing gate faults which are very useful logical fault models for reversible logic to model any physical defect. Proposed algorithm can be used to test a reversible circuit designed with k-CNOT, Peres and Fredkin gates. Through extensive experiments, we have validated our proposed algorithm for several benchmark circuits and other circuits with family of reversible gates. This algorithm produces a minimal and complete test set while reducing test generation time as compared to existing state-of-the-art algorithms. A testing tool is developed satisfying the purpose of generating all possible CTS's indicating the simulation time, number of levels and gates in the circuit. This paper also contributes to the detection and removal of redundant faults for optimal test set generation.

关键词： exact algorithms Testing Redundant faults Stuck-at faults Missing gate faults

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：