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

Computational aspects of relaxation complexity: possibilities and limitations

MATHEMATICAL programming 2023年第2期197卷 1173-1200页

作者： Averkov, Gennadiy Hojny, Christopher Schymura, Matthias BTU Cottbus Senftenberg Pl Deutsch Einheit 1 D-03046 Cottbus Germany Eindhoven Univ Technol Combinatorial Optimizat Grp POB 513 NL-5600 MB Eindhoven Netherlands

The relaxation complexity rc(X) of the set of integer points X contained in a polyhedron is the smallest number of facets of any polyhedron P such that the integer points in P coincide with X. It is a useful tool to investigate the existence of compact linear descriptions of X. In this article, we derive tight and computable upper bounds on rc(Q)(X), a variant of rc(X) in which the polyhedra P are required to be rational, and we show that rc(X) can be computed in polynomial time if X is 2-dimensional. Further, we investigate computable lower bounds on rc(X) with the particular focus on the existence of a finite set Y subset of Z(d) such that separating X and Y \ X allows us to deduce rc(X) >= k. In particular, we show for some choices of X that no such finite set Y exists to certify the value of rc(X), providing a negative answer to a question by Weltge (2015). We also obtain an explicit formula for rc(X) for specific classes of sets X and present the first practically applicable approach to compute rc(X) for sets X that admit a finite certificate.

关键词： integer programming formulation Relaxation complexity

来源：评论

学校读者我要写书评

暂无评论

Optimal Schedule of a Dairy Manufactory

引用

CHEMICAL AND BIOCHEMICAL ENGINEERING QUARTERLY 2009年第2期23卷 231-237页

作者： Adonyi, R. Shopova, E. Vaklieva-Bancheva, N. Bulgarian Acad Sci Inst Chem Engn BU-1113 Sofia Bulgaria Univ Pannonia Dept Comp Sci H-8200 Veszprem Hungary

This paper deals with short-term scheduling of the dairy industry. Two different approaches are proposed for obtaining the minimal makespan schedules. According to the first, S-graph framework is proposed to find the optimal solution of the flow-shop scheduling problem. The problem is solved by applying the branch and bound technique. The second approach uses the integer programming formulation of the scheduling problem and BASIC genetic algorithm has been used to solve the optimization problem. Both approaches take into consideration volumes of units assigned to perform tasks, and respective size factors that affect the size of batches and their number must be produces to achieve production goals and thus on the schedules duration. Manufacturing of two type curds is used as a case study. The results obtained show that both approaches provide comparable solutions. Both approaches could be seen as a good alternative to project manager to find appropriate schedule of the dairy industry.

关键词： Scheduling problem S-graph framework integer programming formulation dairy industry

来源：评论

学校读者我要写书评

暂无评论

Lagrangian relaxation heuristics for the uncapacitated single-source multi-product facility location problem

引用

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS 2013年第2期145卷 713-723页

作者： Nezhad, Ali Mohammad Manzour, Hasan Salhi, Said Sharif Univ Technol Dept Ind Engn Tehran Iran Univ Oklahoma Sch Ind & Syst Engn Norman OK 73019 USA Univ Kent Kent Business Sch Ctr Logist & Heurist Optimisat Canterbury Kent England

Facility location problem is one of the strategic logistical drivers within the supply chain which is a hard to solve optimization problem. In this study, we focus on the uncapacitated single-source multi-product production/distribution facility location problem with the presence of set-up cost. To efficiently tackle this decision problem, two Lagrangian-based heuristics are proposed one of which incorporates integer cuts to strengthen the formulation. Local search operators are also embedded within these methods to improve the upper bounds as the search progresses. Three sets of instances with various characteristics are generated and used to evaluate the performance of the proposed algorithms. Encouraging results are obtained when assessed against an ILP formulation using CPLEX. The latter is used for generating optimal solutions for small size instances and also as a means for producing upper and lower bounds for larger ones when restricted by a limited amount of execution time. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Location problems integer programming formulation Lagrangian relaxation Cutting plane Local search

来源：评论

学校读者我要写书评

暂无评论

Modeling a flexible staff scheduling problem in the Era of Covid-19

引用

OPTIMIZATION LETTERS 2022年第4期16卷 1259-1279页

作者： Guerriero, Francesca Guido, Rosita Univ Calabria DIMEG Arcavacata Di Rende CS Italy

