How to construct conditional function in objective expression?

[Pang]

I want solve an integer programming problem in which the objective expression includes some conditional functions.

Explicitly, the problem is modeled as follow:

How to construct this model with python in Gurobi?

Is there any solution?

If not, is there any other tools that can handle this?

     

[Eric Berger]

According to the way you wrote the problem there is no interaction between x_i and x_j for i <> j.

So you can solve the problem for n=1 and then just use that solution for each of the i, 1 <= i <= n.

For n=1 you can solve it by hand, by breaking it into two cases. Case 1: b_1 = 10 and Case 2: b_1 <> 10.

I hope that helps.

--

---
You received this message because you are subscribed to the Google Groups "Gurobi Optimization" group.
To unsubscribe from this group and stop receiving emails from it, send an email to gurobi+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Daniel Espinoza]

Dear Pang,

As stated, your problem is unbounded (just take x_i to infinity), but I guess you do have some bounds.

The positive part is easy, just introduce 

y_i >= 0

y_i >= x_i

and substitute \phi(x_i) with y_i

now, for lambda(x,a) you have a problem; since all number operations are carried on in floating point precision, you MUST use a tolerance (epsilon) for the comparison x == a and use instead ABS(x-a) < epsilon

such an epsilon can not be smaller than the value of InfTol parameter.

the, to express lambda(x_i,a_i) you could the following:

z_i binary

z_i = 1 -> ABS(x_i - a_i ) >= epsilon

and substitute lambda(x_i,a_i) with z_i

Hope it helps,

Best

Daniel

[Pang]

Thanks for your help! As stated in the model, the decision variables (x_i) are restricted in a set ({1 ,3, 5, 7, 10})

The problem i'm facing is that such indicator functions are not supported to be appear in the objective expression in Gurobi.

Introducing binary variables to reformulate the original objective function seems like a good idea, I'm trying it.

However, in your idea, the definition of y_i and z_i seems unable to reflect the correlations of x_i and the values of phi(x_i - b_i) and lambda(x_i, a_i).

Is there any further suggestion?

在 2016年10月31日星期一 UTC+8上午12:56:31，Daniel Espinoza写道：

[Daniel Espinoza]

Dear Pang,

I missed that x_i \in {v_i1,....,v_ik}

The set is rather unusual for MIP's, but certainly not impossible.

A common general trick would be to define 

x_ij a binary variable indicating that x_i = v_ik (if one) and add a partition constraint

sum (x_ij : j=1...k) = 1

which force exactly one x_ij to be one, i.e. is equivalent to forcing x_i to take one value within the possible set.

The advantage is that now \phi(x_i-b_i) and \lambda(x_i,a_i) is really just computing \phi(v_ij-b_i) and \lambda(v_ij,a_i) for each x_ij (and so you could use even more complicated functions in the objective function

Just out of curiosity... what is this model for?

Best

Daniel

[Eric Berger]

As I wrote earlier this problem can be quite easily solved by hand in two stages.

Stage 1: consider the case n=1. Call this the 1-variable problem and let it be denoted Problem(a,b), with solution x(a,b). 

We now calculate the explicit solution for n=1, a=a_1, b=b_1, which involves two cases.

Case 1: b=10

In this case phi(x) = 0 for all x, so the objective function is determined by the lambda function which has a maximum value of 1 and which is achieved for x any value other than a. (i.e. there are 4 solutions)

Case 2: b <> 10 (b not equal to 10)

Hear we see that the phi(x) contribution will be maximal for x=10. The maximal value for the objective function is \lambda(10,a) + (10-b) which is either (10-b) if a=10 or (10-b+1) if a<>10.

Stage 2: n > 1

For n > 1 you just have a case of n independent 1-variable problems i.e. Problem(a_i,b_i) for x_i, 1 <= i <= n.

You simply solve each of these n problems for x_i as in Stage1 and then add the values of their objective functions to get the value of the objective function for the full problem.

I don't think Gurobi is needed for this optimization problem.

--