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

作者： Kamyar Khodamoradi Simon Fraser University

学位级别：博士

Optimization has been a central topic in most scientific disciplines for centuries. Continu- ous optimization has long benefited from well-established techniques of calculus. Discrete optimization, on the other hand, has risen to prominence quite recently. Advances in combinatorial optimization and integer programming in the past few decades, together with the improvement of computer hardware have enabled computer scientists to approach the problems in this area both theoretically and computationally. However, obtaining the exact solution for many discrete optimization problems remains is still a challenging task, mainly because most of these problems are NP -hard. Under the widespread assumption that P 6= NP, these problems are intractable from a computational complexity standpoint. Therefore, we should settle for near-optimal solutions. In this thesis, we develop techniques to obtain solutions that are provably close to the optimal for different indivisible resource allocation problems. Indivisible resource allocation encompasses a large class of problems in discrete optimization which can appear in disguise in various theoretical or applied settings. Specifically, we consider two indivisible resource allocation problems. The first one is a variant of the vehicle routing problem known as Skill Vehicle Routing problem, in which the aim is to obtain optimal tours for a fleet of vehicles that provides service to a set of customers. Each of the vehicles possesses a particular set of skills suitable for a subset of the tasks. Each customer, based on the type of service he requires, can only be served by a subset of vehicles. We study this problem computationally and find either the optimal solution or a relatively tight bound on the optimal solution on fairly large problem instances. The second problem involves approximation algorithms for two versions of the classic scheduling problem, the restricted R | | C max and the restricted Santa Claus problem. The objective is

关键词： Vehicle routing problem Integer linear programming branch-and-cut algorithms Prize-collecting traveling salesman problem Scheduling problems Convex and bipartite permutation graphs

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

On the hop-constrained survivable network design problem with reliable edges

引用

COMPUTERS & OPERATIONS RESEARCH 2015年第Dec.期64卷 159-167页

作者： Botton, Quentin Fortz, Bernard Gouveia, Luis Catholic Univ Louvain Louvain Sch Management Louvain Belgium Univ Libre Bruxelles Fac Sci Dept Informat Brussels Belgium Univ Lisbon Fac Ciencias DEIO CIO Lisbon Portugal

In this paper, we study the hop-constrained survivable network design problem with reliable edges. Given a graph with non-negative edge costs and node pairs Q the hop-constrained survivable network design problem consists of constructing a minimum cost set of edges so that the induced subgraph contains at least K edge-disjoint paths containing at most L edges between each pair in Q. In addition, we consider here a subset of reliable edges that are not subject to failure. We study two variants: a static problem where the reliability of edges is given, and an upgrading problem where edges can be upgraded to the reliable status at a given cost We adapt for the two variants an extended formulation proposed in Botton, Fortz, Gouveia, Poss (2011) [1] for the case without reliable edges. As before, we use Benders decomposition to accelerate the solving process. Our computational results indicate that these two variants appear to be more difficult to solve than the original problem (without reliable edges). We conclude with an economical analysis which evaluates the incentive of using reliable edges in the network. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： Network design Survivability Hop constraints Benders decomposition branch-and-cut algorithms

来源：评论

学校读者我要写书评

暂无评论

Formulations for the Minimum 2-Connected Dominating Set Problem

引用

Electronic Notes in Discrete Mathematics 2013年 41卷 415-422页

作者： do Forte, Vinicius Leal Lucena, Abilio Maculan, Nelson Programa de Engenharia de Sistemas e Computação - COPPE Universidade Federal do Rio de Janeiro Rio de Janeiro Brazil

Three formulations for the Minimum 2-Connected Dominating Set Problem, valid inequalities, a primal heuristic and branch-and-cut algorithms are introduced in this paper. As shown here, the preliminary computational re... 详细信息

关键词： 2-connected graphs branch-and-cut algorithms Dominating sets

来源：评论

学校读者我要写书评

暂无评论

Models and algorithms for the Asymmetric Traveling Salesman Problem: an experimental comparison

引用

EURO JOURNAL ON TRANSPORTATION AND LOGISTICS 2012年第1-2期1卷 113-133页

作者： Roberti, Roberto Toth, Paolo Univ Bologna DEIS Viale Risorgimento 2 I-40136 Bologna BO Italy

This paper surveys the most effective mathematical models and exact algorithms proposed for finding the optimal solution of the well-known Asymmetric Traveling Salesman Problem (ATSP). The fundamental Integer Linear Programming (ILP) model proposed by Dantzig, Fulkerson and Johnson is first presented, its classical (assignment, shortest spanning r-arborescence, linear programming) relaxations are derived, and the most effective branch-and-bound and branch-andcut algorithms are described. The polynomial ILP formulations proposed for the ATSP are then presented and analyzed. The considered algorithms and formulations are finally experimentally compared on a set of benchmark instances.

关键词： Asymmetric Traveling Salesman Problem Integer Linear Programming models branch-and-bound algorithms branch-and-cut algorithms Experimental comparison

来源：评论

学校读者我要写书评

暂无评论

Conic mixed-integer rounding cuts

引用

MATHEMATICAL PROGRAMMING 2010年第1期122卷 1-20页

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

