Economic spare capacity planning for DCS mesh-restorable networks

This paper considers an integer programming (IP) based optimization algorithm to solve the Spare Channel Assignment Problem (SCAP) for the new synchronous transmission networks that use a Digital Cross-Connect System (DCS) for each node of the network. Given predetermined working channels on each link of the network, the problem is to determine the spare capacity that should be added on each link to ensure rerouting of the traffic in case of a link failure. We propose an IP model which determines not only the spare capacity on each link but also the number of each link facility needed to be installed on each link to meet the aggregated requirements of working and spare channels. The objective is to minimize the total installation cost. We propose a branch-and-cut algorithm to solve the SCAR To solve the linear programming (LP) relaxation of the problem, an efficient constraint generation routine was devised. Moreover, some strong valid inequalities were found and used to strengthen the formulation. Computational results show that the algorithm can solve real world problems to optimality within a reasonable time.     

Supply capacity acquisition and allocation with uncertain customer demands

We study a class of capacity acquisition and assignment problems with stochastic customer demands often found in operations planning contexts. In this setting, a supplier utilizes a set of distinct facilities to satisfy the demands of different customers or markets. Our model simultaneously assigns customers to each facility and determines the best capacity level to operate or install at each facility. We propose a branch-and-price solution approach for this new class of stochastic assignment and capacity planning problems. For problem instances in which capacity levels must fall between some pre-specified limits, we offer a tailored solution approach that reduces solution time by nearly 80% over an alternative approach using a combination of commercial nonlinear optimization solvers. We have also developed a heuristic solution approach that consistently provides optimal or near-optimal solutions, where solutions within 0.01% of optimality are found on average without requiring a nonlinear optimization solver.     

Lagrangian-relaxation-based solution procedures for a multiproduct capacitated facility location problem with choice of facility type

This paper presents exact and heuristic solution procedures for a multiproduct capacitated facility location (MPCFL) problem in which the demand for a number of different product families must be supplied from a set of facility sites, and each site offers a choice of facility types exhibiting different capacities. MPCFL generalizes both the uncapacitated (or simple) facility location (UFL) problem and the pure-integer capacitated facility location problem. We define a branch-and-bound algorithm for MPCFL that utilizes bounds formed by a Lagrangian relaxation of MPCFL which decomposes the problem into UFL subproblems and easily solvable 0-1 knapsack subproblems. The UFL subproblems are solved by the dual-based procedure of Erlenkotter. We also present a subgradient optimization-Lagrangian relaxation-based heuristic for MPCFL. Computational experience with the algorithm and heuristic are reported. The MPCFL heuristic is seen to be extremely effective, generating solutions to the test problems that are on average within 2% of optimality, and the branch-and-bound algorithm is successful in solving all of the test problems to optimality.     

A linear programming approach for linear programs with probabilistic constraints

We study a class of mixed-integer programs for solving linear programs with joint probabilistic constraints from random right-hand side vectors with finite distributions. We present greedy and dual heuristic algorithms that construct and solve a sequence of linear programs. We provide optimality gaps for our heuristic solutions via the linear programming relaxation of the extended mixed-integer formulation of Luedtke et al. (2010) [13] as well as via lower bounds produced by their cutting plane method. While we demonstrate through an extensive computational study the effectiveness and scalability of our heuristics, we also prove that the theoretical worst-case solution quality for these algorithms is arbitrarily far from optimal. Our computational study compares our heuristics against both the extended mixed-integer programming formulation and the cutting plane method of Luedtke et al. (2010) [13]. Our heuristics efficiently and consistently produce solutions with small optimality gaps, while for larger instances the extended formulation becomes intractable and the optimality gaps from the cutting plane method increase to over 5%.     

An Optimization Problem with a Separable Non-Convex Objective Function and a Linear Constraint

