-
作者：Müller, D
作者单位：University of Bonn
摘要：The edge-disjoint paths problem and many special cases of it are known to be NP-complete. We present a new NP-completeness result for a special case of the problem, namely the directed edge-disjoint paths problem restricted to planar supply graphs and demand graphs consisting of two sets of parallel edges.
-
作者：Fischer, I; Gruber, G; Rendl, F; Sotirov, R
作者单位：University of Vienna; University of Klagenfurt; University of Melbourne
摘要：We propose a dynamic version of the bundle method to get approximate solutions to semidefinite programs with a nearly arbitrary number of linear inequalities. Our approach is based on Lagrangian duality, where the inequalities are dualized, and only a basic set of constraints is maintained explicitly. This leads to function evaluations requiring to solve a relatively simple semidefinite program. Our approach provides accurate solutions to semidefinite relaxations of the Max-Cut and the Equipar...
-
作者：Letchford, AN; Salazar-González, JJ
作者单位：Lancaster University; Universidad de la Laguna
摘要：A variety of integer programming formulations have been proposed for Vehicle Routing Problems (VRPs), including the so-called two- and three-index formulations, the set partitioning formulation, and various formulations based on extra variables representing the flow of one or more commodities. Until now, there has not been a systematic study of how these formulations relate to each other. An exception is a paper of Luis Gouveia, which shows that a one-commodity flow formulation of Gavish and G...
-
作者：Sherali, Hanif D.; Zhu, Xiaomei
作者单位：Virginia Polytechnic Institute & State University
摘要：In this paper, we propose a decomposition-based branch-and-bound (DBAB) algorithm for solving two-stage stochastic programs having mixed-integer first- and second-stage variables. A modified Benders' decomposition method is developed, where the Benders' subproblems define lower bounding second-stage value functions of the first-stage variables that are derived by constructing a certain partial convex hull representation of the two-stage solution space. This partial convex hull is sequentially ...
-
作者：De Franceschi, R; Fischetti, M; Toth, P
作者单位：University of Padua; University of Bologna
摘要：In this paper we address the Distance-Constrained Capacitated Vehicle Routing Problem (DCVRP), where k minimum-cost routes through a central depot have to be constructed so as to cover all customers while satisfying, for each route, both a capacity and a total-distance-travelled limit. Our starting point is the following refinement procedure proposed in 1981 by Sarvanov and Doroshko for the pure Travelling Salesman Problem (TSP): given a starting tour, (a) remove all the nodes in even position...
-
作者：Bayraksan, Guezin; Morton, David P.
作者单位：University of Arizona; University of Texas System; University of Texas Austin
摘要：Determining whether a solution is of high quality (optimal or near optimal) is fundamental in optimization theory and algorithms. In this paper, we develop Monte Carlo sampling-based procedures for assessing solution quality in stochastic programs. Quality is defined via the optimality gap and our procedures' output is a confidence interval on this gap. We review a multiple-replications procedure that requires solution of, say, 30 optimization problems and then, we present a result that justif...
-
作者：Klein Haneveld, Willem K.; Stougie, Leen; van der Vlerk, Maarten H.
作者单位：University of Groningen; Eindhoven University of Technology; Centrum Wiskunde & Informatica (CWI)
摘要：We consider the objective function of a simple recourse problem with fixed technology matrix and integer second-stage variables. Separability due to the simple recourse structure allows to study a one-dimensional version instead. Based on an explicit formula for the objective function, we derive a complete description of the class of probability density functions such that the objective function is convex. This result is also stated in terms of random variables. Next, we present a class of con...
-
作者：Michaels, D; Weismantel, R
作者单位：Otto von Guericke University
摘要：This paper deals with the reformulation of a polynomial integer program. For deducing a linear integer relaxation of such a program a class of polyhedra that are associated with nonlinear functions is introduced. A characterization of the family of polynomials for which our approach leads to an equivalent linear integer program is given. Finally the family of so-called integer-convex polynomials is defined, and polyhedra related to such a polynomial are investigated.
-
作者：Silva, Eduardo F.; Wood, R. Kevin
作者单位：United States Department of Defense; United States Navy; Naval Postgraduate School
摘要：We begin this paper by identifying a class of stochastic mixed-integer programs that have column-oriented formulations suitable for solution by a branch-and-price algorithm (B&P). We then survey a number of examples, and use a stochastic facility-location problem (SFLP) for a detailed demonstration of the relevant modeling and solution techniques. Computational results with a scenario representation of uncertain costs, demands and capacities show that B&P can be orders of magnitude faster than...
-
作者：Roman, Diana; Darby-Dowman, Ken; Mitra, Gautam
作者单位：Brunel University
摘要：Mean-risk models have been widely used in portfolio optimization. However, such models may produce portfolios that are dominated with respect to second order stochastic dominance and therefore not optimal for rational and risk-averse investors. This paper considers the problem of constructing a portfolio which is non-dominated with respect to second order stochastic dominance and whose return distribution has specified desirable properties. The problem is multi-objective and is transformed int...
