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

The Multiple Steiner TSP with order constraints: complexity and optimization algorithms

SOFT COMPUTING 2020年第23期24卷 17957-17968页

作者： Gabrel, Virginie Mahjoub, A. Ridha Taktak, Raouia Uchoa, Eduardo PSL Res Univ Univ Paris Dauphine CNRS LAMSADE F-75016 Paris France Univ Sfax CRNS ISIMS Sfax Tunisia Univ Sfax CRNS LT2S Sfax Tunisia Univ Fed Fluminense Dept Engn Prod Niteroi RJ Brazil

We consider a variant of the Travelling Salesman Problem (TSP), the Multiple Steiner TSP with Order constraints (MSTSPO). Consider a weighted undirected graph and a set of salesmen, and each salesman is associated with a set of compulsory vertices to visit, called terminals. The MSTSPO consists in finding a minimum-cost subgraph containing for each salesman a tour going in a specified order through its terminals. Along with its importance from a theoretical point of view, the problem is also challenging in practice since it has applications in telecommunication networks. We show that the problem is NP-hard even for a single salesman and propose integer programming formulations. We then devise both branch-and-cut and branch-and-Price algorithms to solve the problem. The extensive computational results are presented, showing the efficiency of our algorithms.

关键词： Steiner TSP Order constraints Integer linear programming branch-and-Price algorithm branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

The inventory routing problem with split deliveries

引用

NETWORKS 2023年第4期82卷 400-413页

作者： Dinh, Nho Minh Archetti, Claudia Bertazzi, Luca Univ Brescia Dept Econ & Management Brescia Italy ESSEC Business Sch Dept Informat Syst Decis Sci & Stat Paris France

We study the benefit of introducing split deliveries in the inventory routing problem (IRP), both when the order-up-to level (OU) and the maximum level replenishment policies are applied. We first propose a mathematical formulation and solve it by implementing a branch-and-cut algorithm. Then, we carry out a worst-case analysis to show the cost increase we have in the worst case by using unsplit deliveries instead of split deliveries, both for the OU and the maximum-level replenishment policies. Extensive computational results on benchmark instances allow us to evaluate the benefit of introducing split deliveries. Finally, a sensitivity analysis on customer demands, initial inventory levels, maximum inventory levels and distance to the depot allows us to understand the instance features that make split deliveries effective in IRPs.

关键词： branch-and-cut algorithm inventory routing problems maximum-level order-up-to-level split deliveries worst-case analysis

来源：评论

学校读者我要写书评

暂无评论

On integer and bilevel formulations for the k-vertex cut problem

引用

MATHEMATICAL PROGRAMMING COMPUTATION 2020年第2期12卷 133-164页

作者： Furini, Fabio Ljubic, Ivana Malaguti, Enrico Paronuzzi, Paolo Univ Paris 09 LAMSADE Paris France ESSEC Business Sch Paris Cergy France Univ Bologna DEI Bologna Italy

The family of critical node detection problems asks for finding a subset of vertices, deletion of which minimizes or maximizes a predefined connectivity measure on the remaining network. We study a problem of this family called the k-vertex cut problem. The problem asks for determining the minimum weight subset of nodes whose removal disconnects a graph into at least k components. We provide two new integer linear programming formulations, along with families of strengthening valid inequalities. Both models involve an exponential number of constraints for which we provide poly-time separation procedures and design the respective branch-and-cut algorithms. In the first formulation one representative vertex is chosen for each of the k mutually disconnected vertex subsets of the remaining graph. In the second formulation, the model is derived from the perspective of a two-phase Stackelberg game in which a leader deletes the vertices in the first phase, and in the second phase a follower builds connected components in the remaining graph. Our computational study demonstrates that a hybrid model in which valid inequalities of both formulations are combined significantly outperforms the state-of-the-art exact methods from the literature.

关键词： Vertex cut Mixed-integer linear programming Bilevel programming branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Formulations for an inventory routing problem

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2014年第3期21卷 353-374页

作者： Archetti, Claudia Bianchessi, Nicola Irnich, Stefan Speranza, M. Grazia Univ Brescia Dept Econ & Management Brescia Italy Johannes Gutenberg Univ Mainz Chair Logist Management D-55122 Mainz Germany