For a class of global optimization (maximization) problems, with a separable non-concave objective function and a linear constraint a computationally efficient heuristic has been developed.The concave relaxation of a global optimization problem is introduced. An algorithm for solving this problem to optimality is presented. The optimal solution of the relaxation problem is shown to provide an upper bound for the optimal value of the objective function of the original global optimization problem. An easily checked sufficient optimality condition is formulated under which the optimal solution of concave relaxation problem is optimal for the corresponding non-concave problem. An heuristic algorithm for solving the considered global optimization problem is developed.The considered global optimization problem models a wide class of optimal distribution of a unidimensional resource over subsystems to provide maximum total output in a multicomponent systems.In the presented computational experiments the developed heuristic algorithm generated solutions, which either met optimality conditions or had objective function values with a negligible deviation from optimality (less than 1/10 of a percent over entire range of problems tested).     

Lower and upper bounds for location-arc routing problems with vehicle capacity constraints

This paper addresses multi-depot location arc routing problems with vehicle capacity constraints. Two mixed integer programming models are presented for single and multi-depot problems. Relaxing these formulations leads to other integer programming models whose solutions provide good lower bounds for the total cost. A powerful insertion heuristic has been developed for solving the underlying capacitated arc routing problem. This heuristic is used together with a novel location–allocation heuristic to solve the problem within a simulated annealing framework. Extensive computational results demonstrate that the proposed algorithm can find high quality solutions. We also show that the potential cost saving resulting from adding location decisions to the capacitated arc routing problem is significant.     

Upper bounds for objective functions of discrete competitive facility location problems

Under study is the problem of locating facilities when two competing companies successively open their facilities. Each client chooses an open facility according to his own preferences and return interests to the leader firm or to the follower firm. The problem is to locate the leader firm so as to realize the maximum profit (gain) subject to the responses of the follower company and the available preferences of clients. We give some formulations of the problems under consideration in the form of two-level integer linear programming problems and, equivalently, as pseudo-Boolean two-level programming problems. We suggest a method of constructing some upper bounds for the objective functions of the competitive facility location problems. Our algorithm consists in constructing an auxiliary pseudo-Boolean function, which we call an estimation function, and finding the minimum value of this function. For the special case of the competitive facility location problems on paths, we give polynomial-time algorithms for finding optimal solutions. Some results of computational experiments allow us to estimate the accuracy of calculating the upper bounds for the competitive location problems on paths.     

Topological Design of Survivable Mesh-Based Transport Networks

The advent of Sonet and DWDM mesh-restorable networks which contain explicit reservations of spare capacity for restoration presents a new problem in topological network design. On the one hand, the routing of working flows wants a sparse tree-like graph for minimization of the classic fixed charge plus routing (FCR) costs. On the other hand, restorability requires a closed (bi-connected) and preferably high-degree topology for efficient sharing of spare capacity allocations (SCA) for restoration over non-simultaneous failure scenarios. These diametrically opposed considerations underlie the determination of an optimum physical facilities graph for a broadband network provider. Standalone instances of each constituent problem are NP-hard. The full problem of simultaneously optimizing mesh-restorable topology, routing, and sparing is therefore very difficult computationally. Following a comprehensive survey of prior work on topological design problems, we provide a {1–0} MIP formulation for the complete mesh-restorable design problem and also propose a novel three-stage heuristic. The heuristic is based on the hypothesis that the union set of edges obtained from separate FCR and SCA sub-problems constitutes an effective topology space within which to solve a restricted instance of the full problem. Where fully optimal reference solutions are obtainable the heuristic shows less than 8% gaps but runs in minutes as opposed to days. In other test cases the reference problem cannot be solved to optimality and we can only report that heuristic results obtained in minutes are not improved upon by CPLEX running the full problem for 6 to 18 hours. The computational behavior we observe gives insight for further work based on an appreciation of the problem as embodying unexpectedly difficult feasibility apects, as well as optimality aspects.     

Improving benders decomposition using a genetic algorithm

We develop and investigate the performance of a hybrid solution framework for solving mixed-integer linear programming problems. Benders decomposition and a genetic algorithm are combined to develop a framework to compute feasible solutions. We decompose the problem into a master problem and a subproblem. A genetic algorithm along with a heuristic are used to obtain feasible solutions to the master problem, whereas the subproblem is solved to optimality using a linear programming solver. Over successive iterations the master problem is refined by adding cutting planes that are implied by the subproblem. We compare the performance of the approach against a standard Benders decomposition approach as well as against a stand-alone solver (Cplex) on MIPLIB test problems.     

On design of a survivable network architecture for dynamic routing: Optimal solution strategy and an efficient heuristic

We investigate network planning and design under volatile conditions of link failures and traffic overload. Our model is a non-simultaneous multi-commodity problem, with any particular two link failure being considered as one scenario. We show that the optimal solution model is not practically solvable for real-world problems and hence an efficient heuristic is provided which is O(n⁶) faster than the optimal model and is based on synthesizing a modified maximum spanning tree using an algorithm due to Gomory and Hu. The output of this procedure is then used to solve a much smaller linear program. Simulation results indicate that the heuristic is near optimal for problems with up to 40 nodes.     

The out-of-kilter algorithm applied to traffic congestion

The out-of-kilter algorithm finds a minimum cost assignment of flows to a network defined in terms of one-way arcs, each with upper and lower bounds on flow, and a cost. It is a mathematical programming algorithm which exploits the network structure of the data. The objective function, being the sum taken over all the arcs of the products, cost×flow, is linear. The algorithm is applied in a new way to minimise a series of linear functions in a heuristic method to reduce the value of a non-convex quadratic function which is a measure of traffic congestion. The coefficients in these linear functions are chosen in a way which avoids one of the pitfalls occurring when Beale's method is applied to such a quadratic function. The method does not guarantee optimality but has produced optimal results with networks small enough for an integer linear programming method to be feasible.     

The design of reverse distribution networks: Models and solution procedures

Reverse distribution, or the management of product return flows, induced by various forms of reuse of products and materials, has received growing attention throughout this decade. In this paper we discuss reverse distribution, and propose a mathematical programming model for a version of this problem. Due to the complexity of the proposed model, we introduce a heuristic solution methodology for this problem. The solution methodology complements a heuristic concentration procedure, where sub-problems with reduced sets of decision variables are iteratively solved to optimality. Based on the solutions from the sub-problems, a final concentration set of potential facility sites is constructed, and this problem is solved to optimality. The potential facility sites are then expanded in a greedy fashion to obtain the final solution. This “heuristic expansion” was also performed using the solution found with a greedy heuristic to provide a short-list of potential facility sites. Computational tests demonstrate a great deal of promise for this solution method, as high-quality solutions are obtained while expending modest computational effort.     

A resource investment problem with time/resource trade-offs

In this study, we consider a Resource Investment Problem with time/resource trade-offs in project networks. We assume that there is a single renewable resource and the processing requirement of an activity can be reduced by investing extra resources. Our aim is to minimize the maximum resource usage, hence, the total amount invested for the single resource, while meeting the pre-specified deadline. We formulate the problem as a mixed integer linear model and find optimal solutions for small-sized problem instances. For large-sized problem instances, we propose a heuristic solution procedure. We develop several lower bounds and use them to evaluate the performance of our heuristic procedure. The results of our computational experiments have revealed the satisfactory behaviour of our optimality properties, lower bounds and heuristic procedure.     

An LP-based heuristic for two-stage capacitated facility location problems

In this paper, a linear programming based heuristic is considered for a two-stage capacitated facility location problem with single source constraints. The problem is to find the optimal locations of depots from a set of possible depot sites in order to serve customers with a given demand, the optimal assignments of customers to depots and the optimal product flow from plants to depots. Good lower and upper bounds can be obtained for this problem in short computation times by adopting a linear programming approach. To this end, the LP formulation is iteratively refined using valid inequalities and facets which have been described in the literature for various relaxations of the problem. After each reoptimisation step, that is the recalculation of the LP solution after the addition of valid inequalities, feasible solutions are obtained from the current LP solution by applying simple heuristics. The results of extensive computational experiments are given.     

