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

mixed integer programming formulations for the generalized traveling salesman problem with time windows

4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH 2021年第4期19卷 571-592页

作者： Yuan, Yuan Cattaruzza, Diego Ogier, Maxime Rousselot, Cyriaque Semet, Frederic Univ Lille CRIStAL Lille CNRS INRIACent LilleUMR 9189 Lille France

The generalized traveling salesman problem with time windows (GTSPTW) is defined on a directed graph where the vertex set is partitioned into clusters. One cluster contains only the depot. Each vertex is associated with a time window, during which the visit must take place if the vertex is visited. The objective is to find a minimum cost tour starting and ending at the depot such that each cluster is visited exactly once and time constraints are respected, i.e., for each cluster, a single vertex is visited during its time window. In this paper, four mixed integer linear programming formulations for the GTSPTW are proposed and compared. They are based on different definitions of variables. All the formulations are compact, which means the number of decision variables and constraints is polynomial with respect to the size of the instance. Dominance relations between their linear relaxations are established theoretically. Computational experiments are conducted to compare the linear relaxations and branch-and-bound performances of the four formulations. The results show that two formulations are better than the other ones.

关键词： Generalized traveling salesman problem Time windows mixed integer programming formulations Last mile delivery

来源：评论

学校读者我要写书评

暂无评论

The impact of service level constraints in deterministic lot sizing with backlogging

引用

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 2018年 79卷 91-103页

作者： Gruson, Matthieu Cordeau, Jean-Francois Jans, Raf HEC Montreal 3000 Chemin Cote St Catherine Montreal PQ H3T 2A7 Canada Gerad 3000 Chemin Cote St Catherine Montreal PQ H3T 2A7 Canada

This paper studies the impact of service level constraints in the context of the capacitated and uncapacitated lot sizing problems with deterministic demand and backlogging over a discrete and finite time horizon. Because the standard formulation of these problems cannot distinguish between a backlog and a backorder, we use a reformulation to explicitly make this distinction. We then formulate several service level constraints adapted from the stochastic inventory control literature and introduce new ones. We analyze the impact of these constraints on the structure of the optimal solutions in terms of the number of backorders and total backlog, and on the performance of these solutions in terms of various service level indicators (proportion of periods with no backlog, proportion of backorders over total demand, maximum delay, average unit waiting time for an item). We also consider the introduction of various types of back-ordering costs (both fixed and duration dependent) and study their impact. We find that they tend to stabilize the structure of solutions, regardless of the service level constraints imposed. Finally, we analyze the impact of a first-in first-out order management policy and show that it helps improving most solutions. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Production planning and control Lot sizing Deterministic demand Service levels Backlogging mixed integer programming formulations

来源：评论

学校读者我要写书评

暂无评论

Efficient symmetry breaking formulations for the job grouping problem

引用

COMPUTERS & OPERATIONS RESEARCH 2013年第4期40卷 1132-1142页

作者： Jans, Raf Desrosiers, Jacques HEC Montreal Montreal PQ H3T 2A7 Canada Gerad Montreal PQ H3T 2A7 Canada

The job grouping problem consists of assigning a set of jobs, each with a specific set of tool requirements, to machines with a limited tool capacity in order to minimize the number of machines needed. Traditionally, a formulation has been used that assigns jobs to machines. However, such a formulation contains a lot of symmetry since the machines are identical and they can be permuted in any feasible solution. We propose a new formulation for this problem, based on the asymmetric representatives formulation (ARF) idea. This formulation eliminates the symmetry between the identical machines. We further propose various symmetry breaking constraints, including variable reduction and lexicographic ordering constraints, which can be added to the traditional formulation. These formulations are tested on a data set from the literature and newly generated data sets using a state-of-the-art commercial solver, which includes symmetry breaking features. A first remarkable conclusion is that the order of the input data has a significant effect on the LP relaxation bound and CPU times for the ARF and some of the traditional formulations with variable reduction. The CPU time of the formulation with lexicographic ordering constraints on the jobs is also substantially affected, but not its LP bound. A second interesting conclusion is that the ARF is able to solve the problems of a large standard set from the literature to optimality 40 times faster than the traditional formulation and 7 times faster than a specialized Branch-and-Bound algorithm from the literature. For a data set with large instances, the traditional formulation extended with limited lexicographic constraints seems to be the best formulation. (C) 2012 Elsevier Ltd. All rights reserved.

关键词： Job grouping Clustering problems Symmetry breaking mixed integer programming formulations

来源：评论

学校读者我要写书评

暂无评论

MILP models for the optimization of real production lines

引用

CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH 2015年第4期23卷 899-912页

作者： Hajba, Tamas Horvath, Zoltan Szechenyi Istvan Univ Dept Math & Comp Sci H-9026 Gyor Hungary

A special class of the permutation flow shop problems (PFSPs) with makespan minimization which contains repeated jobs, limited buffer sizes between the machines and fixed number of palettes that carry the jobs on the production line is introduced in this paper. We define the related PB-R-PFSP, the Permutation with Repetition Flow Shop Problem with Palettes and Buffers, and construct new mixed integer linear programming (MILP) models for this problem. The effectiveness of the MILP models and the influence of the number of palettes and buffers on the problems are investigated experimentally.