In this paper, we propose optimization models to address flexible staff scheduling problems and some main issues arising from efficient workforce management during the Covid-19 pandemic. The adoption of precautionary measures to prevent the pandemic from spreading has raised the need to rethink quickly and effectively the way in which the workforce is scheduled, to ensure that all the activities are conducted in a safe and responsible manner. The emphasis is on novel optimization models that take into account demand requirements, employees' personal and family responsibilities, and anti-Covid-19 measures at the same time. It is precisely considering the anti-Covid-19 measures that the models allow to define the working mode to be assigned to the employees: working remotely or on-site. The last optimization model, which can be viewed as the most general and the most flexible formulation, has been developed to capture the specificity of a real case study of an Italian University. In order to improve employees' satisfaction and ensure the best work/life balance possible, an alternative partition of a workday into shifts to the usual two shifts, morning and afternoon, is proposed. The model has been tested on real data provided by the Department of Mechanical, Energy and Management Engineering, University of Calabria, Italy. The computational experiments show good performance and underline the potentiality of the model to handle worker safety requirements and practicalities and to ensure work activities continuity. In addition, the non-cyclic workforce policy, based on the proposed workday organization, is preferred by employees, since it allows them to better meet their needs.

关键词： Staff scheduling Resource management integer programming formulation Covid-19

来源：评论

学校读者我要写书评

暂无评论

Polynomial size IP formulations of knapsack may require exponentially large coefficients

引用

OPERATIONS RESEARCH LETTERS 2020年第5期48卷 612-618页

作者： Hojny, Christopher Eindhoven Univ Technol Combinatorial Optimizat Grp POB 513 NL-5600 MB Eindhoven Netherlands

A desirable property of integer formulations is to consist of few inequalities having small coefficients. We show that these targets are conflicting by proving the existence of knapsack sets that need exponentially many inequalities or exponentially large coefficients in any integer formulation. Moreover, we show that there exist undirected graphs such that (in a natural model) every integer formulation of stable sets requires exponentially large coefficients if the number of non-trivial inequalities is bounded by a constant. (C) 2020 The Author(s). Published by Elsevier B.V.

关键词： integer programming formulation Knapsack polytope Size of coefficients

来源：评论

学校读者我要写书评

暂无评论

A scaleable projection-based branch-and-cut algorithm for the p-center problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2022年第1期303卷 78-98页

作者： Gaar, Elisabeth Sinnl, Markus Johannes Kepler Univ Linz Inst Prod & Logist Management Linz Austria Johannes Kepler Univ Linz JKU Business Sch Linz Austria

