Mixed integer programming-based solution procedure for single-facility location with maximin of rectilinear distance

Date

2008-04-01

Author

Nadirler, D.
Karasakal, Esra

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

74
views

0
downloads

In this paper, we study the 1-maximin problem with rectilinear distance. We locate a single undesirable facility in a continuous planar region while considering the interaction between the facility and existing demand points. The distance between facility and demand points is measured in the rectilinear metric. The objective is to maximize the distance of the facility from the closest demand point. The 1-maximin problem has been formulated as an MIP model in the literature. We suggest new bounding schemes to increase the solution efficiency of the model as well as improved branch and bound strategies for implementation. Moreover, we simplify the model by eliminating some redundant integer variables. We propose an efficient solution algorithm called cut and prune method, which splits the feasible region into four equal subregions at each iteration and tries to eliminate subregions depending on the comparison of upper and lower bounds. When the sidelengths of the subregions are smaller than a predetermined value, the improved MIP model is solved to obtain the optimal solution. Computational experiments demonstrate that the solution time of the original MIP model is reduced substantially by the proposed solution approach.

Subject Keywords

Marketing, Management Science and Operations Research, Strategy and Management, Management Information Systems

URI

https://hdl.handle.net/11511/48404

Journal

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY

DOI

https://doi.org/10.1057/palgrave.jors.2602372

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

The multi-resource agent bottleneck generalised assignment problem Karsu, Ozlem; Azizoğlu, Meral (Informa UK Limited, 2012-01-01) In this study, we consider the multi resource agent bottleneck generalised assignment problem. Our aim is to minimise the maximum load over all agents. We take our motivation from an assignment problem faced in heating, ventilating and air conditioning sector. We study the linear programming (LP) relaxation of the problem. We use the optimal LP relaxation solutions in our branch and bound algorithm while defining bounding and branching schemes. We find that our branch and bound algorithm returns optimal sol...
JOB-SHOP SCHEDULING UNDER A NONRENEWABLE RESOURCE CONSTRAINT TOKER, A; KONDAKCI, S; ERKIP, N (JSTOR, 1994-08-01) In this paper we consider the job shop scheduling problem under a discrete non-renewable resource constraint. We assume that jobs have arbitrary processing times and resource requirements and there is a unit supply of the resource at each time period. We develop an approximation algorithm for this problem and empirically test its effectiveness in finding the minimum makespan schedules.
A flexible flowshop problem with total flow time minimization Azizoğlu, Meral; Kondakci, S (Elsevier BV, 2001-08-01) In this study, we consider total flow time problem in a flexible flowshop environment. We develop a branch and bound algorithm to find the optimal schedule. The efficiency of the algorithm is enhanced by upper and lower bounds and a dominance criterion. Computational experience reveals that the algorithm solves moderate sized problems in reasonable solution times.
A discrete optimality system for an optimal harvesting problem Bakan, Hacer Oz; Yilmaz, Fikriye; Weber, Gerhard Wilhelm (Springer Science and Business Media LLC, 2017-10-01) In this paper, we obtain the discrete optimality system of an optimal harvesting problem. While maximizing a combination of the total expected utility of the consumption and of the terminal size of a population, as a dynamic constraint, we assume that the density of the population is modeled by a stochastic quasi-linear heat equation. Finite-difference and symplectic partitioned Runge-Kutta (SPRK) schemes are used for space and time discretizations, respectively. It is the first time that a SPRK scheme is e...
A resource investment problem with time/resource trade-offs Colak, Erdem; Azizoğlu, Meral (Informa UK Limited, 2014-05-01) 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 in...

Citation Formats

D. Nadirler and E. Karasakal, “Mixed integer programming-based solution procedure for single-facility location with maximin of rectilinear distance,” JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, pp. 563–570, 2008, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/48404.