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

A Simple but Usually Fast Branch-and-Bound algorithm for the Capacitated Facility Location Problem

INFORMS JOURNAL ON COMPUTING 2012年第4期24卷 597-610页

作者： Goertz, Simon Klose, Andreas Berg Univ Wuppertal Schumpeter Sch Business & Econ D-42119 Wuppertal Germany Aarhus Univ Dept Math Sci DK-8000 Aarhus Denmark

This paper presents a simple branch-and-bound method based on Lagrangean relaxation and subgradient optimization for solving large instances of the capacitated facility location problem (CFLP) to optimality. To guess a primal solution to the Lagrangean dual, we average solutions to the Lagrangean subproblem. Branching decisions are then based on this estimated (fractional) primal solution. Extensive numerical results reveal that the method is much faster and more robust than other state-of-the-art methods for solving the CFLP exactly.

关键词： mixed-integer programming Lagrangean relaxation capacitated facility location subgradient optimization volume algorithm branch and bound

来源：评论

学校读者我要写书评

暂无评论

Lagrangian Decomposition for large-scale two-stage stochastic mixed 0-1 problems

引用

TOP 2012年第2期20卷 347-374页

作者： Escudero, L. F. Garin, M. A. Perez, G. Unzueta, A. Univ Basque Country Dpto Econ Aplicada 3 E-48080 Bilbao Vizcaya Spain Univ Rey Juan Carlos Dpto Estadist & Invest Operat Madrid Spain Univ Basque Country Dpto Matemat Aplicada Estadist & Invest Operat Leioa Vizcaya Spain

In this paper we study solution methods for solving the dual problem corresponding to the Lagrangian Decomposition of two-stage stochastic mixed 0-1 models. We represent the two-stage stochastic mixed 0-1 problem by a splitting variable representation of the deterministic equivalent model, where 0-1 and continuous variables appear at any stage. Lagrangian Decomposition (LD) is proposed for satisfying both the integrality constraints for the 0-1 variables and the non-anticipativity constraints. We compare the performance of four iterative algorithms based on dual Lagrangian Decomposition schemes: the Subgradient Method, the volume algorithm, the Progressive Hedging algorithm, and the Dynamic Constrained Cutting Plane scheme. We test the tightness of the LD bounds in a testbed of medium- and large-scale stochastic instances.

关键词： Two-stage stochastic integer programming Lagrangian Decomposition Subgradient Method volume algorithm Progressive Hedging algorithm and Dynamic Constrained Cutting Plane scheme

来源：评论

学校读者我要写书评

暂无评论

Stochastic set packing problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2011年第2期211卷 232-240页

作者： Escudero, Laureano F. Landete, Mercedes Rodriguez-Chia, Antonio M. Univ Rey Juan Carlos Dpto Estadist & Invest Operat Barcelona Spain Univ Miguel Hernandez Elche Ctr Invest Operat Elche Spain Univ Cadiz Dpto Estadist & Investigac Operat Cadiz Spain

In this paper a stochastic version of the set packing problem (SPP), is studied via scenario analysis. We consider a one-stage recourse approach to deal with the uncertainty in the coefficients. It consists of maximizing in the stochastic SPP a composite function of the expected value minus the weighted risk of obtaining a scenario whose objective function value is worse than a given threshold. The splitting variable representation is decomposed by dualizing the nonanticipativity constraints that link the deterministic SPP with a 0-1 knapsack problem for each scenario under consideration. As a result a (structured) larger pure 0-1 model is created. We present several procedures for obtaining good feasible solutions, as well as a preprocessing approach for fixing variables. The Lagrange multipliers updating is performed by using the volume algorithm. Computational experience is reported for a broad variety of instances, which shows that the new approach usually outperforms a state-of-the-art optimization engine, producing a comparable optimality gap with smaller (several orders of magnitude) computing time. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Assignment Set packing Stochastic 0-1 programming Simple recourse Lagrangian decomposition volume algorithm

来源：评论

学校读者我要写书评

暂无评论

Comparison of bundle and classical column generation

