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

exact algorithms for class-constrained packing problems

COMPUTERS & INDUSTRIAL ENGINEERING 2020年 144卷 106455-106455页

作者： Borges, Yulle G. F. Miyazawa, Flavio K. Schouery, Rafael C. S. Xavier, Eduardo C. Univ Estadual Campinas Av Albert Einstein 1251Cidade Univ Campinas SP Brazil

We consider a generalization of the classic Bin Packing Problem, called the Class-Constrained Bin Packing Problem (CCBPP), in which given a set of items, each one with a size and a class, one must pack the items in the least amount of bins respecting the bin capacity and the number of different classes that it can hold. We also consider the Class-Constrained Knapsack Problem (CCKP), in which items also have a value and one must select a subset of items with a maximum value which fits in a single bin. We consider a Branch-and-Price framework for CCBPP, exploring several options in the design of a Branch-and-Price algorithm. For the Pricing Problem, which is equivalent to the CCKP, we present two dynamic programming algorithms and a Branch-and-Bound algorithm. We also present other exact algorithms for generalizations of CCKP. These generalized problems also appear as Pricing Problems when solving the CCBPP. Our best algorithm for CCBPP was able to solve 95% of the instances considered in less than 15 min.

关键词： Bin packing Knapsack exact algorithm Branch-and-price

来源：评论

学校读者我要写书评

暂无评论

exact algorithms of Search for a Cluster of the Largest Size in Two Integer 2-Clustering Problems

引用

NUMERICAL ANALYSIS AND APPLICATIONS 2019年第2期12卷 105-115页

作者： Kel'manov, A., V Panasenko, A., V Khandeev, V., I Russian Acad Sci Sobolev Inst Math Siberian Branch Pr Akad Koptyuga 4 Novosibirsk 630090 Russia Novosibirsk State Univ Ul Pirogova 1 Novosibirsk 630090 Russia

We consider two related discrete optimization problems of searching for a subset in a finite set of points in Euclidean space. Both problems are induced by versions of a fundamental problem in data analysis, namely, that of selecting a subset of similar elements in a set of objects. In each problem, given an input set and a positive real number, it is required to find a cluster (i.e., a subset) of the largest size under constraints on a quadratic clusterization function. The points in the input set, which are outside the sought-for subset, are treated as a second (complementary) cluster. In the first problem, the function under the constraint is the sum over both clusters of the intracluster sums of the squared distances between the elements of the clusters and their centers. The center of the first (i.e., the sought-for) cluster is unknown and determined as a centroid, while the center of the second one is fixed at a given point in Euclidean space (without loss of generality, at the origin of coordinates). In the second problem, the function under the constraint is the sum over both clusters of the weighted intracluster sums of the squared distances between the elements of the clusters and their centers. As in the first problem, the center of the first cluster is unknown and determined as a centroid, while the center of the second one is fixed at the origin of coordinates. In this paper, we show that both problems are strongly NP-hard. Also, we present exact algorithms for the problems in which the input points have integer components. If the space dimension is bounded by some constant, the algorithms are pseudopolynomial.

关键词： Euclidean space 2-clustering largest subset NP-hardness exact algorithm pseudopolynomial-time solvability

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for weighted and unweighted Borda manipulation problems

引用

THEORETICAL COMPUTER SCIENCE 2016年 622卷 79-89页

作者： Yang, Yongjie Guo, Jiong Shandong Univ Sch Comp Sci & Technol ShunHua Rd 1500 Jinan 250101 Peoples R China Univ Saarland Campus E 1-7 D-66123 Saarbrucken Germany

We propose O*((m.2(m))(t+1))-time and O*(((t+m-1)(t)) . (t + 1)(m))-time algorithms for the weighted and the unweighted Borda manipulation problems, respectively, where t is the number of manipulators and m is the number of candidates. In particular, for t = 2, our algorithm for the unweighted case runs in O*(3(m)) time, affirmatively resolving one open problem posed by Betzler et al. [2]. As a byproduct of our results, we show that the unweighted Borda manipulation problem admits an algorithm with running time 0*(2(9m2) (logm)), based on an integer linear programming technique. Finally, we prove that the unweighted Borda manipulation problem is polynomial-time solvable in single-peaked elections, in contrast to the NP-hardness in the general case. (C) 2016 Published by Elsevier B.V.

