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

A polynomial time algorithm for the stochastic uncapacitated lot-sizing problem with backlogging

13th international conference on integer programming and combinatorial optimization

作者： Guan, Yongpei Miller, Andrew Univ Oklahoma Sch Ind Engn Norman OK 73019 USA Univ Wisconsin Dept Ind & Syst Engn Madison WI 53706 USA

ISBN: (纸本)9783540688860

Since Wagner and Whitin published a seminal paper on the deterministic uncapacitated lot-sizing problem, many other researchers have investigated the structure of other fundamental models on lot-sizing that are embedded in practical production planning problems. In this paper we consider basic versions of such models in which demand (and other problem parameters) are stochastic rather than deterministic. It is named stochastic uncapacitated lot-sizing problem with backlogging. We define a production path property of optimal solutions for this model and use this property to develop backward dynamic programming recursions. this approach allows us to show that the value function is piecewise linear and continuous, which we can further use to define a polynomial time algorithm for the problem in a general stochastic scenario tree setting.

关键词： Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Can pure cutting plane algorithms work?

引用

13th international conference on integer programming and combinatorial optimization

作者： Zanette, Arrigo Fischetti, Matteo Balas, Egon Univ Padua DEI I-35100 Padua Italy Carnegie Mellon Univ Pittsburgh PA 15213 USA

ISBN: (纸本)9783540688860

We discuss an implementation of the lexicographic version of Gomory's fractional cutting plane method and of two heuristics mimicking the latter. In computational testing on a battery of MIPLIB problems we compare the performance of these variants with that of the standard Gomory algorithm, both in the single-cut and in the multi-cut (rounds of cuts) version, and show that they provide a radical improvement over the standard procedure. In particular, we report the exact solution of ILP instances from MIPLIB such as stein15, stein27, and bm23, for which the standard Gomory cutting plane algorithm is not able to close more than a tiny fraction of the integrality gap. We also offer an explanation for this surprizing phenomenon.

关键词： cutting plane methods Gomory cuts degeneracy in linear programming lexicographic dual simplex computational analysis

来源：评论

学校读者我要写书评

暂无评论

Disjunctive cuts for non-convex mixed integer quadratically constrained programs

引用

13th international conference on integer programming and combinatorial optimization

作者： Saxena, Anureet Bonami, Pierre Lee, Jon Carnegie Mellon Univ Tepper Sch Business Pittsburgh PA 15213 USA Univ Marseille CNRS Lab Informat Fondamentale Marseille Marseille France IBM TJ Watson Res Ctr Yorktown Hts NY 10598 USA

ISBN: (纸本)9783540688860

this paper addresses the problem of generating strong convex relaxations of Mixed integer Quadratically Constrained programming (MIQCP) problems. MIQCP problems are very difficult because they combine two kinds of non-convexities: integer variables and non-convex quadratic constraints. To produce strong relaxations of MIQCP problems, we use techniques from disjunctive programming and the lift-and-project methodology. In particular, we propose new methods for generating valid inequalities by using the equation Y = xx(T). We use the concave constraint 0 >= Y - xx(T) to derive disjunctions of two types. the first ones are directly derived from the eigenvectors of the matrix Y-xx(T) with positive eigenvalues, the second type of disjunctions are obtained by combining several eigenvectors in order to minimize the width of the disjunction. We also use the convex SDP constraint Y - xx(T) >= 0 to derive convex quadratic cuts and combine both approaches in a cutting plane algorithm. We present preliminary computational results to illustrate our findings.

关键词： Eigenvalues and eigenfunctions

来源：评论

学校读者我要写书评

暂无评论

ON SEMIDEFINITE programming RELAXATIONS OF thE TRAVELING SALESMAN PROBLEM

引用

SIAM JOURNAL ON optimization 2008年第4期19卷 1559-1573页

作者： De Klerk, Etienne Pasechnik, Dmitrii V. Sotirov, Renata Tilburg Univ Dept Econometr & OR NL-5000 LE Tilberg Netherlands Nanyang Technol Univ Sch Phys & Math Sci Singapore Singapore

We consider a new semidefinite programming (SDP) relaxation of the symmetric traveling salesman problem (TSP) that may be obtained via an SDP relaxation of the more general quadratic assignment problem (QAP). We show that the new relaxation dominates the one in [D. Cvetkovic, M. Cangalovic, and V. Kovacevic-Vujcic, Semidefinite programming methods for the symmetric traveling salesman problem, in Proceedings of the 7th international IPCO conference on integer programming and combinatorial optimization, Springer-Verlag, London, UK, 1999, pp. 126-136]. Unlike the bound of Cvetkovic et al., the new SDP bound is not dominated by the Held-Karp linear programming bound, or vice versa.

关键词： traveling salesman problem semidefinite programming quadratic assignment problem association schemes

来源：评论

学校读者我要写书评