引用

MATHEMATICAL PROGRAMMING 2008年第2期113卷 299-344页

作者： Briant, O. Lemarechal, C. Meurdesoif, Ph. Michel, S. Perrot, N. Vanderbeck, F. INRIA F-38334 Montbonnot St Martin St Ismier France Univ Bordeaux 1 MAB F-33405 Talence France Gilco F-38000 Grenoble France

When a column generation approach is applied to decomposable mixed integer programming problems, it is standard to formulate and solve the master problem as a linear program. Seen in the dual space, this results in the algorithm known in the nonlinear programming community as the cutting-plane algorithm of Kelley and Cheney-Goldstein. However, more stable methods with better theoretical convergence rates are known and have been used as alternatives to this standard. One of them is the bundle method;our aim is to illustrate its differences with Kelley's method. In the process we review alternative stabilization techniques used in column generation, comparing them from both primal and dual points of view. Numerical comparisons are presented for five applications: cutting stock (which includes bin packing), vertex coloring, capacitated vehicle routing, multi-item lot sizing, and traveling salesman. We also give a sketchy comparison with the volume algorithm.

关键词： Lagrangian duality Dantzig-Wolfe decomposition stabilized column generation cutting-plane algorithms bundle algorithm volume algorithm nonsmooth convex optimization

来源：评论

学校读者我要写书评

暂无评论

Sample based visibility for soft shadows using alias-free shadow maps

引用

COMPUTER GRAPHICS FORUM 2008年第4期27卷 1285-1292页

作者： Sintorn, Erik Eisemann, Elmar Assarsson, Ulf Chalmers Univ Technol S-41296 Gothenburg Sweden Grenoble Univ ARTIS INRIA Grenoble France

This paper introduces an accurate real-time soft shadow algorithm that uses sample based visibility Initially, we present a GPU-based alias-free hard shadow map algorithm that typically requires only a single render pass from the light, in contrast to using depth peeling and one pass per layer. For closed objects, we also suppress the need for a bias. The method is extended to soft shadow sampling for an arbitrarily shaped area-/volumetric light source using 128-1024 light samples per screen pixel. The alias-free shadow map guarantees that the visibility is accurately sampled per screen-space pixel, even for arbitrarily shaped (e.g. non-planar) surfaces or solid objects. Another contribution is a smooth coherent shading model to avoid common light leakage near shadow borders due to normal interpolation.

关键词： volume algorithm HARDWARE

来源：评论

学校读者我要写书评

暂无评论

On embedding the volume algorithm in a variable target value method

引用

OPERATIONS RESEARCH LETTERS 2004年第5期32卷 455-462页

作者： Sherali, HD Lim, C Virginia Polytech Inst & State Univ Grado Dept Ind & Syst Engn Blacksburg VA 24061 USA

We employ the volume algorithm as a subgradient deflection strategy in a variable target value method for solving nondifferentiable optimization problems. Focusing on Lagrangian duals for LPs, we exhibit primal nonconvergence of the original method, establish convergence of the proposed algorithm in the dual space, and present related computational results. (C) 2004 Elsevier B.V. All rights reserved.

关键词： nondifferentiable optimization Lagrangian relaxation variable target value method volume algorithm

来源：评论

学校读者我要写书评

暂无评论

Faster mixing and small bottlenecks

引用

PROBABILITY THEORY AND RELATED FIELDS 2007年第3-4期137卷 475-486页

作者： Fountoulakis, N. Reed, B. A. McGill Univ Sch Comp Sci Montreal PQ H3A 2A7 Canada

We prove a new bound on the mixing time of a Markov chain by considering the conductance of its connected subsets.

关键词： volume algorithm MARKOV-CHAINS RANDOM-WALKS CLUSTER GRAPHS MODEL TIME

来源：评论

学校读者我要写书评

暂无评论

The geometry of logconcave functions and sampling algorithms

引用

RANDOM STRUCTURES & algorithmS 2007年第3期30卷 307-358页

