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

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.

Answer 1

[Matt J]

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

[etudiant_is]

This is not exactly what I want to do. I edited my question to try to explain better.

[Matt J]

I don't understand the new description but my original point is still relevant. You are not minimizing a smooth continuous function. You have a discrete problem. So, fmincon is the wrong tool.

You should edit your question further to explain what constraints you have. If there aren't any, and you already have a table of "possible" costs per employee/room, why can't you minimize for each employee independently? Why not just lookup each employee's minimum cost in the table?

[Alan Weiss]

It sounds like the office assignment example is relevant. As Matt J suggests, the solution technique is integer linear programming.

Alan Weiss

MATLAB mathematical toolbox documentation

[etudiant_is]

I added the constraints. I can't solve the problems from each employee's side because their choices impact each other.

[Matt J]

the cost for each employee picking an office depends partially of the numbers of other employees who picked the same office.

Based on that, it appears that the cost function is non-linear. You will therefore have to use ga() as discussed here. Other than that, though, you would still set up the problem as I said, with binary decision variables X(i,j) to represent the room assignments and constraint matrices defined as I proposed to express any linear constraints.