关键词： exact algorithm Computational social choice Borda manipulation Single-peaked elections

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for two integer-valued problems of searching for the largest subset and longest subsequence

引用

ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE 2020年第1-3期88卷 157-168页

作者： Kel'manov, Alexander Khamidullin, Sergey Khandeev, Vladimir Pyatkin, Artem Sobolev Inst Math 4 Koptyug Ave Novosibirsk 630090 Russia Novosibirsk State Univ 2 Pirogova St Novosibirsk 630090 Russia

The following two strongly NP-hard problems are considered. In the first problem, we need to find in the given finite set of points in Euclidean space the subset of largest size. The sum of squared distances between the elements of this subset and its unknown centroid (geometrical center) must not exceed a given value. This value is defined as percentage of the sum of squared distances between the elements of the input set and its centroid. In the second problem, the input is a sequence (not a set) and we have some additional constraints on the indices of the elements of the chosen subsequence. The restriction on the sum of squared distances is the same as in the first problem. Both problems can be treated as data editing problems aimed to find similar elements and removal of extraneous (dissimilar) elements. We propose exact algorithms for the cases of both problems in which the input points have integer-valued coordinates. If the space dimension is bounded by some constant, our algorithms run in a pseudopolynomial time. Some results of numerical experiments illustrating the performance of the algorithms are presented.

关键词： Euclidean space Largest subset Longest subsequence Quadratic variation exact algorithm Pseudopolynomial time

来源：评论

学校读者我要写书评

暂无评论

A Mixed-Integer Linear Programming Model for Addressing Efficient Flexible Flow Shop Scheduling Problem with Automatic Guided Vehicles Consideration

引用

APPLIED SCIENCES-BASEL 2025年第6期15卷 3133-3133页

作者： Wang, Dekun Wu, Hongxu Zheng, Wengang Zhao, Yuhao Tian, Guangdong Wang, Wenjie Chen, Dong Zhengzhou Univ Sch Mech & Power Engn Zhengzhou 450001 Peoples R China Beijing Univ Civil Engn & Architecture Sch Machinery & Vehicles Beijing 100044 Peoples R China

With the development of Industry 4.0, discrete manufacturing systems are accelerating their transformation toward flexibility and intelligence to meet the market demand for various products and small-batch production. The flexible flow shop (FFS) paradigm enhances production flexibility, but existing studies often address FFS scheduling and automated guided vehicle (AGV) path planning separately, resulting in resource competition conflicts, such as equipment idle time and AGV congestion, which prolong the manufacturing cycle time and reduce system energy efficiency. To solve this problem, this study proposes an integrated production-transportation scheduling framework (FFSP-AGV). By using the adjacent sequence modeling idea, a mixed-integer linear programming (MILP) model is established, which takes into account the constraints of the production process and AGV transportation task conflicts with the aim of minimizing the makespan and improving overall operational efficiency. Systematic evaluations are carried out on multiple test instances of different scales using the CPLEX solver. The results show that, for small-scale instances (job count <= 10), the MILP model can generate optimal scheduling solutions within a practical computation time (several minutes). Moreover, it is found that there is a significant marginal diminishing effect between AGV quantity and makespan reduction. Once the number of AGVs exceeds 60% of the parallel equipment capacity, their incremental contribution to cycle time reduction becomes much smaller. However, the computational complexity of the model increases exponentially with the number of jobs, making it slightly impractical for large-scale problems (job count > 20). This research highlights the importance of integrated production-transportation scheduling for reducing manufacturing cycle time and reveals a threshold effect in AGV resource allocation, providing a theoretical basis for collaborative optimization in smart factories.

