We treat uncertain linear programming problems by utilizing the notion of weighted analytic centers and notions from the area of multi-criteria decision making. After introducing our approach, we develop interactive c...
详细信息
We treat uncertain linear programming problems by utilizing the notion of weighted analytic centers and notions from the area of multi-criteria decision making. After introducing our approach, we develop interactive cutting-plane algorithms for robust optimization, based on concave and quasi-concave utility functions. In addition to practical advantages, due to the flexibility of our approach, we prove that under a theoretical framework proposed by Bertsimas and Sim (Oper Res 52:35-53, 2004), which establishes the existence of certain convex formulation of robust optimization problems, the robust optimal solutions generated by our algorithms are at least as desirable to the decision maker as any solution generated by many other robust optimization algorithms in the theoretical framework. We present some probabilistic bounds for feasibility of robust solutions and evaluate our approach by means of computational experiments.
Stochastic network design is fundamental to transportation and logistic problems in practice, yet faces new modeling and computational challenges resulted from heterogeneous sources of uncertainties and their unknown ...
详细信息
Stochastic network design is fundamental to transportation and logistic problems in practice, yet faces new modeling and computational challenges resulted from heterogeneous sources of uncertainties and their unknown distributions given limited data. In this article, we design arcs in a network to optimize the cost of single-commodity flows under random demand and arc disruptions. We minimize the network design cost plus cost associated with network performance under uncertainty evaluated by two schemes. The first scheme restricts demand and arc capacities in budgeted uncertainty sets and minimizes the worst-case cost of supply generation and network flows for any possible realizations. The second scheme generates a finite set of samples from statistical information (e.g., moments) of data and minimizes the expected cost of supplies and flows, for which we bound the worst-case cost using budgeted uncertainty sets. We develop cutting-plane algorithms for solving the mixed-integer nonlinear programming reformulations of the problem under the two schemes. We compare the computational efficacy of different approaches and analyze the results by testing diverse instances of random and real-world networks. (c) 2017 Wiley Periodicals, Inc.
In this paper, we consider an infrastructure as a network with supply, transshipment, and demand nodes. A subset of potential arcs can be constructed between node pairs for conveying service flows. The paper studies t...
详细信息
In this paper, we consider an infrastructure as a network with supply, transshipment, and demand nodes. A subset of potential arcs can be constructed between node pairs for conveying service flows. The paper studies two optimization models under stochastic arc disruption. Model 1 focuses on a single network with small-scale failures, and repairs arcs for quick service restoration. Model 2 considers multiple interdependent infrastructures under large-scale disruptions, and mitigates cascading failures by selectively disconnecting failed components. We formulate both models as scenario-based stochastic mixed-integer programs, in which the first-stage problem builds arcs, and the second-stage problem optimizes recourse operations for restoring service or mitigating losses. The goal is to minimize the total cost of infrastructure design and recovery operations. We develop cutting-plane algorithms and several heuristic approaches for solving the two models. Model 1 is tested on an IEEE 118-bus system. Model 2 is tested on systems consisting of the 118-bus system, a 20-node network, and/or a 50-node network, with randomly generated interdependency sets in three different topological forms (i.e., chain, tree, and cycle). The computational results demonstrate that (i) decomposition and cutting-plane algorithms effectively solve Model 1, and (ii) heuristic approaches dramatically decrease the CPU time for Model 2, but yield worse bounds when cardinalities of interdependency sets increase. Future research includes developing special algorithms for optimizing Model 2 for complex multiple infrastructures with special topological forms of system interdependency. (c) 2013 Elsevier Ltd. All rights reserved.
We consider an optimization problem that integrates network design and broadcast domination decisions. Given an undirected graph, a feasible broadcast domination is a set of nonnegative integer powers f (i) assigned t...
详细信息
We consider an optimization problem that integrates network design and broadcast domination decisions. Given an undirected graph, a feasible broadcast domination is a set of nonnegative integer powers f (i) assigned to each node i, such that for any node j in the graph, there exists some node k having a positive f (k) -value whose shortest distance to node j is no more than f (k) . The cost of a broadcast domination solution is the sum of all node power values. The network design problem constructs edges that decrease the minimum broadcast domination cost on the graph. The overall problem we consider minimizes the sum of edge construction costs and broadcast domination costs. We show that this problem is NP-hard in the strong sense, even on unweighted graphs. We then propose a decomposition strategy, which iteratively adds valid inequalities based on optimal broadcast domination solutions corresponding to the first-stage network design solutions. We demonstrate that our decomposition approach is computationally far superior to the solution of a single large-scale mixed-integer programming formulation.
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 th...
详细信息
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.
This paper presents a cutting-plane algorithm for nonlinear programming which, under suitable conditions, exhibits a linear or geometric global rate of convergence. Other known rates of convergence for cutting-plane a...
详细信息
This paper presents a cutting-plane algorithm for nonlinear programming which, under suitable conditions, exhibits a linear or geometric global rate of convergence. Other known rates of convergence for cutting-plane algorithms are no better than arithmetic for problems not satisfying a Haar condition. The feature responsible for this improved rate of convergence is the addition at each iteration of a new cut for each constraint, rather than adding only one new cut corresponding to the most violated constraint as is typically the case. Certain cuts can be dropped at each iteration, and there is a uniform upper bound on the number of old cuts retained. Geometric convergence is maintained if the subproblems at each iteration are approximated, rather than solved exactly, so the algorithm is implementable. The algorithm is flexible with respect to the point used to generate new cuts.
This paper presents the results of computational studies of the properties of cuttingplanealgorithms as applied to posynomial geometric programs. The four cuttingplanes studied represent the gradient method of Kell...
详细信息
This paper presents the results of computational studies of the properties of cuttingplanealgorithms as applied to posynomial geometric programs. The four cuttingplanes studied represent the gradient method of Kelley and an extension to develop tangential cuts; the geometric inequality of Duffin and an extension to generate several cuts at each iteration. As a result of over 200 problem solutions, we will draw conclusions regarding the effectiveness of acceleration procedures, feasible and infeasible starting point, and the effect of the initial bounds on the variables. As a result of these experiments, certain cuttingplane methods are seen to be attractive means of solving large scale geometric programs.
暂无评论