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

Valid inequalities for the single-item capacitated lot sizing problem with step-wise costs

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2009年第2期198卷 412-434页

作者： Akbalik, A. Pochet, Y. Univ Catholique Louvain CORE B-1348 Louvain Belgium

This paper presents a new class of valid inequalities for the single-item capacitated lot sizing problem with step-wise production costs (LS-SW). constant sized batch production is carried out with a limited production capacity in order to satisfy the customer demand over a finite horizon. A new class of valid inequalities we call mixed flow cover, is derived from the existing integer flow cover inequalities by a lifting procedure. The lifting coefficients are sequence independent when the batch sizes (V) and the production capacities (P) are constant and when V divides P. When the restriction of the divisibility is removed, the lifting coefficients are shown to be sequence independent. We identify some cases where the mixed flow cover inequalities are facet defining. We Propose a cutting plane algorithm for different classes of valid inequalities introduced in the paper. The exact separation algorithm proposed for the constant capacitated case runs in polynomial time. Computational results show the efficiency of the new class mixed flow cover compared to the existing methods. (C) 2008 Published by Elsevier B.V.

关键词： Integer programming Single-item capacitated lot sizing problem Flow cover inequalities cutting plane algorithm

来源：评论

学校读者我要写书评

暂无评论

Shelter Location and Evacuation Route Assignment Under Uncertainty: A Benders Decomposition Approach

引用

TRANSPORTATION SCIENCE 2018年第2期52卷 416-436页

作者： Bayram, Vedat Yaman, Hande TED Univ Dept Ind Engn TR-06420 Ankara Turkey Bilkent Univ Dept Ind Engn TR-06800 Bilkent Turkey

Shelters are safe facilities that protect a population from possible damaging effects of a disaster. For that reason, shelter location and traffic assignment decisions should be considered simultaneously for an efficient evacuation plan. In addition, as it is very difficult to anticipate the exact place, time, and scale of a disaster, one needs to take into account the uncertainty in evacuation demand, the disruption/degradation of evacuation road network structure, and the disruption in shelters. In this study, we propose an exact algorithm based on Benders decomposition to solve a scenario-based two-stage stochastic evacuation planning model that optimally locates shelters and that assigns evacuees to shelters and routes in an efficient and fair way to minimize the expected total evacuation time. The second stage of the model is a second-order cone programming problem, and we use duality results for second-order cone programming in a Benders decomposition setting. We solve practical-size problems with up to 1,000 scenarios in moderate CPU times. We investigate methods such as employing a multicut strategy, deriving Pareto-optimal cuts, and using a preemptive priority multiobjective program to enhance the proposed algorithm. We also use a cutting plane algorithm to solve the dual subproblem since it contains a constraint for each possible path. Computational results confirm the efficiency of our algorithms.

关键词： disaster management shelter location two-stage stochastic programming second-order cone programming cutting plane algorithm evacuation traffic management constrained system optimal Benders decomposition

来源：评论

学校读者我要写书评

暂无评论

Computational study of separation algorithms for clique inequalities

引用

SOFT COMPUTING 2019年第9期23卷 3013-3027页

作者： Marzi, Francesca Rossi, Fabrizio Smriglio, Stefano Univ Aquila DISIM Via Vetoio I-67010 Laquila AQ Italy

Clique inequalities appear in linear descriptions of many combinatorial optimisation problems. In general, they form an exponential family and, in addition, the associated separation problem is strongly NP-hard, being equivalent to a maximum weight clique problem. Therefore, most of the known (both exact and heuristic) separation procedures follow the decomposition scheme of a maximum clique algorithm. We introduce a new heuristic, aimed at constructing a collection of (violated) clique inequalities covering all the edges of the underlying graph. We present an extensive computational experience showing that this closely approximates the results of an exact separation oracle while being faster than standard heuristics.

关键词： Clique inequalities Separation problem cutting plane algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimal berth allocation and time-invariant quay crane assignment in container terminals

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2014年第1期235卷 88-101页

作者： Turkogullari, Yavuz B. Taskin, Z. Caner Aras, Necati Altinel, I. Kuban Maltepe Univ Dept Ind Engn Istanbul Turkey Bogazici Univ Dept Ind Engn TR-34342 Istanbul Turkey

Due to the dramatic increase in the world's container traffic, the efficient management of operations in seaport container terminals has become a crucial issue. In this work, we focus on the integrated planning of the following problems faced at container terminals: berth allocation, quay crane assignment (number), and quay crane assignment (specific). First, we formulate a new binary integer linear program for the integrated solution of the berth allocation and quay crane assignment (number) problems called BACAP. Then we extend it by incorporating the quay crane assignment (specific) problem as well, which is named BACASP. Computational experiments performed on problem instances of various sizes indicate that the model for BACAP is very efficient and even large instances up to 60 vessels can be solved to optimality. Unfortunately, this is not the case for BACASP. Therefore, to be able to solve large instances, we present a necessary and sufficient condition for generating an optimal solution of BACASP from an optimal solution of BACAP using a post-processing algorithm. In case this condition is not satisfied, we make use of a cutting plane algorithm which solves BACAP repeatedly by adding cuts generated from the optimal solutions until the aforementioned condition holds. This method proves to be viable and enables us to solve large BACASP instances as well. To the best of our knowledge, these are the largest instances that can be solved to optimality for this difficult problem, which makes our work applicable to realistic problems. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Berth allocation Crane assignment Container terminals cutting plane algorithm

来源：评论

学校读者我要写书评

暂无评论

Solving two-stage robust optimization problems using a column-and-constraint generation method

引用

OPERATIONS RESEARCH LETTERS 2013年第5期41卷 457-461页

作者： Zeng, Bo Zhao, Long Univ S Florida Dept Ind & Management Syst Engn Tampa FL 33620 USA

In this paper, we present a column-and-constraint generation algorithm to solve two-stage robust optimization problems. Compared with existing Benders-style cutting plane methods, the column-and-constraint generation algorithm is a general procedure with a unified approach to deal with optimality and feasibility. A computational study on a two-stage robust location-transportation problem shows that it performs an order of magnitude faster. (c) 2013 Elsevier B.V. All rights reserved.

关键词： Two-stage robust optimization cutting plane algorithm Location-and-transportation

来源：评论

学校读者我要写书评

暂无评论

A Generator-Matrix-Based Approach for Adaptively Generating Cut-Inducing Redundant Parity Checks

引用

IEEE COMMUNICATIONS LETTERS 2016年第4期20卷 640-643页

作者： Falsafain, Hossein Mousavi, Sayyed Rasoul Isfahan Univ Technol Dept Elect & Comp Engn Esfahan *** Iran Amirkabir Univ Technol Dept Comp Engn & Informat Technol Tehran *** Iran

A generator matrix (GM)-based approach for adaptively deriving cut-inducing redundant parity checks (RPCs) during the adaptive linear programming decoding algorithm is presented. More precisely speaking, if the decoder gets stuck in a non-integral pseudocodeword, then the resulting RPCs are likely to provide violated forbidden-set inequalities that can separate this non-integral optimal solution from the feasible region. The described approach can be viewed as a GM-based counterpart of the approach proposed by Zhang and Siegel in 2012. For binary linear codes of low rate, while providing the same error-correcting performance, our approach requires much less computational time compared to its analogue. Index Terms-Adaptive linear programming (ALP)

关键词： Adaptive linear programming (ALP) decoding cut-inducing redundant parity check (RPC) cutting plane algorithm heuristic separation algorithm

来源：评论

学校读者我要写书评

暂无评论

On the most imbalanced orientation of a graph

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2018年第2期36卷 637-669页

作者： Ben-Ameur, Walid Glorieux, Antoine Neto, Jose Univ Paris Saclay CNRS Telecom SudParis SAMOVAR 9 Rue Charles Fourier F-91011 Evry France

We study the problem of orienting the edges of a graph such that the minimum over all the vertices of the absolute difference between the outdegree and the indegree of a vertex is maximized. We call this minimum the imbalance of the orientation, i.e. the higher it gets, the more imbalanced the orientation is. The studied problem is denoted by . We first characterize graphs for which the optimal objective value of is zero. Next we show that is generally NP-hard and cannot be approximated within a ratio of for any constant in polynomial time unless even if the minimum degree of the graph equals 2. Then we describe a polynomial-time approximation algorithm whose ratio is almost equal to . An exact polynomial-time algorithm is also derived for cacti. Finally, two mixed integer linear programming formulations are presented. Several valid inequalities are exhibited with the related separation algorithms. The performance of the strengthened formulations is assessed through several numerical experiments.

关键词： Graph theory Orientation Complexity Mixed integer programming cutting plane algorithm (In)approximability Cactus

