A convergence proof for linear mean value cross decomposition

The mean value cross decomposition method for linear programming problems is a modification of ordinary cross decomposition that eliminates the need for using the Benders or Dantzig-Wolfe master problem. It is a generalization of the Brown-Robinson method for a finite matrix game and can also be considered as a generalization of the Kornai-Liptak method. It is based on the subproblem phase in cross decomposition, where we iterate between the dual subproblem and the primal subproblem. As input to the dual subproblem we use the average of a part of all dual solutions of the primal subproblem, and as input to the primal subproblem we use the average of a part of all primal solutions of the dual subproblem. In this paper we give a new proof of convergence for this procedure. Previously convergence has only been shown for the application to a special separable case (which covers the Kornai-Liptak method), by showing equivalence to the Brown-Robinson method.     

Accelerating Benders' decomposition for the capacitated facility location problem

Discrete facility location problems are attractive candidates for decomposition procedures since two types of decisions have to be performed: on the one hand the yes/no-decision where to locate the facilities, on the other hand the decision how to allocate the demand to the selected facilities. Nevertheless, Benders' decomposition seems to have a rather slow convergence behaviour when applied for solving location problems. In the following, a procedure will be presented for strengthening the Benders' cuts for the capacitated facility location problem. Computational results show the efficiency of the modified Benders' decomposition algorithm. Furthermore, the paretooptimality of the strengthened Benders' cuts in the sense of [Magnanti and Wong 1990] is shown under a weak assumption.This paper was written when the author was at the Institute for Operations Research, University of St. Gallen, Switzerland, and partly supported by Schweizerischer Nationalfond zur Förderung der wissenschaftlichen Forschung (Grant 12-30140.90).     

Solution methods for the bi-objective (cost-coverage) unconstrained facility location problem with an illustrative example

The Colombian coffee supply network, managed by the Federación Nacional de Cafeteros de Colombia (Colombian National Coffee-Growers Federation), requires slimming down operational costs while continuing to provide a high level of service in terms of coverage to its affiliated coffee growers. We model this problem as a biobjective (cost-coverage) uncapacitated facility location problem (BOUFLP). We designed and implemented three different algorithms for the BOUFLP that are able to obtain a good approximation of the Pareto frontier. We designed an algorithm based on the Nondominated Sorting Genetic Algorithm; an algorithm based on the Pareto Archive Evolution Strategy; and an algorithm based on mathematical programming. We developed a random problem generator for testing and comparison using as reference the Colombian coffee supply network with 29 depots and 47 purchasing centers. We compared the algorithms based on the quality of the approximation to the Pareto frontier using a nondominated space metric inspired on Zitzler and Thiele's. We used the mathematical programming-based algorithm to identify unique tradeoff opportunities for the reconfiguration of the Colombian coffee supply network. Finally, we illustrate an extension of the mathematical programming-based algorithm to perform scenario analysis for a set of uncapacitated location problems found in the literature.     

A decomposition approach for facility location and relocation problem with uncertain number of future facilities

In this paper, we discuss two challenges of long term facility location problem that occur simultaneously; future demand change and uncertain number of future facilities. We introduce a mathematical model that minimizes the initial and expected future weighted travel distance of customers. Our model allows relocation for the future instances by closing some of the facilities that were located initially and opening new ones, without exceeding a given budget. We present an integer programming formulation of the problem and develop a decomposition algorithm that can produce near optimal solutions in a fast manner. We compare the performance of our mathematical model against another method adapted from the literature and perform sensitivity analysis. We present numerical results that compare the performance of the proposed decomposition algorithm against the exact algorithm for the problem.     

A polynomial time algorithm for solving the fermat-weber location problem with mixed norms

This paper discusses the Fermat-Weber location problem, manages to apply the ellipsoid method to this problem and proves the ellipsoid method can be terminated at an approximately optimal location in polynomial time, verifies the ellipsoid method is robust for the lower dimensional location problem     

A projection method for the uncapacitated facility location problem

Several algorithms already exist for solving the uncapacitated facility location problem. The most efficient are based upon the solution of the strong linear programming relaxation. The dual of this relaxation has a condensed form which consists of minimizing a certain piecewise linear convex function. This paper presents a new method for solving the uncapacitated facility location problem based upon the exact solution of the condensed dual via orthogonal projections. The amount of work per iteration is of the same order as that of a simplex iteration for a linear program inm variables and constraints, wherem is the number of clients. For comparison, the underlying linear programming dual hasmn + m + n variables andmn +n constraints, wheren is the number of potential locations for the facilities. The method is flexible as it can handle side constraints. In particular, when there is a duality gap, the linear programming formulation can be strengthened by adding cuts. Numerical results for some classical test problems are included.     

