Assignment Problem Integer Linear Programming Matlab

This example shows how to set up and solve a mixed-integer linear programming problem. The problem is to find the optimal production and distribution levels among a set of factories, warehouses, and sales outlets. For the solver-based approach, see Factory, Warehouse, Sales Allocation Model: Solver-Based.

The example first generates random locations for factories, warehouses, and sales outlets. Feel free to modify the scaling parameter , which scales both the size of the grid in which the production and distribution facilities reside, but also scales the number of these facilities so that the density of facilities of each type per grid area is independent of .

Facility Locations

For a given value of the scaling parameter , suppose that there are the following:

  • factories

  • warehouses

  • sales outlets

These facilities are on separate integer grid points between 1 and in the and directions. In order that the facilities have separate locations, you require that . In this example, take , , , and .

Production and Distribution

There are products made by the factories. Take .

The demand for each product in a sales outlet is . The demand is the quantity that can be sold in a time interval. One constraint on the model is that the demand is met, meaning the system produces and distributes exactly the quantities in the demand.

There are capacity constraints on each factory and each warehouse.

Suppose that each sales outlet receives its supplies from just one warehouse. Part of the problem is to determine the cheapest mapping of sales outlets to warehouses.

Costs

The cost of transporting products from factory to warehouse, and from warehouse to sales outlet, depends on the distance between the facilities, and on the particular product. If is the distance between facilities and , then the cost of shipping a product between these facilities is the distance times the transportation cost :

The distance in this example is the grid distance, also known as the distance. It is the sum of the absolute difference in coordinates and coordinates.

The cost of making a unit of product in factory is .

Optimization Problem

Given a set of facility locations, and the demands and capacity constraints, find:

  • A production level of each product at each factory

  • A distribution schedule for products from factories to warehouses

  • A distribution schedule for products from warehouses to sales outlets

These quantities must ensure that demand is satisfied and total cost is minimized. Also, each sales outlet is required to receive all its products from exactly one warehouse.

Variables and Equations for the Optimization Problem

The control variables, meaning the ones you can change in the optimization, are

The objective function to minimize is

The constraints are

(capacity of factory).

(demand is met).

(capacity of warehouse).

(each sales outlet associates to one warehouse).

(nonnegative production).

(binary ).

The variables and appear in the objective and constraint functions linearly. Because is restricted to integer values, the problem is a mixed-integer linear program (MILP).

Generate a Random Problem: Facility Locations

Set the values of the , , , and parameters, and generate the facility locations.

Of course, it is not realistic to take random locations for facilities. This example is intended to show solution techniques, not how to generate good facility locations.

Plot the facilities. Facilities 1 through F are factories, F+1 through F+W are warehouses, and F+W+1 through F+W+S are sales outlets.

Generate Random Capacities, Costs, and Demands

Generate random production costs, capacities, turnover rates, and demands.

These random demands and capacities can lead to infeasible problems. In other words, sometimes the demand exceeds the production and warehouse capacity constraints. If you alter some parameters and get an infeasible problem, during solution you will get an exitflag of -2.

Generate Variables and Constraints

To begin specifying the problem, generate the distance arrays and .

Create variables for the optimization problem. represents the production, a continuous variable, with dimension -by--by-. represents the binary allocation of sales outlet to warehouse, an -by- variable.

Now create the constraints. The first constraint is a capacity constraint on production.

The next constraint is that the demand is met at each sales outlet.

There is a capacity constraint at each warehouse.

Finally, there is a requirement that each sales outlet connects to exactly one warehouse.

Create Problem and Objective

Create an optimization problem.

The objective function has three parts. The first part is the sum of the production costs.

The second part is the sum of the transportation costs from factories to warehouses.

The third part is the sum of the transportation costs from warehouses to sales outlets.

The objective function to minimize is the sum of the three parts.

Include the constraints in the problem.

Solve the Problem

Turn off iterative display so that you don't get hundreds of lines of output. Include a plot function to monitor the solution progress.

Call the solver to find the solution.

Examine the Solution

Examine the exit flag and the infeasibility of the solution.

Round the portion of the solution to be exactly integer-valued. To understand why these variables might not be exactly integers, see the documentation.

How many sales outlets are associated with each warehouse? Notice that, in this case, some warehouses have 0 associated outlets, meaning the warehouses are not in use in the optimal solution.

Plot the connection between each sales outlet and its warehouse.

The black * with no green lines represent the unused warehouses.

rng(1) % for reproducibility N = 20; % N from 10 to 30 seems to work. Choose large values with caution. N2 = N*N; f = 0.05; % density of factories w = 0.05; % density of warehouses s = 0.1; % density of sales outlets F = floor(f*N2); % number of factories W = floor(w*N2); % number of warehouses S = floor(s*N2); % number of sales outlets xyloc = randperm(N2,F+W+S); % unique locations of facilities [xloc,yloc] = ind2sub([N N],xyloc);
h = figure; plot(xloc(1:F),yloc(1:F),'rs',xloc(F+1:F+W),yloc(F+1:F+W),'k*',... xloc(F+W+1:F+W+S),yloc(F+W+1:F+W+S),'bo'); lgnd = legend('Factory','Warehouse','Sales outlet','Location','EastOutside'); lgnd.AutoUpdate = 'off'; xlim([0 N+1]);ylim([0 N+1])
P = 20; % 20 products% Production costs between 20 and 100 pcost = 80*rand(F,P) + 20; % Production capacity between 500 and 1500 for each product/factory pcap = 1000*rand(F,P) + 500; % Warehouse capacity between P*400 and P*800 for each product/warehouse wcap = P*400*rand(W,1) + P*400; % Product turnover rate between 1 and 3 for each product turn = 2*rand(1,P) + 1; % Product transport cost per distance between 5 and 10 for each product tcost = 5*rand(1,P) + 5; % Product demand by sales outlet between 200 and 500 for each% product/outlet d = 300*rand(S,P) + 200;
distfw = zeros(F,W); % Allocate matrix for factory-warehouse distancesfor ii = 1:F for jj = 1:W distfw(ii,jj) = abs(xloc(ii) - xloc(F + jj)) + abs(yloc(ii) ... - yloc(F + jj)); endend distsw = zeros(S,W); % Allocate matrix for sales outlet-warehouse distancesfor ii = 1:S for jj = 1:W distsw(ii,jj) = abs(xloc(F + W + ii) - xloc(F + jj)) ... + abs(yloc(F + W + ii) - yloc(F + jj)); endend
x = optimvar('x',P,F,W,'LowerBound',0); y = optimvar('y',S,W,'Type','integer','LowerBound',0,'UpperBound',1);
capconstr = sum(x,3) <= pcap';
demconstr = squeeze(sum(x,2)) == d'*y;
warecap = sum(diag(1./turn)*(d'*y),1) <= wcap';
salesware = sum(y,2) == ones(S,1);
factoryprob = optimproblem;
objfun1 = sum(sum(sum(x,3).*(pcost'),2),1);
objfun2 = 0; for p = 1:P objfun2 = objfun2 + tcost(p)*sum(sum(squeeze(x(p,:,:)).*distfw)); end
r = sum(distsw.*y,2); % r is a length s vector v = d*(tcost(:)); objfun3 = sum(v.*r);
factoryprob.Objective = objfun1 + objfun2 + objfun3;
factoryprob.Constraints.capconstr = capconstr; factoryprob.Constraints.demconstr = demconstr; factoryprob.Constraints.warecap = warecap; factoryprob.Constraints.salesware = salesware;
opts = optimoptions('intlinprog','Display','off','PlotFcn',@optimplotmilp);
[sol,fval,exitflag,output] = solve(factoryprob,opts);
if isempty(sol) % If the problem is infeasible or you stopped early with no solution disp('The solver did not return a solution.') return% Stop the script because there is nothing to examineend
exitflag = OptimalSolution
infeas1 = max(max(infeasibility(capconstr,sol)))
infeas2 = max(max(infeasibility(demconstr,sol)))
infeas3 = max(infeasibility(warecap,sol))
infeas4 = max(infeasibility(salesware,sol))
sol.y = round(sol.y); % get integer solutions
outlets = 2 0 3 2 2 2 3 2 3 2 1 0 0 3 4 3 2 3 2 1
figure(h); hold onfor ii = 1:S jj = find(sol.y(ii,:)); % Index of warehouse associated with ii xsales = xloc(F+W+ii); ysales = yloc(F+W+ii); xwarehouse = xloc(F+jj); ywarehouse = yloc(F+jj); if rand(1) < .5 % Draw y direction first half the time plot([xsales,xsales,xwarehouse],[ysales,ywarehouse,ywarehouse],'g--') else% Draw x direction first the rest of the time plot([xsales,xwarehouse,xwarehouse],[ysales,ysales,ywarehouse],'g--') endend hold off title('Mapping of sales outlets to warehouses')

Office Assignment Problem

You want to assign six people, Marcelo, Rakesh, Peter, Tom, Marjorie, and Mary Ann, to seven offices. Each office can have no more than one person, and each person gets exactly one office. So there will be one empty office. People can give preferences for the offices, and their preferences are considered based on their seniority. The longer they have been at the MathWorks, the higher the seniority. Some offices have windows, some do not, and one window is smaller than others. Additionally, Peter and Tom often work together, so should be in adjacent offices. Marcelo and Rakesh often work together, and should be in adjacent offices.

Office Layout

Offices 1, 2, 3, and 4 are inside offices (no windows). Offices 5, 6, and 7 have windows, but the window in office 5 is smaller than the other two. Here is how the offices are arranged.

Problem Formulation

You need to formulate the problem mathematically. Create binary variables that indicate whether a person occupies an office. The list of people's names is

Create binary variables indexed by office number and name.

Seniority

You want to weight the preferences based on seniority so that the longer you have been at MathWorks, the more your preferences count. The seniority is as follows: Mary Ann 9 years, Marjorie 10 years, Tom 5 years, Peter 3 years, Marcelo 1.5 years, and Rakesh 2 years. Create a normalized weight vector based on seniority.

People's Office Preferences

Set up a preference matrix where the rows correspond to offices and the columns correspond to people. Ask each person to give values for each office so that the sum of all their choices, i.e., their column, sums to 100. A higher number means the person prefers the office. Each person's preferences are listed in a column vector.

The ith element of a person's preference vector is how highly they value the ith office. Thus, the combined preference matrix is as follows.

Weight the preferences matrix by to scale the columns by seniority.

Objective Function

The objective is to maximize the satisfaction of the preferences weighted by seniority. This is the linear objective function .

Create an optimization problem and include the objective function.

Constraints

The first set of constraints requires that each person gets exactly one office, that is for each person, the sum of the values corresponding to that person is exactly one.

The second set of constraints are inequalities. These constraints specify that each office has no more than one person in it.

You want Tom and Peter no more than one office away from each other, and the same with Marcelo and Rakesh.

Set constraints that Tom and Peter are not more than 1 away from each other.

Now create constraints that Marcelo and Rakesh are not more than 1 away from each other.

Solve Assignment Problem

Call to solve the problem.

View the Solution -- Who Got Each Office?

Solution Quality

For this problem, the satisfaction of the preferences by seniority is maximized to the value of . = 1 tells you that converged to an optimal solution. The output structure gives information about the solution process, such as how many nodes were explored, and the gap between the lower and upper bounds in the branching calculation. In this case, no branch-and-bound nodes were generated, meaning the problem was solved without a branch-and-bound step. The gap is 0, meaning the solution is optimal, with no difference between the internally calculated lower and upper bounds on the objective function.

officelist = {'Office 1','Office 2','Office 3','Office 4','Office 5','Office 6','Office 7'}; printofficeassign(officelist)
namelist = {'Mary Ann','Marjorie','Tom','Peter','Marcelo','Rakesh'};
occupy = optimvar('occupy',namelist,officelist,...'Type','integer','LowerBound',0,'Upperbound',1);
seniority = [9 10 5 3 1.5 2]; weightvector = seniority/sum(seniority);
MaryAnn = [0, 0, 0, 0, 10, 40, 50]; Marjorie = [0, 0, 0, 0, 20, 40, 40]; Tom = [0, 0, 0, 0, 30, 40, 30]; Peter = [1, 3, 3, 3, 10, 40, 40]; Marcelo = [3, 4, 1, 2, 10, 40, 40]; Rakesh = [10, 10, 10, 10, 20, 20, 20];
prefmatrix = [MaryAnn;Marjorie;Tom;Peter;Marcelo;Rakesh];
PM = diag(weightvector) * prefmatrix;
peopleprob = optimproblem('ObjectiveSense','maximize','Objective',sum(sum(occupy.*PM)));
peopleprob.Constraints.constr1 = sum(occupy,2) == 1;
peopleprob.Constraints.constr2 = sum(occupy,1) <= 1;
peopleprob.Constraints.constrpt1 = occupy('Tom','Office 1') + sum(occupy('Peter',:)) - occupy('Peter','Office 2') <= 1; peopleprob.Constraints.constrpt2 = occupy('Tom','Office 2') + sum(occupy('Peter',:)) - occupy('Peter','Office 1') ... - occupy('Peter','Office 3') - occupy('Peter','Office 5') <= 1; peopleprob.Constraints.constrpt3 = occupy('Tom','Office 3') + sum(occupy('Peter',:)) - occupy('Peter','Office 2') ... - occupy('Peter','Office 4') - occupy('Peter','Office 6') <= 1; peopleprob.Constraints.constrpt4 = occupy('Tom','Office 4') + sum(occupy('Peter',:)) - occupy('Peter','Office 3') ... - occupy('Peter','Office 7') <= 1; peopleprob.Constraints.constrpt5 = occupy('Tom','Office 5') + sum(occupy('Peter',:)) - occupy('Peter','Office 2') ... - occupy('Peter','Office 6') <= 1; peopleprob.Constraints.constrpt6 = occupy('Tom','Office 6') + sum(occupy('Peter',:)) - occupy('Peter','Office 3') ... - occupy('Peter','Office 5') - occupy('Peter','Office 7') <= 1; peopleprob.Constraints.constrpt7 = occupy('Tom','Office 7') + sum(occupy('Peter',:)) - occupy('Peter','Office 4') ... - occupy('Peter','Office 6') <= 1;
peopleprob.Constraints.constmr1 = occupy('Marcelo','Office 1') + sum(occupy('Rakesh',:)) - occupy('Rakesh','Office 2') <= 1; peopleprob.Constraints.constmr2 = occupy('Marcelo','Office 2') + sum(occupy('Rakesh',:)) - occupy('Rakesh','Office 1') ... - occupy('Rakesh','Office 3') - occupy('Rakesh','Office 5') <= 1; peopleprob.Constraints.constmr3 = occupy('Marcelo','Office 3') + sum(occupy('Rakesh',:)) - occupy('Rakesh','Office 2') ... - occupy('Rakesh','Office 4') - occupy('Rakesh','Office 6') <= 1; peopleprob.Constraints.constmr4 = occupy('Marcelo','Office 4') + sum(occupy('Rakesh',:)) - occupy('Rakesh','Office 3') ... - occupy('Rakesh','Office 7') <= 1; peopleprob.Constraints.constmr5 = occupy('Marcelo','Office 5') + sum(occupy('Rakesh',:)) - occupy('Rakesh','Office 2') ... - occupy('Rakesh','Office 6') <= 1; peopleprob.Constraints.constmr6 = occupy('Marcelo','Office 6') + sum(occupy('Rakesh',:)) - occupy('Rakesh','Office 3') ... - occupy('Rakesh','Office 5') - occupy('Rakesh','Office 7') <= 1; peopleprob.Constraints.constmr7 = occupy('Marcelo','Office 7') + sum(occupy('Rakesh',:)) - occupy('Rakesh','Office 4') ... - occupy('Rakesh','Office 6') <= 1;
[soln,fval,exitflag,output] = solve(peopleprob);
LP: Optimal objective value is -33.836066. Optimal solution found. Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the default value).
numOffices = length(officelist); office = cell(numOffices,1); for i=1:numOffices office{i} = find(soln.occupy(:,i)); % people index in officeend whoinoffice = officelist; % allocatefor i=1:numOffices if isempty(office{i}) whoinoffice{i} = ' empty '; else whoinoffice{i} = namelist(office{i}); endend printofficeassign(whoinoffice); title('Solution of the Office Assignment Problem');
fval = 33.8361 exitflag = OptimalSolution output = struct with fields: relativegap: 0 absolutegap: 0 numfeaspoints: 1 numnodes: 0 constrviolation: 0 message: 'Optimal solution found.↵↵Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the default value).' solver: 'intlinprog'
Categories: 1

0 Replies to “Assignment Problem Integer Linear Programming Matlab”

Leave a comment

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *