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

Theorems of the alternative for conic integer programming

OPERATIONS RESEARCH LETTERS 2020年第3期48卷 329-335页

作者： Ajayi, Temitayo Suriyanarayana, Varun Schaefer, Andrew J. Rice Univ Dept Computat & Appl Math Houston TX 77005 USA Cornell Univ Dept Operat Res & Informat Engn Ithaca NY 14853 USA

Farkas' Lemma is a foundational result in linear programming, with implications in duality, optimality conditions, and stochastic and bilevel programming. Its generalizations are known as theorems of the alternative. There exist theorems of the alternative for integer programming and conic programming. We present theorems of the alternative for conic integer programming. We provide a nested procedure to construct a function that characterizes feasibility over right-hand sides and can determine which statement in a theorem of the alternative holds. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Farkas' lemma conic integer programming Superadditivity

来源：评论

学校读者我要写书评

暂无评论

Supermodular covering knapsack polytope

引用

DISCRETE OPTIMIZATION 2015年 18卷 74-86页

作者： Atamtuerk, Alper Bhardwaj, Avinash Univ Calif Berkeley Ind Engn & Operat Res Berkeley CA 94720 USA

The supermodular covering knapsack set is the discrete upper level set of a non-decreasing supermodular function. Submodular and supermodular knapsack sets arise naturally when modeling utilities, risk and probabilistic constraints on discrete variables. In a recent paper Atamturk and Narayanan (2009) study the lower level set of a non-decreasing submodular function. In this complementary paper we describe pack inequalities for the supermodular covering knapsack set and investigate their separation, extensions and lifting. We give sequence-independent upper bounds and lower bounds on the lifting coefficients. Furthermore, we present a computational study on using the polyhedral results derived for solving 0-1 optimization problems over conic quadratic constraints with a branch-and-cut algorithm. (C) 2015 Elsevier B.V. All rights reserved.

关键词： conic integer programming Supermodularity Lifting Probabilistic covering knapsack constraints Branch-and-cut algorithms

来源：评论

学校读者我要写书评

暂无评论

Polyhedral results for a class of cardinality constrained submodular minimization problems

引用

DISCRETE OPTIMIZATION 2017年 24卷 87-102页

作者： Yu, Jiajin Ahmed, Shabbir Georgia Inst Technol Coll Comp Atlanta GA 30332 USA Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA

