Ceiling function for objective function in MILP optimization

Hi.

I am using intlinprog to optimise a room allocation schedule for an event. My variables are all integers.

I need to minimise the cost of running this event. Cost is incurred for multiples of 28 people in a room. For example having a room with 0-28 people costs 15$, a room with 29-56 people costs 30$.

I figured I could use the a ceiling function to round up (# of people / 28) to the closest integer, but I cont find a way to incorporate this into the objective function.

Is it possible to use ceiling, or is there a workaround?

Any ideas would be appreciated.

Thanks for reading my question. M

Answer 1

[Alan Weiss]

You can use an extra variable that keeps track of the number of segments of people/28. Here's how.

Suppose that n is the number of people (this might be a sum of some other variables in your problem). Introduce a new variable y that has the following constraints:

• y is integer-valued
• 28*y >= n (you can represent this as a linear inequality constraint)
• The (linear) cost function includes y as one term

Then the minimum of the cost function will occur when y is minimized, meaning when it is as small as it can be but still above n/28. Then you can write your cost in terms of y.

Alan Weiss

MATLAB mathematical toolbox documentation

[m c]

Thank you so much that. It looks like that might be exactly what I'm looking for.

Can you help me just a little more, please?

Do I understand you correctly that n and y variables (one n and one y for each room) will have have to be added to my X vector of variables?

If yes, how do I make the various n a function of some other elements of that X variable vector?

If no, how else can I define the n? I can just define an n vector as a function of X before I run intlinprog, but how do I make sure n is updated while intlinprog is running?

I hope these questions make sense.

Thanks again for your help! M

[Alan Weiss]

As in some documentation examples, you just append the new variables (you might not need n) to your vector of control variables, usually called x. Make sure that your constraint matrices take into account the new variable. The example I linked you to has details for one particular problem.

Good luck,

Alan Weiss

MATLAB mathematical toolbox documentation

[m c]

I have been trying to work through the example, but I am still stuck on one thing.

I see now I have to append the n variables to the end of the x vector.

However, I dont know how to relate the n part of the x vector to the part of the x vector that controls room allocations. I imagine I would have to include part of the x vector in the beq vector.

How do I do this?

Thanks again M

[m c]

Never mind. I figured it out.

I just had to modify the A matrix and b vector.

And now I have my optimised schedule!

Thanks for your help.

M