关键词： integrated scheduling flexible flow shop scheduling makespan AGV scheduling mixed-integer linear programming exact algorithm

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for problems related to the densest k-set problem

引用

INFORMATION PROCESSING LETTERS 2014年第9期114卷 510-513页

作者： Chang, Maw-Shang Chen, Li-Hsuan Hung, Ling-Ju Rossmanith, Peter Wu, Guan-Han HungKuang Univ Dept Comp Sci & Informat Engn Taichung 43302 Taiwan Natl Chung Cheng Univ Dept Comp Sci & Informat Engn Chiayi 62102 Taiwan Rhein Westfal TH Aachen Dept Comp Sci D-52056 Aachen Germany

Many graph concepts such as cliques, k-clubs, and k-plexes are used to define cohesive subgroups in a social network. The concept of densest k-set is one of them. A densest k-set in an undirected graph G = (V, E) is a vertex set S subset of V of size k such that the number of edges in the subgraph of G induced by S is maximum among all subgraphs of G induced by vertex sets of size k. One can obtain a densest k-set of G in O (k(2)n(k)) time by exhaustive-search technique for an undirected graph of n vertices and a number k < n. However, if the value of k approaches n/2, the running time of the exhaustive-search algorithm is O*(2(n)). Whether there exists an O*(c(n))-time algorithm with the fixed constant c < 2 to find a densest k-set in an undirected graph of n vertices remains open in the literature. In this paper, we point out that the densest k-set problem and a class of problems related to the concept of densest k-sets can be solved in time O*(1.7315(n)). (C) 2014 Elsevier B.V. All rights reserved.

关键词： Densest (sparsest) k-set Minimum (maximum) k-vertex cover Partial vertex cover exact algorithm Design of algorithms

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for Two Quadratic Euclidean Problems of Searching for the Largest Subset and Longest Subsequence 12th

Exact Algorithms for Two Quadratic Euclidean Problems of Sea...

引用

12th International Conference on Learning and Intelligent Optimization (LION)

ISBN: (纸本)9783030053482;9783030053475

The following two strongly NP-hard problems are considered. In the first problem, we need to find in the given finite set of points in Euclidean space the subset of largest size such that the sum of squared distances between the elements of this subset and its unknown centroid (geometrical center) does not exceed a given percentage of the sum of squared distances between the elements of the input set and its centroid. In the second problem, the input is a sequence (not a set) and we have some additional constraints on the indices of the elements of the chosen subsequence under the same restriction on the sum of squared distances as in the first problem. Both problems can be treated as data editing problems aimed to find similar elements and removal of extraneous (dissimilar) elements. We propose exact algorithms for the cases of both problems in which the input points have integer-valued coordinates. If the space dimension is bounded by some constant, our algorithms run in a pseudopolynomial time. Some results of numerical experiments illustrating the performance of the algorithms are presented.

关键词： Euclidean space Largest set Longest subsequence Quadratic variation NP-hard problem Integer coordinates exact algorithm Fixed space dimension Pseudopolynomial time

来源：评论

学校读者我要写书评

暂无评论

On exact algorithms for the permutation CSP

引用

THEORETICAL COMPUTER SCIENCE 2013年 511卷 109-116页

作者： Kim, Eun Jung Goncalves, Daniel Univ Paris 09 LAMSADE F-75775 Paris 16 France CNRS F-75700 Paris France Univ Montpellier 2 LIRMM F-34095 Montpellier 5 France