作者： Lovasz, Laszlo Vempala, Santosh Microsoft Res Redmond WA USA MIT Dept Math Cambridge MA 02139 USA

The class of logconcave functions in R-n is a common generalization of Gaussians and of indicator functions of convex sets, Motivated by the problem of sampling from logconcave density functions, we study their geometry and introduce a technique for "smoothing" them out. These results are applied to analyze two efficient algorithms for sampling from a logconcave distribution in n dimensions, with no assumptions on the local smoothness of the density function. Both algorithms, the ball walk and the hit-and-run walk, use a random walk (Markov chain) to generate a random point. After appropriate preprocessing, they produce a point from approximately the right distribution in time O* (n(4)) and in amortized time O* (n(3)) if n or more sample points are needed (where the asterisk indicates that dependence on the error parameter and factors of log n are not shown). These bounds match previous bounds for the special case of sampling from the uniform distribution over a convex body. (c) 2006 Wiley Periodicals, Inc.

关键词： HIT-AND-RUN RANDOM-WALKS volume algorithm CONVEX-BODIES

来源：评论

学校读者我要写书评

暂无评论

A hybrid Lagrangian genetic algorithm for the prize collecting Steiner tree problem

引用

COMPUTERS & OPERATIONS RESEARCH 2006年第5期33卷 1274-1288页

作者： Haouari, M Siala, JC Ecole Polytech CORG Lab Math Engn La Marsa 2078 Tunisia

We consider the version of prize collecting Steiner tree problem (PCSTP) where each node of a given weighted graph is associated with a prize and where the objective is to find a minimum weight tree spanning a subset of nodes and collecting a total prize not less that a given quota Q. We present a lower bound and a genetic algorithm for the PCSTR The lower bound is based on a Lagrangian decomposition of a minimum spanning tree formulation of the problem. The volume algorithm is used to solve the Lagrangian dual. The genetic algorithm incorporates several enhancements. In particular, it fully exploits both primal and dual information produced by Lagrangian decomposition. The proposed lower and upper bounds are assessed through computational experiments on randomly generated instances with up to 500 nodes and 5000 edges. For these instances, the proposed lower and upper bounds exhibit consistently a tight gap: in 76% of the cases the gap is strictly less than 2%. (c) 2004 Elsevier Ltd. All rights reserved.

关键词： prize collecting Steiner tree Lagrangian decomposition volume algorithm genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

Blocking conductance and mixing in random walks

引用

COMBINATORICS PROBABILITY & COMPUTING 2006年第4期15卷 541-570页

作者： Kannan, R. Lovasz, L. Montenegro, R. Yale Univ Dept Comp Sci New Haven CT 06520 USA Microsoft Res Redmond WA 98052 USA Georgia Inst Technol Sch Math Atlanta GA 30332 USA

The notion of conductance introduced by Jerrum and Sinclair [8] has been widely used to prove rapid mixing of Markov chains. Here we introduce a bound that extends this in two directions. First, instead of measuring the conductance of the worst subset of states, we bound the mixing time by a formula that can be thought of as a weighted average of the Jerrum-Sinclair bound (where the average is taken over subsets of states with different sizes). Furthermore, instead of just the conductance, which in graph theory terms measures edge expansion, we also take into account node expansion. Our bound is related to the logarithmic Sobolev inequalities, but it appears to be more flexible and easier to compute. In the case of random walks in convex bodies, we show that this new bound is better than the known bounds for the worst case. This saves a factor of O(n) in the mixing time bound, which is incurred in all proofs as a 'penalty' for a 'bad start'. We show that in a convex body in R-n, with diameter D, random walk with steps in a ball with radius 6 mixes in O*(nD(2)/delta(2)) time (if idle steps at the boundary are not counted). This gives an O*(n(3)) sampling algorithm after appropriate preprocessing, improving the previous bound of O*(n(4)). The application of the general conductance bound in the geometric setting depends on an improved isoperimetric inequality for convex bodies.

关键词： SOBOLEV INEQUALITIES volume algorithm CONVEX-BODIES MARKOV-CHAINS TIMES

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：