Motivated by concave cost combinatorial optimization problems, we study the following mixed integer nonlinear set: P = {(w, x) is an element of R x {0,1}(n) : w >= f(a'x), e'x R is a concave function, n an... 详细信息

Motivated by concave cost combinatorial optimization problems, we study the following mixed integer nonlinear set: P = {(w, x) is an element of R x {0,1}(n) : w >= f(a'x), e'x <= k} where f : R -> R is a concave function, n and k are positive integers, alpha is an element of R-n is a nonnegative vector, e is an element of R-n is a vector of ones, and x'y denotes the scalar product of vectors x and y of same dimension. A standard linearization approach for P is to exploit the fact that f(a'x) is submodular with respect to the binary vector x. We extend this approach to take the cardinality constraint e'x <= k into account and provide a full description of the convex hull of P when the vector a has identical components. We also develop a family of facet-defining inequalities when the vector a has nonidentical components. Computational results using the proposed inequalities in a branch-and-cut framework to solve mean-risk knapsack problems show significant decrease in both time and the number of nodes over standard methods. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Cardinality constraint Submodular minimization conic integer programming Cutting planes

来源：评论

学校读者我要写书评

暂无评论

A computational study for common network design in multi-commodity supply chains

引用

COMPUTERS & OPERATIONS RESEARCH 2014年 44卷 206-213页

作者： Wu, Ting Zhang, Kaike Nanjing Univ Sch Business Nanjing Jiangsu Peoples R China Nanjing Univ Dept Math Nanjing Jiangsu Peoples R China Univ Tennessee Dept Ind & Syst Engn Knoxville TN 37996 USA

In this paper, we study a supply chain network design problem which consists of one external supplier, a set of potential distribution centers, and a set of retailers, each of which is faced with uncertain demands for multiple commodities. The demand of each retailer is fulfilled by a single distribution center for all commodities. The goal is to minimize the system-wide cost including location, transportation, and inventory costs. We propose a general nonlinear integer programming model for the problem and present a cutting plane approach based on polymatroid inequalities to solve the model. Randomly generated instances for two special cases of our model, i.e., the single-sourcing UPL&TAP and the single-sourcing multi-commodity location-inventory model, are provided to test our algorithm. Computational results show that the proposed algorithm can solve moderate-sized problem instances efficiently. (C) 2013 Elsevier Ltd. All rights reserved.

关键词： Integrated supply chain design conic integer programming Polymatroid cuts Cutting plane

来源：评论

学校读者我要写书评

暂无评论

Fill-rate service level constrained distribution network design

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2024年第1期31卷 5-28页

作者： Escalona, Pablo Angulo, Alejandro Brotcorne, Luce Fortz, Bernard Tapia, Paulina Univ Tecn Federico Santa Maria Dept Ind Engn Ave Espana 1680 Valparaiso Chile Univ Tecn Federico Santa Maria Dept Elect Engn Ave Espana 1680 Valparaiso Chile INRIA Lille Nord Europe INOCS Team 40 Ave Halley F-59650 Villeneuve DAscq France Univ Liege HEC Management Sch B-4000 Liege Belgium Univ Libre Bruxelles Fac Sci Dept Informat Blvd Triomphe Bruxelles B-1050 Brussels Belgium

The design of distribution networks that simultaneously consider location and inventory decisions seeks to balance costs and product availability. The most commonly observed measure of product availability in practical settings is the fill-rate service level. However, the optimal design of a distribution network that considers the fill rate to control shortages of fast-moving consumer goods (FMCG) is considered intractable and has only been addressed by heuristic methods. This paper addresses the optimal design of a distribution network for FMCG able to provide high fill-rate service level under a continuous review (r,Q)$(r,Q)$ policy. Considering the exact formulation for the provided fill rate, we formulated a joint location-inventory model with fill-rate service level constraints as a convex mixed integer nonlinear problem for which a novel decomposition-based outer approximation algorithm is proposed. Numerical experiments have shown that our solution approach provides good-quality solutions that are on average 0.15% and, at worst, 2.2% from the optimal solution.

关键词： location inventory fill rate network design conic integer programming outer approximation

来源：评论

学校读者我要写书评

暂无评论

The submodular knapsack polytope

引用

DISCRETE OPTIMIZATION 2009年第4期6卷 333-344页

作者： Atamtuerk, Alper Narayanan, Vishnu Univ Calif Berkeley Dept Ind Engn & Operat Res Berkeley CA 94720 USA Indian Inst Technol Mumbai 400076 Maharashtra India

The submodular knapsack set is the discrete lower level set of a submodular function. The modular case reduces to the classical linear 0-1 knapsack set. One motivation for studying the submodular knapsack polytope is to address 0-1 programming problems with uncertain coefficients. Under various assumptions, a probabilistic constraint on 0-1 variables can be modeled as a submodular knapsack set. In this paper we describe cover inequalities for the submodular knapsack set and investigate their lifting problem. Each lifting problem is itself an optimization problem over a submodular knapsack set. We give sequence-independent upper and lower bounds on the valid lifting coefficients and show that whereas the upper bound can be computed in polynomial time, the lower bound problem is NP-hard. Furthermore, we present polynomial algorithms based on parametric linear programming and computational results for the conic quadratic 0-1 knapsack case. (C) 2009 Elsevier B.V. All rights reserved.

关键词： conic integer programming Submodular functions Probabilistic knapsacks Branch-and-cut algorithms

来源：评论

学校读者我要写书评

暂无评论

Aircraft Rescheduling with Cruise Speed Control

引用

OPERATIONS RESEARCH 2014年第4期62卷 829-845页

作者： Akturk, M. Selim Atamturk, Alper Gurel, Sinan Bilkent Univ Dept Ind Engn TR-06800 Ankara Turkey Univ Calif Berkeley Berkeley CA 94720 USA Middle E Tech Univ Dept Ind Engn TR-06800 Ankara Turkey

Airline operations are subject to frequent disruptions typically due to unexpected aircraft maintenance requirements and undesirable weather conditions. Recovery from a disruption often involves propagating delays in downstream flights and increasing cruise stage speed when possible in an effort to contain the delays. However, there is a critical trade-off between fuel consumption (and its adverse impact on air quality and greenhouse gas emissions) and cruise speed. Here we consider delays caused by such disruptions and propose a flight rescheduling model that includes adjusting cruise stage speed on a set of affected and unaffected flights as well as swapping aircraft optimally. To the best of our knowledge, this is the first study in which the cruise speed is explicitly included as a decision variable into an airline recovery optimization model along with the environmental constraints and costs. The proposed model allows one to investigate the trade-off between flight delays and the cost of recovery. We show that the optimization approach leads to significant cost savings compared to the popular recovery method delay propagation. Flight time controllability, nonlinear delay, fuel burn and CO2 emission cost functions, and binary aircraft swapping decisions complicate the aircraft recovery problem significantly. In order to mitigate the computational difficulty we utilize the recent advances in conic mixed integer programming and propose a strengthened formulation so that the nonlinear mixed integer recovery optimization model can be solved efficiently. Our computational tests on realistic cases indicate that the proposed model may be used by operations controllers to manage disruptions in real time in an optimal manner instead of relying on ad-hoc heuristic approaches.

关键词： airline disruption management fuel burn cruise speed control conic integer programming

来源：评论

学校读者我要写书评

暂无评论

Multi-stage airline scheduling problem with stochastic passenger demand and non-cruise times

引用

TRANSPORTATION RESEARCH PART B-METHODOLOGICAL 2018年 114卷 39-67页

作者： Safak, Ozge Cavus, Ozlem Akturk, M. Selim Bilkent Univ Dept Ind Engn Ankara Turkey

We propose a three-stage stochastic programming model which determines flight timing, fleeting and routing decisions while considering the randomness of demand and non cruise times. Our model differs from the existing two-stage stochastic models by considering not only flight timing and potential passenger demand, but also expected operational expenses, such as fuel burn and carbon emission costs. We include aircraft cruise speed decisions to compensate for non-cruise time variability so as to satisfy the time requirements of the passenger connections. We handle nonlinear functions of fuel and emission costs associated with cruise speed adjustments by utilizing mixed integer second order cone programming. Because the three-stage stochastic model leads to a large decision tree and can be very time-consuming to solve optimally, we suggest a scenario group-wise decomposition algorithm to obtain lower and upper bounds for the optimal value of the proposed model. The lower and upper bounds are obtained by solving a number of group subproblems, which are similar to proposed multi-stage stochastic model defined over a reduced number of scenarios. We suggest a cutting plane algorithm, along with improvements, to efficiently solve each group subproblem. In the numerical experiments, we provide a significant cost savings over two-stage stochastic programming and deterministic approaches. (C) 2018 Elsevier Ltd. All rights reserved.

关键词： Airline scheduling Fleet assignment Aircraft routing Cruise speed control conic integer programming Multi-stage stochastic programming

来源：评论

学校读者我要写书评

暂无评论

Polymatroids and mean-risk minimization in discrete optimization

引用

OPERATIONS RESEARCH LETTERS 2008年第5期36卷 618-622页

作者： Atamtuerk, Alper Narayanan, Vishnu Univ Calif Berkeley Dept Ind Engn & Operat Res Berkeley CA 94720 USA

We study discrete optimization problems with a submodular mean-risk minimization objective. For-0-1 problems a linear characterization of the convex lower envelope is given. For mixed 0-1 problems we derive an exponential class of conic quadratic valid inequalities. We report computational experiments on risk-averse capital budgeting problems with uncertain returns. (c) 2008 Elsevier B.V. All rights reserved.

关键词： conic integer programming Value-at-risk Ellipsoidal uncertainty sets Submodular functions

来源：评论

学校读者我要写书评

暂无评论

MULTI-LOCATION ASSORTMENT OPTIMIZATION UNDER CAPACITY CONSTRAINTS

MULTI-LOCATION ASSORTMENT OPTIMIZATION UNDER CAPACITY CONSTR...

引用

作者： Basak Bebitoglu Bilkent University

学位级别：硕士

We study the assortment optimization problem in an online setting where a re- tailer determines the set of products to carry in each of its distribution centers under a capacity constraint so as to maximize its expected profit (revenue mi- nus the shipping costs). It is assumed that each distribution center is primarily responsible for a geographical location whose customers' choice is governed by a separate multinomial logit model. A distribution center can satisfy a demand of a region that it is not primarily responsible for, but this incurs an additional shipping cost for the retail company. We consider two variants of this problem. In the first variant, customers have access to the entire assortment in all locations but in the second variant, the online retail company can select which product to show to each region. Under each variant, we first assume that there is a constant shipping cost for all products between any two location. In the second case, we allow the shipping costs to differ based on the origin and destination. We develop conic quadratic mixed integer programming formulations and suggest a family of valid inequalities to strengthen these formulations. Numerical experiments show that our conic approach, combined with valid inequalities over-perform the mixed integer linear programming formulation and enables us to solve large instances optimally. Finally, we study the effect of various factors such as no-purchase preference, capacity constraint and shipping cost on company's profitability and assortment selection.

关键词： online retailing multi-locational assortment optimization MMNL consumer choice model conic integer programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：