Skip to main content

Available algorithm for obtaining a convex hull for 2D points

Answered

Comments

5 comments

  • Jonasz Staszek
    Community Moderator Community Moderator
    Gurobi-versary
    Thought Leader
    First Question

    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
    Jonasz

    1
  • Matthias Miltenberger
    Gurobi Staff Gurobi Staff

    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,
    Matthias

    1
  • Matthias Miltenberger
    Gurobi Staff Gurobi Staff

    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,
    Matthias

    1
  • Jonasz Staszek
    Community Moderator Community Moderator
    Gurobi-versary
    Thought Leader
    First Question

    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
    Jonasz

     

    1
  • Sanket Yenare
    First Question
    First Comment

    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

Please sign in to leave a comment.