In this paper, we present and compare formulations for the inventory routing problem (IRP) where the demand of customers has to be served, over a discrete time horizon, by capacitated vehicles starting and ending their routes at a depot. The objective of the IRP is the minimization of the sum of inventory and transportation costs. The formulations include known and new mathematical programming formulations. Valid inequalities are also presented. The formulations are tested on a large set of benchmark instances. One of the most significant conclusions is that the formulations that use vehicle-indexed variables are superior to the more compact, aggregate formulations.

关键词： supply chain management branch-and-cut algorithm integer programming routing problems

来源：评论

学校读者我要写书评

暂无评论

Solving VLSI design and DNA sequencing problems using bipartization of graphs

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2012年第2期51卷 749-781页

作者： Fouilhoux, Pierre Mahjoub, A. Ridha Univ Paris 09 LAMSADE CNRS F-75775 Paris 16 France Univ Paris 06 Lab LIP6 CNRS UMR 7626 F-75005 Paris France

In this paper we consider the 2-layer constrained via minimization problem and the SNP haplotype assembly problem. The former problem arises in the design of integrated and printed circuit boards, and the latter comes up in the DNA sequencing process for diploid organisms. We show that, for any maximum junction degree, the problem can be reduced to the maximum bipartite induced subgraph problem. Moreover we show that the SNP haplotype assembly problem can also be reduced to the maximum bipartite induced subgraph problem for the so-called minimum error correction criterion. We give a partial characterization of the bipartite induced subgraph polytope. Using this, we devise a branch-and-cut algorithm and report some experimental results. This algorithm has been used to solve real and large instances.

关键词： Electronics Genomics Bipartite induced subgraph problem Polyhedral approach branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

An exact approach for the r-interdiction covering problem with fortification

引用

CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH 2019年第1期27卷 111-131页

作者： Roboredo, Marcos Costa Aizemberg, Luiz Pessoa, Artur Alves Univ Fed Fluminense Dept Engn Prod Rua Passo Patria 156 BR-24210240 Niteroi RJ Brazil Banco Nacl Desenvolvimento Ave Republ Chile 100 BR-20031917 Rio De Janeiro RJ Brazil

In this paper we treat the r-interdiction covering problem with fortification (RICF). The environment of this problem is composed of a set of customers J and a set of facilities I. For each customer j, there is set of facilities containing the facilities that can cover the demand of j. The system efficiency is given by the sum of the total covered demand. The facilities are subject to interdictions. When a facility is interdicted, it can not cover the demand of any customer. To mitigate the negative impact of the interdictions on the system efficiency, the system planner can fortify a subset of facilities. If a facility is fortified then it can not be interdicted. The RICF consists of choosing q facilities to be fortified knowing that r not fortified facilities will be interdicted at the worst case. We propose a branch-and-cut algorithm for the problem. Our results are compared with the exact method found in the literature, being faster for the most instances, mainly the large ones.

关键词： Integer programming branch-and-cut algorithm r-Interdiction covering problem with fortification

来源：评论

学校读者我要写书评

暂无评论

Polyhedral techniques in combinatorial optimization II: applications and computations

引用

STATISTICA NEERLANDICA 1999年第2期53卷 131-177页

作者： Aardal, K van Hoesel, CPM Univ Utrecht Dept Comp Sci NL-3508 TB Utrecht Netherlands Univ Limburg Dept Quantitat Econ NL-6200 MD Maastricht Netherlands

The polyhedral approach is one of the most powerful techniques available for solving hard combinatorial optimization problems. The main idea behind the technique is to consider the linear relaxation of the integer combinatorial optimization problem, and try to iteratively strengthen the linear formulation by adding violated strong valid inequalities, i.e., inequalities that are violated by the current fractional solution but satisfied by all feasible solutions, and that define high-dimensional faces, preferably facets, of the convex hull of feasible solutions. If we have the complete description of the convex hull of feasible solutions at hand all extreme points of this formulation are integral, which means that we can solve the problem as a linear programming problem. Linear programming problems are known to be computationally easy. In Part 1 of this article we discuss theoretical aspects of polyhedral techniques. Here we will mainly concentrate on the computational aspects. In particular we discuss how polyhedral results are used in cutting plane algorithms. We also consider a few theoretical issues not treated in Part 1, such as techniques for proving that a certain inequality is facet defining, and that a certain linear formulation gives a complete description of the convex hull of feasible solutions. We conclude the article by briefly mentioning some alternative techniques for solving combinatorial optimization problems.