A new approximation algorithm for the multilevel facility location problem

In this paper we propose a new integer programming formulation for the multilevel facility location problem and a novel 3-approximation algorithm based on LP-rounding. The linear program that we use has a polynomial number of variables and constraints, thus being more efficient than the one commonly used in the approximation algorithms for these types of problems.     

A cut-and-solve based algorithm for the single-source capacitated facility location problem

In this paper, we present a cut-and-solve (CS) based exact algorithm for the Single Source Capacitated Facility Location Problem (SSCFLP). At each level of CS’s branching tree, it has only two nodes, corresponding to the Sparse Problem (SP) and the Dense Problem (DP), respectively. The SP, whose solution space is relatively small with the values of some variables fixed to zero, is solved to optimality by using a commercial MIP solver and its solution if it exists provides an upper bound to the SSCFLP. Meanwhile, the resolution of the LP of DP provides a lower bound for the SSCFLP. A cutting plane method which combines the lifted cover inequalities and Fenchel cutting planes to separate the 0–1 knapsack polytopes is applied to strengthen the lower bound of SSCFLP and that of DP. These lower bounds are further tightened with a partial integrality strategy. Numerical tests on benchmark instances demonstrate the effectiveness of the proposed cutting plane algorithm and the partial integrality strategy in reducing integrality gap and the effectiveness of the CS approach in searching an optimal solution in a reasonable time. Computational results on large sized instances are also presented.     

A constant factor approximation algorithm for the fault-tolerant facility location problem

We consider a generalization of the classical facility location problem, where we require the solution to be fault-tolerant. In this generalization, every demand point j must be served by r_j facilities instead of just one. The facilities other than the closest one are “backup” facilities for that demand, and any such facility will be used only if all closer facilities (or the links to them) fail. Hence, for any demand point, we can assign nonincreasing weights to the routing costs to farther facilities. The cost of assignment for demand j is the weighted linear combination of the assignment costs to its r_j closest open facilities. We wish to minimize the sum of the cost of opening the facilities and the assignment cost of each demand j. We obtain a factor 4 approximation to this problem through the application of various rounding techniques to the linear relaxation of an integer program formulation. We further improve the approximation ratio to 3.16 using randomization and to 2.41 using greedy local-search type techniques.     

p-Hub approach for the optimal park-and-ride facility location problem

Park and Ride facilities (P&R) are car parks at which users can transfer to public transportation to reach their final destination. We propose a mixed linear programming formulation to determine the location of a fixed number of P&R facilities so that their usage is maximized. The facilities are modeled as hubs. Commuters can use one of the P&R facilities or choose to travel by car to their destinations, and their behavior follows a logit model. We apply a p-hub approach considering that users incur in a known generalized cost of using each P&R facility as input for the logit model. For small instances of the problem, we propose a novel linearization of the logit model, which allows transforming the binary nonlinear programming problem into a mixed linear programming formulation. A modification of the Heuristic Concentration Integer (HCI) procedure is applied to solve larger instances of the problem. Numerical experiments are performed, including a case in Queens, NY. Further research is proposed.     

A general model for the undesirable single facility location problem

In this paper, a finite set in which an optimal solution for a general Euclidean problem of locating an undesirable facility in a polygonal region, is determined and can be found in polynomial time. The general problem we propose leads us, among others, to several well-known problems such as the maxisum, maximin, anticentdian or r-anticentrum problem.     

The approximation gap for the metric facility location problem is not yet closed

We consider the 1.52-approximation algorithm of Mahdian et al. for the metric uncapacitated facility location problem. We show that their algorithm does not close the gap with the lower bound on approximability, 1.463, by providing a construction of instances for which its approximation ratio is not better than 1.494.     

A branch and bound algorithm for the two-level uncapacitated facility location problem with some side constraints

This paper deals with the problem of locating at minimum total costs both plants and warehouses in a two-level distribution system where commodities are delivered from plants to customers either directly or indirectly via warehouses. Some side-constraints are imposed on the problem, which represent the adjunct relationship of some warehouses to a certain plant. Proposed is an efficient branch and bound solution procedure, employing a set of new devices for lower bounds and simplifications which are obtained by exploiting the submodularity of the objective function and the special structure of the side-constraints. Computational experiments with fifteen test problems are provided.     