A conic integer program is an integer programming problem with conic constraints. Many problems in finance, engineering, statistical learning, and probabilistic optimization are modeled using conic constraints. Here we study mixed-integer sets defined by second-order conic constraints. We introduce general-purpose cuts for conic mixed-integer programming based on polyhedral conic substructures of second-order conic sets. These cuts can be readily incorporated in branch-and-bound algorithms that solve either second-order conic programming or linear programming relaxations of conic integer programs at the nodes of the branch-and-bound tree. Central to our approach is a reformulation of the second-order conic constraints with polyhedral second-order conic constraints in a higher dimensional space. In this representation the cuts we develop are linear, even though they are nonlinear in the original space of variables. This feature leads to a computationally efficient implementation of nonlinear cuts for conic mixed-integer programming. The reformulation also allows the use of polyhedral methods for conic integer programming. We report computational results on solving unstructured second-order conic mixed-integer problems as well as mean-variance capital budgeting problems and least-squares estimation problems with binary inputs. Our computational experiments show that conic mixed-integer rounding cuts are very effective in reducing the integrality gap of continuous relaxations of conic mixed-integer programs and, hence, improving their solvability.

关键词： Conic programming Integer programming Mixed-integer rounding branch-and-cut algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A new formulation for the Traveling Deliveryman Problem

引用

DISCRETE APPLIED MATHEMATICS 2008年第17期156卷 3223-3237页

作者： Mendez-Diaz, Isabel Zabala, Paula Lucena, Abilio Univ Buenos Aires FCEyN Depto Computac RA-1053 Buenos Aires DF Argentina Univ Fed Rio de Janeiro Depto Adm BR-21941 Rio De Janeiro Brazil

The Traveling Deliveryman Problem is a generalization of the Minimum Cost Hamiltonian Path Problem where the starting vertex of the path, i.e. a depot vertex, is fixed in advance and the cost associated with a Hamiltonian path equals the sum of the costs for the layers of paths (along the Hamiltonian path) going from the depot vertex to each of the remaining vertices. In this paper, we propose a new Integer Programming formulation for the problem and computationally evaluate the strength of its Linear Programming relaxation. Computational results are also presented for a cutting plane algorithm that uses a number of valid inequalities associated with the proposed formulation. Some of these inequalities are shown to be facet defining for the convex hull of feasible solutions to that formulation. These inequalities proved very effective when used to reinforce Linear Programming relaxation bounds, at the nodes of a branch and Bound enumeration tree. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Traveling deliveryman problem Integer programming branch-and-cut algorithms

来源：评论

学校读者我要写书评

暂无评论

Intermediate integer programming representations using value disjunctions

引用

DISCRETE OPTIMIZATION 2008年第2期5卷 293-313页

作者： Koeppe, Matthias Louveaux, Quentin Weismantel, Robert Otto VonGuericke Univ Magdeburg Dept Math IMO D-39106 Magdeburg Germany

We introduce a general technique for creating an extended formulation of a mixed-integer program. We classify the integer variables into blocks, each of which generates a finite set of vector values. The extended formulation is constructed by creating a new binary variable for each generated value. Initial experiments show that the extended formulation can have a more compact complete description than the original formulation. We prove that, using this reformulation technique, the facet description decomposes into one "linking polyhedron" per block and the "aggregated polyhedron". Each of these polyhedra can be analyzed separately. For the case of identical coefficients in a block, we provide a complete description of the linking polyhedron and a polynomial-time separation algorithm. Applied to the knapsack with a fixed number of distinct coefficients, this theorem provides a complete description in an extended space with a polynomial number of variables. On the basis of this theory, we propose a new branching scheme that analyzes the problem structure. It is designed to be applied in those subproblems of hard integer programs where LP-based techniques do not provide good branching decisions. Preliminary computational experiments show that it is successful for some benchmark problems of multi-knapsack type. (c) 2007 Elsevier B.V. All rights reserved.

关键词： mixed-integer programming extended formulations branch-and-cut algorithms polyhedral combinatorics

来源：评论

学校读者我要写书评

暂无评论

New branch-and-cut algorithm for bilevel linear programming

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2007年第2期134卷 353-370页

作者： Audet, C. Savard, G. Zghal, W. Ecole Hautes Etud Commerciales Gerad Montreal PQ Canada Ecole Polytech Montreal PQ H3C 3A7 Canada

Linear mixed 0-1 integer programming problems may be reformulated as equivalent continuous bilevel linear programming (BLP) problems. We exploit these equivalences to transpose the concept of mixed 0-1 Gomory cuts to BLP. The first phase of our new algorithm generates Gomory-like cuts. The second phase consists of a branch-and-bound procedure to ensure finite termination with a global optimal solution. Different features of the algorithm, in particular, the cut selection and branching criteria are studied in details. We propose also a set of algorithmic tests and procedures to improve the method. Finally, we illustrate the performance through numerical experiments. Our algorithm outperforms pure branch-and-bound when tested on a series of randomly generated problems.

关键词： Bilevel linear programming Gomory cuts linear mixed 0-1 integer programming branch-and-cut algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：