暂无评论

Lifting integer variables in minimal inequalities corresponding to lattice-free triangles

引用

13th international conference on integer programming and combinatorial optimization

作者： Dey, Santanu S. Wolsey, Laurence A. CORE 34 Voie Roman Pays B-1348 Louvain Belgium Catholic Univ Louvain CORE & INMA B-1348 Louvain Belgium

ISBN: (纸本)9783540688860

Recently, Andersen et al. [1] and Borozan and Cornuejols [3] characterized the minimal inequalities of a system of two rows with two free integer variables and nonnegative continuous variables. these inequalities are either split cuts or intersection cuts derived using maximal lattice-free convex sets. In order to use these minimal inequalities to obtain cuts from two rows of a general simplex tableau, it is necessary to extend the system to include integer variables (giving the two-dimensional mixed integer infinite group problem), and to develop lifting functions giving the coefficients of the integer variables in the corresponding inequalities. In this paper, we analyze the lifting of minimal inequalities derived from lattice-free triangles. Maximal lattice-free triangles in R-2 can be classified into three categories: those with multiple integral points in the relative interior of one of its sides, those with integral vertices and one integral point in the relative interior of each side, and those with non integral vertices and one integral point in the relative interior of each side. We prove that the lifting functions are unique for each of the first two categories such that the resultant inequality is minimal for the mixed integer infinite group problem, and characterize them. We show that the lifting function is not necessarily unique in the third category. For this category we show that a fill-in inequality (Johnson [11]) yields minimal inequalities for mixed integer infinite group problem under certain sufficiency conditions. Finally, we present conditions for the fill-in inequality to be extreme.

关键词： Set theory

来源：评论

学校读者我要写书评

暂无评论

Perspective relaxation of mixed integer nonlinear programs with indicator variables

引用

13th international conference on integer programming and combinatorial optimization

作者： Gunluk, Oktay Linderoth, Jeff IBM Corp Thomas J Watson Res Ctr Dept Math Sci Yorktown Hts NY 10598 USA Univ Wisconsin Madison Dept Ind & Syst Engn Madison WI 53706 USA

ISBN: (纸本)9783540688860

We study mixed integer nonlinear programs (MINLP) that are driven by a collection of indicator variables where each indicator variable controls a subset of the decision variables. An indicator variable, when it is "turned off", forces some of the decision variables to assume a fixed value, and, when it is "turned on", forces them to belong to a convex set. Most of the integer variables in known MINLP problems are of this type. We first study a mixed integer set defined by a single separable quadratic constraint and a collection of variable upper and lower bound constraints. this is an interesting set that appears as a substructure in many applications. We present the convex hull description of this set. We then extend this to produce an explicit characterization of the convex hull of the union of a point and a bounded convex set defined by analytic functions. Further, we show that for many classes of problems, the convex hull can be expressed via conic quadratic constraints, and thus relaxations can be solved via second-order cone programming. Our work is closely related with the earlier work of Ceria and Soares (1996) as well as recent work by Frangioni and Gentile (2006) and, Akturk, Atamturk and Gurel (2007). Finally, we apply our results to develop tight formulations of mixed integer nonlinear programs in which the nonlinear functions are separable and convex and in which indicator variables play an important role. In particular, we present strong computational results with two applications - quadratic facility location and network design with congestion - that show the power of the reformulation technique.

关键词： Second-order cone programming

来源：评论

学校读者我要写书评

暂无评论

the stochastic machine replenishment problem

引用

13th international conference on integer programming and combinatorial optimization

作者： Munagala, Kamesh Shi, Peng Duke Univ Dept Comp Sci Durham NC 27708 USA

ISBN: (纸本)9783540688860

We study the stochastic machine replenishment problem, which is a canonical special case of closed multiclass queuing systems in Markov decision theory. the problem models the scheduling of processor repairs in a multiprocessor system in which one repair can be made at a time and the goal is to maximize system utilization. We analyze the performance of a natural greedy index policy for this problem. We first show that this policy is a 2 approximation by exploring linear queuing structure in the index policy. We then try to exploit more complex queuing structures, but this necessitates solving an infinite-size, non-linear, non-convex, and non-separable function-maximization program. We develop a general technique to solve such programs to arbitrary degree of accuracy, which involves solving a discretized program on the computer and rigorously bounding the error. this proves that the index policy is in fact a 1.51 approximation. the main non-trivial ingredients of the proof are two folds: finding a way to analyze the complex queuing structure of the index policy, and bounding the error in discretization when numerically solving the non-linear function-maximization. We believe that this framework is general enough to be useful in the analysis of index policies in related problems. As far as we are aware, this is one of the first non-trivial approximation analysis of an index policy a multi-class queuing problem, as well as one of the first non-trivial example of an approximation ratio that is rigorously proven by numerical optimization via a computer.

