Wednesday, April 29, 2009

Ceiling in OML

Hello, I have to deal with an objective function of the following form: min [C1 * ceiling (X/m) plus C2 * (X-ceiling(X/m))];
where C1, C2, m are parameters and X is the decision variable. Ceiling is a mathematical operator that rounds a number up, to the nearest integer (see Excel's definition).
My first question is: is the Ceiling operator defined in OML?
My second question: is there a solver within the Microsoft Solver Foundation that can handle this type of objective function?
Thank you.

I believe you can do the following in OML:

Let Y be an integer variable with the constraint

X/m ≤ Y ≤ 1+X/m

then minimize

C1 * Y + C2 * (X-Y)

Hopefully the rest of the model is linear. In that case this is a much better formulation as it gets rid of a non-smooth function: solvers often have troubles with that.

See also http://yetanothermathprogrammingconsultant.blogspot.com/2009/02/floor-in-minlp-model.html and http://yetanothermathprogrammingconsultant.blogspot.com/2008/08/gams-documentation-endogenous-floor.html.

8 comments:

  1. What if i need to minimize the following function using MS Excel:
    c1*ceiling(x1) + c2*ceiling(x2) + ..

    When I gave the the above constraints i.e.,
    x1<=y1<=1+x1 and x2<=y2<=1+x2
    i am getting the results as y1=x1 and y2=x2

    Can you please help me on this?

    ReplyDelete
  2. You probably forgot the integrality conditions.

    ReplyDelete
  3. no.. i gave the constraints that i have mentioned. is there anything else that i shud give?

    ReplyDelete
  4. I added the cells y1, y2.. as adjustable cells along with the cell which has the value of c1*ceiling(x1) + c2*ceiling(x2) + ..
    and finally set the solver to minimize the selected cells. Thus i got the values of y1,y2.. equal to x1,x2.. (minimum values). What should be done?

    ReplyDelete
  5. x y 1+x
    ___________________________

    1.1 2.1
    2.7 3.7
    mincost=sum(all rows in y)

    in the solver: adjustable cell: all rows in y and mincost cell
    i have set it to minimization (as i want to minimize the mincost cell value)
    [Note: part of the problem is alone explained here]
    I know I am wrong by giving minimization constraint to cells of column y. what can be done to find the ceiling value?

    ReplyDelete
  6. *formatting is poor :)
    three columns: x,y and 1+x
    the values 1.1 and 2.7 are in column x.
    column y is empty (i have set it to adjustable cells)
    column 1+x has 2.1 and 3.7

    ReplyDelete
  7. You probably forgot the integrality conditions: Y should be restricted to allow integer values only.

    ReplyDelete