Available algorithm for obtaining a convex hull for 2D points
Answered
Hi,
I am going to start with GUROBI optimization and I am a beginner in optimization as well. I am looking for any Constraint programming model that can give me a convex hull for a given list of 2D points ?
The list of points [xi, yi] are decision variables and I want the algorithm to be in a purely Constraint programming format, not in Linear programming as I am dealing with only integers. I cannot use floating point values even for obtaining the convex hull.
Is this even possible in a Constraint program? Any materials you could advice me to read? Any posts related to that?
I am considering moving to GUROBI from another operations research library because GUROBI provides a lot of additional functions and the support I staff is very helpful it seems
thanks in advance :)
-
Dear Sanket,
you should turn to some other software package, e.g. Porta or Polymake to perform polyhedral analysis (i.e. to get a description of the convex hull you look for)
As far as I know the topic of polyhedral combinatorics is studied best for linear problems. But if anyone (perhaps also from Gurobi team) is aware of any works on the crossroads of constraint programming and polyhedral combinatorics, I would also like to learn about them!
Best regards
Jonasz1 -
I don't have much to add to Jonasz' comment. His suggested tools are way more specialized for this purpose and should be much easier to use to solve that problem.
Cheers,
Matthias1 -
Thanks Jonasz Staszek and Matthias Miltenberger for responding,
I looked into Porta and Polymake, the thing is I have a model in which one of the parts is for polyhedral analysis, and the rest of the parts are other constraints and inequalities. So my question is, even though if Porta or Polymake helps me with polyhedral analysis, can I incorporate that into my constraint model? Like having the polyhedral analysis as constraints some how using Porta or Polymake? I hope you are getting what I am saying.
I have no such experience with the above-mentioned tool but is there any way for example to include porta methods for Gurobi decision variables? No right? I just want to confirm this.
best,
Sanket :)
0 -
Hi Sanket,
The only way I can think of to incorporate the results from tools like Porta or Polymake into Gurobi is via callbacks. But I don't think this is going to help you much because you only have limited control in those callbacks, and the main model will have to remain constant.
Best regards,
Matthias1 -
Hi Sanket,
Generally speaking, Porta and Polymake can guide you towards finding strong, potentially facet-defining inequalities for your problem.
The best way you could benefit from using Porta or Polymake is to study the structure of the convex hull of your problem and see if you can generate the inequalities which they give you yourself. If yes, you could then either reformulate your problem to exploit them, or perhaps find a way to generate them in a callback.
Practically, I can't imagine one could use Porta or Polymake directly in a callback, as these tools actually need to enumerate the convex hull of your problems, and experience shows this can be done in an acceptable time for problems with up to 20-25 variables.
So unless your problem is exceptionally small, you are better off generating a tiny instance, which captures the most important characteristics of your problem, and then playing with Porta or Polymake to learn as much as possible about the polyhedral structure. I should also add that such experiments are a kind of an art in their own sense, so you shouldn't get discouraged by early failures.
Hope this helps.
Best regards
Jonasz1
Please sign in to leave a comment.
Comments
5 comments