关键词： optimization

来源：评论

学校读者我要写书评

暂无评论

Linearizing Quadratic Assignment Problem 20

Linearizing Quadratic Assignment Problem

引用

20th international conference/Euro Mini conference on Continuous optimization and Knowledge-Based Technologies (EurOPT 2008)

作者： Singh, Surya Prakash Xavier Inst Management Bhubaneswar 751013 Khurda India

ISBN: (纸本)9789955282839

In past several linearization of the Quadratic Assignment Problem (QAP) which is a NP-hard problem have been given (See Lawler (1962) and Christofides et al. (1980)). Here, a new set of constraints that perfectly linearize the QAP is proposed. the new linearization is compared with other linearization and it is found that proposed linearization performs better in time complexity. We have also shown that linear programming relaxations of these linearizations give optimal solution for the 0-1 integer linearization of QAP. Empirical evidence shows that this results in substantial savings in computational time. T-test has been also carried out to show the significance statistically.

关键词： combinatorial optimization linearization QAP T-test MILP continuous optimization

来源：评论

学校读者我要写书评

暂无评论

the induced disjoint paths problem

引用

13th international conference on integer programming and combinatorial optimization

作者： Kawarabayashi, Ken-ichi Kobayashi, Yusuke Natl Inst Informat Tokyo 1018430 Japan Univ Tokyo Tokyo 1138656 Japan

ISBN: (纸本)9783540688860

For a graph G and a collection of vertex pairs {(s(1), t(1)),..., (s(k), t(k))}, the disjoint paths problem is to find k vertex-disjoint paths P-1,..., P-k, where P-i is a path from s(i) to t(i) for each i = 1,..., k. this problem is one of the classic problems in combinatorial optimization and algorithmic graph theory, and has many applications, for example in transportation networks, VLSI layout, and recently, virtual circuits routing in high-speed networks. As an extension of the disjoint paths problem, we introduce a new problem which we call the induced disjoint paths problem. In this problem we are given a graph G and a collection of vertex pairs {(s(1,) t(1)),..., (s(k), t(k))}. the objective is to find k paths P-i,..., P-k such that Pi is a path from si to ti and P-i and P-j have neither common vertices nor adjacent vertices for any distinct i,j. this problem setting is a generalization of the disjoint paths problem, since if we subdivide each edge, then desired disjoint paths would be induced disjoint paths. the problem is motivated by not only the disjoint paths problem but also the recognition of an induced subgraph. the latter has been developed in the recent years, and this is actually connected to the Strong Perfect Graph theorem [4], and the recognition of the perfect graphs [2]. In this paper, we shall investigate the complexity issues of this problem. the induced disjoint paths problem has several variants depending on whether k is a fixed constant or a part of the input, whether the graph is directed or undirected, and whether the graph is planar or not. We show that the induced disjoint paths problem is (i) solvable in polynomial time when k is fixed and G is a directed planar graph, (ii) solvable in linear time when k is fixed and G is an undirected planar graph, (iii) NP-hard when k = 2 and G is an acyclic directed graph, (iv) NP-hard when k = 2 and G is an undirected general graph. (i) generalizes the result by Schrijver [22], while (ii) genera

关键词： combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

the performance of the modified subgradient algorithm on solving the 0-1 quadratic knapsack problem 20

The performance of the modified subgradient algorithm on sol...

引用

20th international conference/Euro Mini conference on Continuous optimization and Knowledge-Based Technologies (EurOPT 2008)

作者： Sipahioglu, Aydin Sarac, Tugba Osmangazi Univ Dept Ind Engn TR-26030 Bademlik Eskisehir Turkey

ISBN: (纸本)9789955282839

In this study, the performance of the modified subgradient algorithm (MSG) to solve the 0-1 quadratic knapsack problem (QKP) is examined. the MSG is proposed by Gasimov for solving dual problems constructed with respect to sharp Augmented Lagrangian function. the MSG has some important proven properties. For example, it is convergent, and it guarantees the zero duality gap for the problems such that its objective and constraint functions are all Lipschtz. Besides it doesn't need to be convexity or differentiability conditions on the primal problem. the MSG has successfully used for solving nonconvex continuous and some combinatorial problems with equality constraints since it was suggested. In this study, the MSG is used to solve the QKP which is one of the well known combinatorial optimization problems with inequality constraint. Firstly, zero-one nonlinear problem is converted into continuous nonlinear problem by adding only one constraint and not adding new variables, then to solve the continuous QKP, dual problem with "zero duality gap" is constructed by using the sharp Augmented Lagrangian function. Finally, to solve the dual problem, the MSG is used by considering the equality constraint in the computation of the norm. the proposed approach is applied for some test problems. the results are also presented and discussed.

关键词： quadratic knapsack problem sharp Augmented Lagrangian function MSG integer programming nonlinear programming quadratic programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：