MATLAB: What to use for customized minimization of the sum of a function

fmincon minimize

Assuming I have a set of employees (ex: 5) to assign to a set of offices (ex: 3).(This is not my real problem but I simplified it to understand the concept then apply it to my problem)
What I want at the end is to have a matrix of this kind
Assignment =[1 2
             3 0
             4 5]
The rows correspond to the offices. In each row, I have the employees assigned to each office. I made the computation of the costs for each employee and I want to minimize the TotalCost which is like the sum of all the employees costs
minimize TotalCost=sum(Costs)
I have written a function to get me a starting feasible assignment
Assignment0=[1 2
             0 0
             3 4 5]
and I want to get as result the assignment with the minimum TotalCost. I have a constraint on the offices (each office has a limited capacity so it can't have more employee assigned to it than this capacity) Besides, the cost for each employee picking an office depends partially of the numbers of other employees who picked the same office.
I have other another constraint on which office an employee can choose (each employee can not necessarily pick anyone of all offices).
What I did is that for unauthorized offices (which an employee can't have), I did put a big value=Inf so that such office is not picked.
So what should I use to get Assignment as result which minimizes the FinalCost
I am actually trying to implement an algorithm which looks like this to solve the problem
  1. Get a starting feasible assignment
  2. Compute the CurrentCost for each employee (with the selected office)
  3. Compute the possible costs for each employee(if he changes his office)
  4. Get the minimum possible cost (MinPossibleCost=min(PossibleCosts)) for each employee
  5. FinalCost=CurrentCost-MinPossibleCost
  6. Minimize sum(FinalCost)
I computed the matrices/vectors for all lines from 1 to 5 What I am stuck at is what to use to solve the last line and get the assignment.

Best Answer

This sounds like a linear integer programming problem and therefore intlinprog is the appropriate tool here, not fmincon.
I would set it up like this. Let X be a 3x5 matrix of binary variables such that X(i,j)=1 means you assign employee j to room i. Let f(i,j) be the cost of doing so. You want to choose X to minimize the linear objective f(:).'*X(:) subject to certain constraints. For example, one constraint is obviously that an employee is not assigned to multiple rooms, so sum(X,1)<=1. This constraint can be put in the matrix-vector form A*X(:)<=1 required by intlinprog by constructing A as
     A=kron(eye(5),ones(1,3))
Related Question