关键词： strong valid inequalities facets convex hull cutting plane algorithm branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Scheduling optimization for two crossover automated stacking cranes considering relocation

引用

OPERATIONAL RESEARCH 2022年第3期22卷 2099-2120页

作者： Chen, Sumin Zeng, Qingcheng Hu, Yushan Dalian Maritime Univ Sch Maritime Econ & Management 1 Linghai Rd Dalian 116026 Peoples R China Dalian Maritime Univ Collaborat Innovat Ctr Transport Studies 1 Linghai Rd Dalian 116026 Peoples R China

In this paper, we focus on the two crossover automated stacking cranes (ASCs) scheduling problem that arises at a storage block in an automated container terminal. To address relocation during retrieval operations, we use two methods with job precedence constraints: (1) adjusting the operation sequence of jobs to avoid relocation operations and (2) optimizing the dispatching for relocation operations to improve the efficiency of ASCs. Therefore, the method proposed in this paper optimizes the dispatching for storage, retrieval, and relocation and the routes of the ASCs while considering interferences between the ASCs and job precedence constraints. A branch-and-cut algorithm based on the characteristics of the problem is designed to decompose the problem into two problem classes connected via logic-based Benders constraints. Numerical experiments indicate that the proposed algorithm is efficient for solving realistically sized problems. Furthermore, the influence of the number of relocations is investigated based on experimental results.

关键词： Container terminals Automated stacking crane scheduling Relocation Benders constraints branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Two-edge connectivity with disjunctive constraints: Polyhedral analysis and branch-and-cut

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2023年 184卷

作者： Almudahka, Intesar Diarrassouba, Ibrahima Mahjoub, A. Ridha Taktak, Raouia Kuwait Univ Coll Sci Dept Stat & Operat Res Safat Kuwait Univ Le Havre Normandy UNIHAVRE LMAH CNRSFR 3335 F-76600 Le Havre France Univ Paris 09 PSL LAMSADE CNRSUMR 7243 Paris France Univ Sfax ISIMS Sfax Tunisia Univ Sfax Smrts CRNS Sfax Tunisia

In this paper we consider the two-edge-connected subgraph problem with disjunctive constraints. We inves-tigate the convex hull of the solutions to this problem. We describe several classes of valid inequalities, and discuss their facial aspect. We also devise separation routines for these inequalities. Using this, we propose a branch-and-cut algorithm for the problem along with an extensive computational study is presented.

关键词： Network survivability Connectivity constraints Disjunctive constraints branch-and-cut algorithm Facet

来源：评论

学校读者我要写书评

暂无评论

The location-dispatching problem: Polyhedral results and content delivery network design

引用

DISCRETE APPLIED MATHEMATICS 2014年第Part1期164卷 68-85页

作者： Chretienne, Philippe Fouilhoux, Pierre Gourdin, Eric Segura, Jean-Mathieu Univ Paris 06 Lab LIP6 F-75005 Paris France France Telecom R&D Orange Labs F-92794 Issy Les Moulineaux 9 France

Let G = (V, A) be a directed graph and F be a set of items. The Location-Dispatching Problem consists of determining subsets L-1 subset of F F located at nodes i is an element of V, minimizing the sum of two costs: a piecewise linear installation cost associated with L-1 and an access cost for each node of V to reach a copy of each item of F. We formulate this problem as a linear program with binary variables x and integer variables z. We propose a facial study of the associated polytope and we introduce the so-called integrity hop cost inequalities that force z to be an integer as soon as x is binary. Using this, we devise a branch-andcut algorithm and report some experimental results. This algorithm has been used to solve Content Delivery Network instances in order to optimize a Video On Demand (VoD) system. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Location Integer program Polytope branch-and-cut algorithm CDN design

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：