来源：评论

学校读者我要写书评

暂无评论

Relatively-Paired Space Analysis: Learning a Latent Common Space From Relatively-Paired Observations

引用

INTERNATIONAL JOURNAL OF COMPUTER VISION 2015年第3期113卷 176-192页

作者： Kuang, Zhanghui Wong, Kwan-Yee K. Univ Hong Kong Dept Comp Sci Pokfulam Hong Kong Peoples R China

Discovering a latent common space between different modalities plays an important role in cross-modality pattern recognition. Existing techniques often require absolutely-paired observations as training data, and are incapable of capturing more general semantic relationships between cross-modality observations. This greatly limits their applications. In this paper, we propose a general framework for learning a latent common space from relatively-paired observations (i.e., two observations from different modalities are more-likely-paired than another two). Relative-pairing information is encoded using relative proximities of observations in the latent common space. By building a discriminative model and maximizing a distance margin, a projection function that maps observations into the latent common space is learned for each modality. Cross-modality pattern recognition can then be carried out in the latent common space. To speed up the learning procedure for large scale training data, the problem is reformulated into learning a structural model, which is efficiently solved by the cutting plane algorithm. To evaluate the performance of the proposed framework, it has been applied to feature fusion, cross-pose face recognition, text-image retrieval and attribute-image retrieval. Experimental results demonstrate that the proposed framework outperforms other state-of-the-art approaches.

关键词： Multi-modality analysis Multi-viewanalysis Absolutely-paired observations Relatively-paired observations Structural learning cutting plane algorithm

来源：评论

学校读者我要写书评

暂无评论

Inverse integer optimization with an imperfect observation

引用

OPERATIONS RESEARCH LETTERS 2020年第6期48卷 763-769页

作者： Moghaddass, Mahsa Terekhov, Daria Concordia Univ Gina Cody Sch Engn & Comp Sci Dept Mech Ind & Aerosp Engn Montreal PQ Canada

This study develops and evaluates methods for inverse integer optimization problems with an imperfect observation where the unknown parameters are the cost coefficients. We propose a cutting plane algorithm for this problem and compare it to a heuristic which solves the inverse of the linear relaxation of the forward problem. We then propose a hybrid approach that initializes the cutting plane algorithm from the solution of the heuristic. (c) 2020 Elsevier B.V. All rights reserved.

关键词： Inverse optimization Inverse integer optimization Integer programming cutting plane algorithm Imperfect observation

来源：评论

学校读者我要写书评

暂无评论

An exact method for trilevel hub location problem with interdiction

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2024年第3期319卷 696-710页

作者： Ramamoorthy, Prasanna Jayaswal, Sachin Sinha, Ankur Vidyarthi, Navneet Indian Inst Technol Delhi Dept Management Studies New Delhi 110016 India Indian Inst Management Ahmedabad Operat & Decis Sci Ahmadabad 380015 Gujarat India Concordia Univ John Molson Sch Business Montreal PQ H3G 1M8 Canada Concordia Univ CIRRELT Montreal PQ H3G 1M8 Canada

In this paper, we study the problem of designing a hub network that is robust against deliberate attacks (interdictions). The problem is modeled as a three-level, two-player Stackelberg game, in which the network designer (defender) acts first to locate hubs to route a set of flows through the network. The attacker (interdictor) acts next to interdict a subset of the located hubs in the designer's network, followed again by the defender who routes the flows through the remaining hubs in the network. We model the defender's problem as a trilevel optimization problem, wherein the attacker's response is modeled as a bilevel hub interdiction problem. We study such a trilevel problem on three variants of hub location problems studied in the literature namely: p-hub median problem, p-hub center, and p-hub maximal covering problems. We present a cutting plane based exact method to solve the problem. The cutting plane method uses supervalid inequalities, which is obtained from the solution of the lower level interdiction problem. To solve the lower level hub interdiction problem efficiently, we propose a penalty-based reformulation of the problem. Using the reformulation, we present a branch-and-cut based exact approach to solve the problem efficiently. We conduct experiments to show the computational advantages of the above algorithm. To the best of our knowledge, the cutting plane approach proposed in this paper is among the first exact method to solve trilevel location-interdiction problems. Our computational results show interesting implications of incorporating interdiction risks in the hub location problem.

关键词： Location Interdiction Trilevel programming cutting plane algorithm Stackelberg games

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：