Facility Location Problem

Problem Description

The facility location problem is a well$-$known problem in the areas of production and operations management and combinatorial optimization. The problem finds an optimal location of facilities considering facility construction costs, transportation costs, etc. This problem is very popular because it is faced by many companies. A large number of researchers have studied this problem and proposed solution approaches.

The purpose of this project is to build a decision support system that helps the managers decide where to locate a facility. We give a mathematical formulation of the un$-$capacitated facility location problem and describe a primal$-$dual algorithm. We do not give details about why this algorithm works. To learn more about the problem and the primal$-$dual algorithm, we refer the student to Francis et al$.(1974)$ and Erlenkotter $(1978).$

Problem Formulation

Let I and J denote a set of facilities and customers, respectively $($i $=1,...,$m and j $=1,...,$n$),$ and let fi denote the fixed cost of locating a facility at location i$.$ Let cij be the cost of supplying customer j from facility i$.$ The decision variables are as follows:

xij: denotes the fraction of customer j$$s demand satisfied by facility i

The following is a mixed$-$integer linear programming formulation of the un$-$capacitated facility location problem.

The objective is to minimize the total costs. The first set of constraints shows that the demand of customer j $($for j $=1,...,$J$)$ will be satisfied. The second set of constraints shows that if a facility is not located at a potential location i$,$ there will be no shipments from that location. The third set of constraints is the non$-$negativity constraints, and the last set of constraints is the integrality constraints.

The following is the dual formulation of the linear programming relaxation of the un$-$capacitated facility location problem.

vj are the dual variables for constraint set $(1),$ and wij are the dual variables for constraint set $(2).$

Dual Ascent Algorithm

Initialization:

$-$ Let denote the set of customers whose vj$$s are eligible to change, initially $.$

$-$ Set vj $=$ c$1$j for all j$$J$.$

$-$ Calculate: $.$

$-$ Let for all j$$J$.$

Step $1$:

Set j $=1$ and $=0.$

Step $2$:

If $,$ go to Step $6.$

Step $3$:

Set

Step $4$:

If $,$ then set: ; $=1$ and k$($j$)=$ k$($j$)+1.$

Step $5$:

For each i$$I$,$ such that decrease si by $.$ Increase vj by $.$

Step $6$:

If $,$ let j $=$ j $+1$ and return to Step $2.$

Step $7$:

If $=1,$ return to Step $1,$ otherwise stop.

The dual adjustment procedure is used in the case that the dual variables found from the dual ascent algorithm do not satisfy the complementary slackness conditions.

Dual Adjustment Procedure

Step $1$:

Set j $=1.$

Step $2$:

If $,$ go to Step $7.$

Step $3$:

If is empty and is empty, go to Step $7.$

Step $4$:

For each i$$I such that $,$ decrease si by and decrease vj to $.$

Step $5$:

$($a$)$ Set and execute the dual ascent procedure.

$($b$)$ Repeat the dual ascent procedure using all of the j$$s that were not included in in Step $5($a$).$

$($c$)$ Repeat the dual ascent procedure with $.$

Step $6$:

If vj did not go back to its original value, return to Step $2.$

Step $7$:

If $,$ let j $=$ j $+1$ and return to Step $2.$ Otherwise, stop.

In this procedure we used the following notation:

The set of tight facilities.

The set of open facilities.

; The set of customers such that facility i$$I$*$ is the only one with $.$

; i$($j$)$ is the second best facility in I$+$ for customer j$.$

The next lower that we might decrease vj to$.$

Excel Spreadsheet

$1.$ Build a spreadsheet that presents the fixed cost of opening a facility $($fi for i$$I$).$

$2.$ Build a spreadsheet that presents the variable unit cost cij $($for i$$I and j$$J$).$

User Interface

$1.$ Create the welcome form.

$2.$ Build a data entry form. The following are suggestions to help you design this form. In this form insert two option buttons. These option buttons allow the user to select whether to read the data from a file or manually enter the data. Include a command button that, when clicked on$,$ performs these actions:

a$.$ If the user chose to read the data from a file, a text box should appear where the user types in the name of the file.

b$.$ If the user chose to enter the data manually, a text box appears where the user types in the total number of facilities $($m$)$ and the total number of customers $($n$).$ Upon submission of this information two tables appear. The first table with dimensions m by $1$ allows the user to type in the fixed cost of opening a facility. The second table with dimensions m by n allows the user to type in the total variable cost of supplying each customer from different suppliers.

$3.$ Build a form that allows the user to understand the facility location problem by looking at an example. This form includes the following:

a$.$ A problem statement.

b$.$ A problem formulation.

c$.$ Present how the dual algorithm was implemented for solving this examp