A fast heuristic method for minimizing traffic congestion on reconfigurable ring topologies

We describe the development of fast heuristics and methodologies for congestion minimization problems in directional wireless networks, and we compare their performance with optimal solutions. The focus is on the network layer topology control problem (NLTCP) defined by selecting an optimal ring topology as well as the flows on it. Solutions to NLTCP need to be computed in near realtime due to changing weather and other transient conditions and which generally preclude traditional optimization strategies. Using a mixed-integer linear programming formulation, we present both new constraints for this problem and fast heuristics to solve it. The new constraints are used to increase the lower bound from the linear programming relaxation and hence speed up the solution of the optimization problem by branch and bound. The upper and lower bounds for the optimal objective function to the mixed integer problem then serve to evaluate new node-swapping heuristics which we also present. Through a series of tests on different sized networks with different traffic demands, we show that our new heuristics achieve within about 0.5% of the optimal value within seconds.     

Global optimality conditions for quadratic 0-1 optimization problems

In the present work, we intend to derive conditions characterizing globally optimal solutions of quadratic 0-1 programming problems. By specializing the problem of maximizing a convex quadratic function under linear constraints, we find explicit global optimality conditions for quadratic 0-1 programming problems, including necessary and sufficient conditions and some necessary conditions. We also present some global optimality conditions for the problem of minimization of half-products.     

Plant location with minimum inventory

We present an integer programming model for plant location with inventory costs. The linear programming relaxation has been solved by Dantzig-Wolfe decomposition. In this case the subproblems reduce to the minimum cut problem. We have used subgradient optimization to accelerate the convergence of the D-W algorithm. We present our experience with problems arising in the design of a distribution network for computer spare parts. In most cases, from a fractional solution we were able to derive integer solutions within 4% of optimality.     

A Lagrangian heuristic for concave cost facility location problems: the plant location and technology acquisition problem

We propose a Lagrangian heuristic for facility location problems with concave cost functions and apply it to solve the plant location and technology acquisition problem. The problem is decomposed into a mixed integer subproblem and a set of trivial single-variable concave minimization subproblems. We are able to give a closed-form expression for the optimal Lagrangian multipliers such that the Lagrangian bound is obtained in a single iteration. Since the solution of the first subproblem is feasible to the original problem, a feasible solution and an upper bound are readily available. The Lagrangian heuristic can be embedded in a branch-and-bound scheme to close the optimality gap. Computational results show that the approach is capable of reaching high quality solutions efficiently. The proposed approach can be tailored to solve many concave-cost facility location problems.     

The bilevel programming problem: reformulations, constraint qualifications and optimality conditions

We consider the bilevel programming problem and its optimal value and KKT one level reformulations. The two reformulations are studied in a unified manner and compared in terms of optimal solutions, constraint qualifications and optimality conditions. We also show that any bilevel programming problem where the lower level problem is linear with respect to the lower level variable, is partially calm without any restrictive assumption. Finally, we consider the bilevel demand adjustment problem in transportation, and show how KKT type optimality conditions can be obtained under the partial calmness, using the differential calculus of Mordukhovich.     

Topological design of wide area communication networks

This paper develops a model for designing a backbone network. It assumes the location of the backbone nodes, the traffic between the backbone nodes and the link capacities are given. It determines the links to be included in the design and the routes used by the origin destination pairs. The objective is to obtain the least cost design where the system costs consist of connection costs and queueing costs. The connection costs depend on link capacity and queueing costs are incurred by users due to the limited capacity of links. The Lagrangian relaxation embedded in a subgradient optimization procedure is used to obtain lower bounds on the optimal solution of the problem. A heuristic based on the Lagrangian relaxation is developed to generate feasible solutions.