In the PERMUTATION CONSTRAINT SATISFACTION PROBLEM (PERMUTATION CSP) we are given a set of variables V and a set of constraints C, in which the constraints are tuples of elements of V. The goal is to find a total ordering of the variables, pi : V -> [1,...,vertical bar V vertical bar], which satisfies as many constraints as possible. A constraint (v(1), v(2),..., v(k)) is satisfied by an ordering pi when pi (v(1)) < (pi v(2)) < ... < pi(v(k)). An instance has arity k if all the constraints involve at most k elements. This problem expresses a variety of permutation problems including FEEDBACK ARC SET and BETWEENNESS problems. A naive algorithm, listing all the n! permutations, requires 2(O(n) (log n)) time. Interestingly, PERMUTATION CSP for arity 2 or 3 can be solved by Held-Karptype algorithms in time O*(2(n)), but no algorithm is known for arity at least 4 with running time significantly better than 2(O(n log n)). In this paper we resolve the gap by showing that ARITY 4 PERMUTATION CSP cannot be solved in time 2(O(n log n)) unless the exponential time hypothesis fails. (C) 2012 Elsevier B.V. All rights reserved.

关键词： exact algorithm algorithmic lower bound Permutation constraint satisfaction problem

来源：评论

学校读者我要写书评

暂无评论

An overview of exact algorithms for the Euclidean Steiner tree problem in n-space

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2016年第5期23卷 861-874页

作者： Fampa, Marcia Lee, Jon Maculan, Nelson Univ Fed Rio de Janeiro Inst Matemat Dept Ciencia Comp Rio De Janeiro RJ Brazil Univ Fed Rio de Janeiro COPPE PESC Rio De Janeiro RJ Brazil Univ Michigan Dept Ind & Operat Engn Ann Arbor MI 48109 USA

The Euclidean Steiner tree problem (ESTP) in R-n is to find a shortest network interconnecting p given points in n-dimensional Euclidean space. The problem was first described in the plane and an algorithm with very good practical efficiency has been proposed to solve this particular case. The generalization for higher dimensions was proposed in the 19th century, however the numerical solution of the problem remains very challenging when n >= 3. We give an overview of the exact algorithms presented in the literature for the ESTP when n >= 3 and discuss their common and distinguished features, their advantages and drawbacks, and some possible directions for improvement toward the numerical solution of large instances of the problem.

关键词： Euclidean Steiner tree problem n-dimensional Euclidean space exact algorithm mixed-integer nonlinear programming global optimization

来源：评论

学校读者我要写书评

暂无评论

Bisection and exact algorithms Based on the Lagrangian Dual for a Single-Constrained Shortest Path Problem

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2020年第1期28卷 224-233页

作者： Kou, Caixia Hu, Dedong Yuan, Jianhua Ai, Wenbao Beijing Univ Posts & Telecommun Sch Sci Beijing 100876 Peoples R China Beijing Univ Posts & Telecommun Sch Comp Sci Beijing 100876 Peoples R China

We propose two new algorithms called BiLAD and exactBiLAD for the well-known Single-Constrained Shortest Path (SCSP) problem. It is a fundamental problem in quality-of-service (QoS) routing, where one seeks a source-destination path with the least cost satisfying a delay QoS constraint in a network. As pointed out by Juttner et al., there is no widely accepted algorithm with polynomial time to the SCSP problem because the SCSP problem is NP-hard. The remarkable feature of BiLAD is that it ensures that the length of iteratively updated angle interval is shrunk at least at a constant ratio. With the help of this feature, we prove its polynomial time complexity. To the best of our knowledge, this is the first time that the polynomial time complexity is proved in details. The numerical results show that, in most QoS routing test instances, the performance of BiLAD is close to their primal optimal solutions. The proposed modified Dijkstra procedure, whose complexity is the same as that of the Dijkstra algorithm, also accelerates BiLAD. In the second part of the paper, based on the information obtained by BiLAD, we design an exact algorithm-exactBiLAD, in which an optimal solution to the SCSP problem is finally obtained by scanning the steadily reduced optimal-path-candidate triangle area. The simulation results indicate that exactBiLAD needs only a dozen times of executing the modified Dijkstra algorithm regardless of the network size or the average node degree. Distinguished from many other exact algorithms, exactBiLAD has a satisfactory performance in the practical computation.

关键词： QoS routing problem delay constrained least cost path single-constrained shortest path problem Lagrangian dual approach bisection scheme exact algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：