关键词： Flow shop scheduling Minimizing makespan mixed integer programming formulations Computational comparisons

来源：评论

学校读者我要写书评

暂无评论

A comparison of formulations for a three-level lot sizing and replenishment problem with a distribution structure

引用

COMPUTERS & OPERATIONS RESEARCH 2019年 111卷 297-310页

作者： Gruson, Matthieu Bazrafshan, Majid Cordeau, Jean-Francois Jans, Raf HEC Montreal 3000 Chemin Cote St Catherine Montreal PQ H3T 2A7 Canada Gerad 3000 Chemin Cote St Catherine Montreal PQ H3T 2A7 Canada

We address a three-level lot sizing and replenishment problem with a distribution structure (3LSPD), which is an extension of the one-warehouse multi-retailer problem (OWMR). We consider one production plant that produces one type of item over a discrete and finite planning horizon. The items produced are used to replenish warehouses and then retailers using direct shipments. Each retailer is linked to a unique warehouse and there are no transfers between warehouses nor between retailers. We also assume that transportation is uncapacitated. However, we consider the possibility of imposing production capacity constraints at the production plant level. The objective is to minimize the sum of the fixed production and replenishment costs and of the variable inventory holding costs at all three levels. We compare 13 different MIP formulations to solve the problem. All of these formulations are adapted from existing MIP formulations found in the one-warehouse multi-retailer literature, but most formulations are new in the context of the 3LSPD. We run experiments on both balanced and unbalanced networks. Our results indicate that the multi-commodity formulation is well suited for uncapacititated instances and that the echelon stock reformulations are better for capacitated instances. They also show that the richer formulations are not necessarily the best ones and that the unbalanced instances are harder to solve. (C) 2019 Elsevier Ltd. All rights reserved.

关键词： Production planning and control Lot sizing Replenishment mixed integer programming formulations Deterministic demand One-warehouse multi-retailer problem Multi-level

来源：评论

学校读者我要写书评

暂无评论

New effective MILP models for PFSPs arising from real applications

引用

CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH 2013年第4期21卷 729-744页

作者： Hajba, Tamas Horvath, Zoltan Szechenyi Istvan Univ Dept Math & Comp Sci H-9026 Gyor Hungary

Permutation flow shop problems (PFSPs) with makespan minimization that model production lines working in industry often have some special features: they are typically large-scale and the jobs can be sorted into types so that jobs of the same type have equal processing time values at each machine. We define the related R-PFSP, the Permutation with Repetition Flow Shop Problem, which is of less complexity if the number of types is bounded. Moreover, a subproblem set of R-PFSPs, the RL-PFSP is considered too, where only those permutations are in the design space in which subsequent tuples of a certain size contain jobs of the same type. We construct adequate new MILP models for R-PFSPs and RL-PFSPs and investigate their effectiveness experimentally. We demonstrate that via our new MILP models significantly larger problems can be solved than via the classical MILP models.

关键词： Flow shop scheduling Minimizing makespan mixed integer programming formulations Computational comparisons

来源：评论

学校读者我要写书评

暂无评论

Small and strong formulations for unions of convex sets from the Cayley embedding

引用

MATHEMATICAL programming 2019年第1-2期177卷 21-53页

作者： Vielma, Juan Pablo MIT Sloan Sch Management 77 Massachusetts Ave Cambridge MA 02139 USA

There is often a significant trade-off between formulation strength and size in mixed integer programming. When modeling convex disjunctive constraints (e.g. unions of convex sets), adding auxiliary continuous variables can sometimes help resolve this trade-off. However, standard formulations that use such auxiliary continuous variables can have a worse-than-expected computational effectiveness, which is often attributed precisely to these auxiliary continuous variables. For this reason, there has been considerable interest in constructing strong formulations that do not use continuous auxiliary variables. We introduce a technique to construct formulations without these detrimental continuous auxiliary variables. To develop this technique we introduce a natural non-polyhedral generalization of the Cayley embedding of a family of polytopes and show it inherits many geometric properties of the original embedding. We then show how the associated formulation technique can be used to construct small and strong formulation for a wide range of disjunctive constraints. In particular, we show it can recover and generalize all known strong formulations without continuous auxiliary variables.

关键词： mixed integer nonlinear programming mixed integer programming formulations Disjunctive constraints

来源：评论

学校读者我要写书评

暂无评论

A survey of network interdiction models and algorithms

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2020年第3期283卷 797-811页

作者： Smith, J. Cole Song, Yongjia Clemson Univ Dept Ind Engn Clemson SC 29631 USA

This paper discusses the development of interdiction optimization models and algorithms, with an emphasis on mathematical programming techniques and future research challenges in the field. After presenting basic interdiction concepts and notation, we recount the motivation and models behind founding research in the network interdiction field. Next, we examine some of the most common means of solving interdiction problems, focusing on dualization models and extended formulations solvable by row-generation techniques. We then examine contemporary interdiction problems involving incomplete information, information asymmetry, stochasticity, and dynamic play. We conclude by discussing several emerging applications in the field of network interdiction. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Networks Network interdiction Min-max games mixed integer programming formulations Decomposition algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：