The p-center problem (pCP) is a fundamental problem in location science, where we are given customer demand points and possible facility locations, and we want to choose p of these locations to open a facility such that the maximum distance of any customer demand point to its closest open facility is minimized. State-of-the-art solution approaches of pCP use its connection to the set cover problem to solve pCP in an iterative fashion by repeatedly solving set cover problems. The classical textbook integer programming (IP) formulation of pCP is usually dismissed due to its size and bad linear programming (LP)-relaxation *** present a novel solution approach that works on a new IP formulation that can be obtained by a projection from the classical formulation. The formulation is solved by means of branch-and-cut, where cuts for demand points are iteratively generated. Moreover, the formulation can be strengthened with combinatorial information to obtain a much tighter LP-relaxation. In particular, we present a novel way to use lower bound information to obtain stronger cuts. We show that the LP-relaxation bound of our strengthened formulation has the same strength as the best known bound in literature, which is based on a ***, we also present a computational study on instances from the literature with up to more than 70 0,0 0 0 customers and locations. Our solution algorithm is competitive with highly sophisticated set cover-based solution algorithms, which depend on various components and parameters.(c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license ( http://***/licenses/by/4.0/ )

关键词： Location p-center problem integer programming formulation Lifting Min-max objective

来源：评论

学校读者我要写书评

暂无评论

On symmetric subtour problems

引用

Japan Journal of Industrial and Applied Mathematics 1992年第3期9卷 383-396页

作者： Kubo, Mikio Kasugai, Hiroshi Department of Industrial Engineering Waseda University Tokyo 169 3-4-1 Okubo Shinjuku Japan

Recently several practical variants of the classical traveling salesman problem are proposed. These variants include the traveling purchaser problem, the prize collecting traveling salesman problem, the orienteering problem, the median shortest path problem, and the covering salesman problem. The most important common characteristic of these problems is that the salesman travels the subset of customers, i.e., the tour does not necessarily visit all nodes as in the traveling salesman problem. We call this class of problems the subtour problem. In this paper, we derive several valid inequalities and show some of them are facets of the polytope of the subtour problem. Further we present several integer or mixed integer programming formulations of the subtour problem and compare these formulations in terms of bounds obtained by linear programming relaxations. © 1992 JJIAM Publishing Committee.

关键词： integer programming formulation subtour problem traveling salesman problem valid inequality

来源：评论

学校读者我要写书评

暂无评论

An efficient 0-1 integer programming algorithm for advertising media selection

引用

Journal of the Academy of Marketing Science 1984年第1-2期12卷 191-204页

作者： Ahmed, Nazim U. Ball State University Muncie United States

Advertising is one of the important instruments in the success and continued growth of a product. Total expenditures for advertising in the United States may run into many billions of dollars. In this paper, an efficient algorithm for allocating scarce advertising resources is developed. The advertising media selection problem is formulated in terms of a 0-1 integer programming problem. An iterative solution procedure for this formulation is presented. A simple numerical example which illustrates the steps of the algorithm is also presented. The algorithm can generate efficient solutions to large media selection problems with relative computational ease, and may be of practical significance to decision makers. © 1984 Academy of Marketing Science.

关键词： integer Program integer programming Problem integer programming formulation Minimum Exposure MBAA

来源：评论

学校读者我要写书评

暂无评论

VNS-Based Matheuristic Approach to Group Steiner Tree with Problem-Specific Node Release Strategy 15th

VNS-Based Matheuristic Approach to Group Steiner Tree with P...

引用

15th International Conference of the Metaheuristics International Conference (MIC)

作者： Davidovic, Tatjana Jelic, Slobodan Serbian Acad Arts & Sci Math Inst Kneza Mihaila 36 Belgrade 11000 Serbia Univ Belgrade Fac Civil Engn Bulevar Kralja Aleksandra 73 Belgrade 11000 Serbia

ISBN: (纸本)9783031629112;9783031629129

For a given undirected graph G = (V, E) with a non-negative weight function w : E -> R+ and subsets G(1),..., G(k) of V, the Group Steiner Tree (GST) problem consists of constructing a tree T = (V-T, E-T) with minimal cost, where V-T. subset of V, E-T subset of E, and T spans at least one node from each of the groups. We develop a VNS-based metaheuristics approach for solving the GST problem. Our main contribution is that we propose a new problem-specific node release strategy that mimics the steps of a VNS-based heuristic. Instead of exploring different neighborhoods by combinatorially enumerating neighboring solutions, as in classical local search, we use a provably good integer Linear programming (ILP) formulation to solve a sequence of subproblems of the original problem. Our approach leads to an improvement over the state-of-theart Gurobi solver both in terms of quality and runtime of the instances available in the literature.

关键词： integer programming formulation subtour elimination metaheuristic methods hybrid heuristic decomposition strategy

来源：评论

学校读者我要写书评

暂无评论

Multi-products Location-Routing problem with Pickup and Delivery

Multi-products Location-Routing problem with Pickup and Deli...

引用

International Conference on Advanced Logistics and Transport (ICALT)

作者： Rahmani, Younes Oulamara, Ammar Cherif, Wahiba Ramdane Univ Lorraine LORIA UMR Lab 7503 Nancy France

ISBN: (纸本)9781479903139;9781479903146

An extended variant of Location-Routing Problem namely LRP with Multi-Product and Pickup and Delivery (LRP-MPPD) is considered in this study. The proposed model deals with simultaneously selecting (locating) one or more facilities from a set of potential hub (locations), assigning customers to the selected hubs and defining routes of the vehicles for serving multi-product customers demand in such way that each selected hub must be visited once for delivering, though they can be visited many times for picking up. We propose a mixed integer linear programming formulation and a heuristic approach for this problem. Since there is not any instance compatible with LRP-MPPD in the literature, we have extended known LRP instances to evaluate the performance of the proposed approach. A comparison with CPLEX shows that the proposed algorithm is a viable approach to solve small and large size LRP-MPPD instances.

关键词： Supply Chain Management Location-Routing Problem Pickup and Delivery Multi Products integer programming formulation Heuristic

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：