A Dual-Bounded Algorithm for the p-Median Problem

Galvão, Roberto O.
September 1980
Operations Research;Sep/Oct80, Vol. 28 Issue 5, p1112
Academic Journal
The p-median problem consists of locating p facilities on a network, so that the sum of shortest distances from each of the nodes of the network to its nearest facility is minimized. A dual bound, based on the dual of the LP relaxation of the integer programming formulation of the problem, is developed and tested in a branch-and-bound algorithm. Computational results show that the resulting solution procedure has some advantages over existing exact methods for this problem.


Related Articles

  • A NEW BRANCH-AND-BOUND ALGORITHM FOR THE FIXED-CHARGE TRANSPORTATION PROBLEM. Kennington, Jeff; Unger, Ed // Management Science;Jun76, Vol. 22 Issue 10, p1116 

    A new branch-and-bound procedure specialized for the fixed-charge transportation problem has been developed. The technique strongly exploits the underlying transportation structure. The relaxed problem assumes this form and simple penalties are easily constructed from the optimal solution of...

  • Merging and Sorting Applied to the Zero-One Knapsack Problem. Ahrens, J. H.; Finke, G. // Operations Research;Nov/Dec75, Vol. 23 Issue 6, p1099 

    Branch-and-bound algorithms are adequate for the solution of a wide range of 0-1 knapsack problems. It is shown that the simplest method of branching is as good as any. However, problems with highly correlated large weights and values quickly become unsolvable in a reasonable time. This paper...

  • Classical Cuts for Mixed-Integer Programming and Branch-and-Cut. Padberg, Manfred // Annals of Operations Research;Oct2005, Vol. 139 Issue 1-4, p321 

    We review classical valid linear inequalities for mixed-integer programming, i.e., Gomory’s fractional and mixed-integer cuts, and discuss their use in branch-and-cut. In particular, a generalization of the recent mixed-integer rounding (MIR) inequality and a sufficient condition for the...

  • Augmented Reality Internet Labs versus its Traditional and Virtual Equivalence. Odeh, Salaheddin; Abu Shanab, Shatha; Anabtawi, Mahasen // International Journal of Emerging Technologies in Learning;2015, Vol. 10 Issue 3, p4 

    Engineering is an applied science; it makes science come alive through experiments and labs. Students can only gain practical knowledge that goes beyond mere scientific theory in the educational labs. This can be done using three different types of educational labs: Augmented reality labs,...

  • AN APPROACH FOR THE OPTIMAL SOLUTION OF MILP PROBLEMS. Ubale, P. V. // Bulletin of Pure & Applied Sciences-Mathematics;Jul-Dec2012, Vol. 31E Issue 2, p169 

    This paper describes an algorithm for finding solutions to optimization problems in which some of the variables must take integer values. The solution of discrete optimization problem to optimality is often an immense job requiring very efficient algorithm. In this paper we describe a Branch and...

  • BRANCH-AND-BOUND METHODS: A SURVEY. Lawler, E. L.; Wood, D. E. // Operations Research;Jul/Aug66, Vol. 14 Issue 4, p699 

    The essential features of the branch-and-bound approach to constrained optimization are described, and several specific applications are reviewed. These include integer linear programming (LAND-DOIG and BALAS methods), nonlinear programming (minimization of nonconvex objective functions), the...

  • Towards a closer integration of finite domain propagation and simplex-based algorithms. Hajian, Mozafar T.; El-Sakkout, Hani; Wallace, Mark; Lever, Jonathan M.; Richards, Barry // Annals of Operations Research;1998, Vol. 81 Issue 1-4, p421 

    This paper describes our experience in implementing an industrial application using the finite domain solver of the ECLiPSe constraint logic programming (CLP) system, in conjunction with the mathematical programming (MP) system, FortMP. In this technique, the ECLiPSe system generates a feasible...

  • A Branch and Bound Algorithm to Minimize Total Weighted Tardiness on a Single Processor. Babu, Pascal; Peridy, Laurent; Pinson, Eric // Annals of Operations Research;Jul2004, Vol. 129 Issue 1-4, p33 

    In this paper, we consider the problem of minimizing the total weighted tardiness of a set of jobs processed on a single processor. First, a lower bound based on a Lagrangian decomposition is presented. The particularity of this decomposition, based on a 0–1 time indexed formulation, is...

  • AN ALGORITHM FOR LARGE SET PARTITIONING PROBLEMS. Marsten, Roy E. // Management Science;Jan1974, Vol. 20 Issue 5, p774 

    An algorithm is presented for the special integer linear program known as the set partitioning problem. This problem has a binary coefficient matrix, binary variables, and unit resources. Furthermore, all of its constraints are equations: In spite of its very special form, the set partitioning...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics