office assignments by binary integer programming: problem-凯发k8网页登录

this example shows how to solve an assignment problem by binary integer programming using the optimization problem approach. for the solver-based approach, see .

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 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.

officelist = {'office 1','office 2','office 3','office 4','office 5','office 6','office 7'};
printofficeassign(officelist)

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

namelist = {'mary ann','marjorie','tom','peter','marcelo','rakesh'};

create binary variables indexed by office number and name.

occupy = optimvar('occupy',namelist,officelist,...
    'type','integer','lowerbound',0,'upperbound',1);

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.

seniority = [9 10 5 3 1.5 2];
weightvector = seniority/sum(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.

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];

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.

prefmatrix = [maryann;marjorie;tom;peter;marcelo;rakesh];

weight the preferences matrix by weightvector to scale the columns by seniority.

pm = diag(weightvector) * prefmatrix;

objective function

the objective is to maximize the satisfaction of the preferences weighted by seniority. this is the linear objective function sum(sum(occupy.*pm)).

create an optimization problem and include the objective function.

peopleprob = optimproblem('objectivesense','maximize','objective',sum(sum(occupy.*pm)));

constraints

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

peopleprob.constraints.constr1 = sum(occupy,2) == 1;

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

peopleprob.constraints.constr2 = sum(occupy,1) <= 1;

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.

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;

now create constraints that marcelo and rakesh are not more than 1 away from each other.

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;

solve assignment problem

call solve to solve the problem.

[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).

view the solution -- who got each office?

numoffices = length(officelist);
office = cell(numoffices,1);
for i=1:numoffices
    office{i} = find(soln.occupy(:,i)); % people index in office
end
whoinoffice = officelist; % allocate
for i=1:numoffices
    if isempty(office{i})
        whoinoffice{i} = ' empty  ';
    else
        whoinoffice{i} = namelist(office{i});
    end
end
printofficeassign(whoinoffice);
title('solution of the office assignment problem');

solution quality

for this problem, the satisfaction of the preferences by seniority is maximized to the value of fval. the value of exitflag indicates that solve 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 absolute gap is 0, meaning the solution is optimal, with no difference between the internally calculated lower and upper bounds on the objective function.

fval,exitflag,output

fval = 33.8361

exitflag = 1

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'