Piecewise linear approximation using separable programming and SOS2 sets

[dips]

Dear All,
It would be my pleasure if anyone addresses my following queries regarding piecewise linear optimization. I am solving one non linear non convex optimization problem using linear programming separable method and SOS2 set by MATLAB GUROBI interface. My queries,
1) Is GUROBI uses Modified simplex method to solve separable programming problem or something else?
2) Does solution to such kind of piecewise linear problem using gurobi matlab interface gives approximation of global minimum? or it simply leads to approximated local minimum?
3) What strategies are used to solve such problems ? Branch and bound or branch and pruning or something else?
Thanks and regards.
 

[Renan Garcia]

Gurobi provides a 'pwlobj' field in the Matlab interface (see http://www.gurobi.com/documentation/6.0/reference-manual/matlab_gurobi) for specifying piecewise-linear objective functions, each defined for a single variable (i.e., separable). When using this interface, Gurobi will solve the model using modified simplex only if the piecewise-linear functions are all convex. Otherwise, branch-and-bound would be used to solve the problem in the non-convex case, and assuming you let the algorithm solve to optimality (i.e., no restrictive termination criteria), it would find the global minimum to the piecewise-linear model.

Renan

--

---
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+un...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Dipesh Makwana]

Thank you Renan.

Just to make it more clear,  I am not using 'pwlobj' of Gurobi , as with this field I can only solved separable problem in which only objective function is piecewise linear. But in my case, I have a linear objective function of minimizing only one variable, while my all constraints are non linear non convex in nature and i have made them peicewise linear with sos2 facility using Gurobi 5.6 v. So in this case also, should I assume that the branch and bound algorithm is used by gurobi and I am getting approximation to the piecewise linear model?

Thanks

--

Thanks and regards,

Dipesh Makwana,
Associate Professor,

G.E.S Class - I,
Vishwakarma Government Engineering College,
Chankheda,
Ahmedabad,
Gujarat, India

Alternately :
Research Scholar (PhD),
Systems and Control Engineering Department,
Indian Institute of Technology-Bombay,
Powai, Mumbai,
Maharashtra, India

[Renan Garcia]

Thanks for the clarification. You are correct, the piecewise-linear API is only for the objective function. In your case, the SOS2 constraints transform the model into a MIP, and branch-and-bound will be used to solve it. However, it is still the case that if you let the algorithm solve to optimality (i.e., no restrictive termination criteria such as time limit), it will find the globally optimal solution (i.e., not a local minimum) to the piecewise-linear model.

[Dipesh Makwana]

Thank you very much Renan. Now, I am clear about my model and its feasible solution. I would like to convey my very sincere thanks to GUROBI team and its academic free license policy, as  I have obtained very challenging results using separable programming concepts and Matlab-Gurobi interface.

Regards.

[dips]

Dear Renan,

I have successfully solved piecewise linear optimization problem for non linear non convex objective and constraint functions using sos2 variables.In response to my last queries, you said that the SOS2 constraints transform the model into a MIP, and branch-and-bound will be used to solve it. Would you please explain with examples or give one example that how GUROBI solves piecewsie linear model (built with sos2)  with MIP and Branch and bound. I need  it to explain it in my thesis that how I have solved my approximating LP problem with gurobi.  

Thanks Regards.

[Tobias Achterberg]

SOS2 constraints will not be part of the LP relaxation, but dealt with by branching.

Consider an SOS2 constraint (x1,...,xk) and assume that in the LP relaxation we
have at least two non-adjacent xj variables with non-zero value. Then, Gurobi
will select a break-point p of this SOS2 constraint (which is somewhere between
the two non-adjacent non-zero variables) and branch by creating two child nodes:
in the left child it will set x1 = ... = x[p-1] = 0, and in the right child it
will set x[p+1] = ... = xk = 0.

This is a valid branching split, because if any of the variables left of p is
non-zero then all variables right of p have to be zero, due to the SOS2
property, and vice versa. It also cuts off the current LP solution.

But note that if there are other branching possibilities (i.e., integer variable
with fractional LP value) then Gurobi would often first branch on an integer
variable before dealing with the SOS2 constraints.


Best regards,

Tobias