Lower and upper bounds for a two-stage capacitated facility location problem with handling costs

We study in this paper multi-product facility location problem in a two-stage supply chain in which plants have production limitation, potential depots have limited storage capacity and customer demands must be satisfied by plants via depots. In the paper, handling cost for batch process in depots is considered in a realistic way by a set of capacitated handling modules. Each module can be regards as alliance of equipment and manpower. The problem is to locate depots, choose appropriate handling modules and to determine the product flows from the plants, opened depots to customers with the objective to minimize total location, handling and transportation costs. For the problem, we developed a hybrid method. The initial lower and upper bounds are provided by applying a Lagrangean based on local search heuristic. Then a weighted Dantzig–Wolfe decomposition and path-relinking combined method are proposed to improve obtained bounds. Numerical experiments on 350 randomly generated instances demonstrate our method can provide high quality solution with gaps below 2%.     

‘Multidimensional’ extensions and a nested dual approach for the m-median problem

A general framework for modeling median type locational decisions, where (i) travel costs and demands may be stochastic, (ii) multiple services or commodities need to be considered, and/or (iii) multiple median type objectives might exist, is presented—using the concept of “multidimensional networks”. The classical m-median problem, the stochastic m-median problem, the multicommodity m-median problem and and multiobjective m-median problem are defined within this framework.By an appropriate transformation of variables, the multidimensional m-median problem simplifies to the classical m-median problem but with a K-fold increase in the number of nodes, where K is the number of dimensions of the network. A nested dual approach to solve the resulting classical m-median problem, that uses Erlenkotter's facility location scheme as a subroutine, is presented. Computational results indicate that the procedure may perhaps be the best available one to solve the m-median problem exactly.     

Perturbed projections and subgradient projections for the multiple-sets split feasibility problem

We study the multiple-sets split feasibility problem that requires to find a point closest to a family of closed convex sets in one space such that its image under a linear transformation will be closest to another family of closed convex sets in the image space. By casting the problem into an equivalent problem in a suitable product space we are able to present a simultaneous subgradients projections algorithm that generates convergent sequences of iterates in the feasible case. We further derive and analyze a perturbed projection method for the multiple-sets split feasibility problem and, additionally, furnish alternative proofs to two known results.     

A combined facility location and network design problem with multi-type of capacitated links

This article presents a mixed-integer model to optimize the location of facilities and the underlying transportation network at the same time to minimize the total transportation and operating costs. In this problem, it is assumed that for connecting two nodes, there are several types of links in which their capacity, transportation and construction costs are different. The developed model has various applications in telecommunication, emergency, regional planning, pipeline network, energy management, distribution, to just name a few. To solve the model effectively, this paper also proposes a fix-and-optimize heuristic based on the evolutionary fire-fly algorithm. Finally, to validate the model and evaluate the algorithm’s performance, a series of test instances with up to 100 nodes and 600 candidate links with three different levels of quality are reported.     

Projected subgradient methods with non-Euclidean distances for non-differentiable convex minimization and variational inequalities

We study subgradient projection type methods for solving non-differentiable convex minimization problems and monotone variational inequalities. The methods can be viewed as a natural extension of subgradient projection type algorithms, and are based on using non-Euclidean projection-like maps, which generate interior trajectories. The resulting algorithms are easy to implement and rely on a single projection per iteration. We prove several convergence results and establish rate of convergence estimates under various and mild assumptions on the problem’s data and the corresponding step-sizes. We dedicate this paper to Boris Polyak on the occasion of his 70th birthday.     

An acceleration of Erlenkotter-Körkel’s algorithms for the uncapacitated facility location problem

This contribution is focused on an acceleration of branch and bound algorithms for the uncapacitated facility location problem. Our approach is based on the well-known Erlenkotters’ procedures and Körkels’ multi-ascent and multi-adjustment algorithms, which have proved to be the efficient tools for solving the large-sized instances of the uncapacitated facility location problem. These two original approaches were examined and a thorough analysis of their performance revealed how each particular procedure contributes to the computational time of the whole algorithms. These analyses helped us to focus our effort on the most frequent procedures. The unique contribution of this paper is a new dual ascent procedure. This procedure leads to considerable acceleration of the lower bound computation process and reduces the resulting computational time. To demonstrate more efficient performance of amended algorithms we present the results of extensive numerical experiments.