Solve time issues with solution overlap parameter

Answered

Comments

5 comments

  • Jakob Schelbert

    Hi Curt,

    If I understand "cosmetic variations" correctly I'd have a look at symmetry breaking constraints. Maybe this helps you to get solutions that are really different from a functional point of view.

    I also noticed that you start with integer variables but gurobi is able to convert almost all of them to binary ones. Maybe you can have a look at your model and check if you can reformulate it a bit using only binary variables.

    How do you model the variety of the solution using the parameter k? I could think of some ways but it would be nice to hear your approach.

    0
    Comment actions Permalink
  • Daniel Espinoza

    Hi Curt,

     

    One question, I guess that the constraints that you are adding are of the form:

    sum(|x_i-x'_i| : i in important set) >= k

    where x_i are binary? or are you dealing with integer variables as well? The short snippet of log you share don't point to obviously large coefficients either... but it could be that you have a lot of epsilon-similar coefficients? Now, if you are forbidding previous solutions, then warm-start has very little chance of helping (as the previous solution would be infeasible by design), now, if you do have a feasible solution for each successive iteration, that should help

     

    Let me know if this helps

    0
    Comment actions Permalink
  • C W

    Hey Daniel,

    Yes, your assessment that the x_i variables are binary is correct and no I'm not dealing with integer variables at all.

    I'm not quite sure what epsilon similar coefficients are - can you explain? I could actually post the MIP if that would help - should I do that? If epsilon similar means the coefficients pertaining to the x_i's are similar below some epsilon, I would say that the coefficients range from 6-12 with indeed some of the coefficients being very close (e.g. maybe 9.5 and 9.6).

    Unfortunately, I don't have a feasible solution to aid with warm start, only the prior and now invalid solution.

    What type of Gurobi parameters would you suggest tuning in this scenario, if any?

    Thanks,
    Curt

    0
    Comment actions Permalink
  • Jakob Schelbert

    Hi Curt,

    If I'm not mistaken, you could use a partial (old) solution and try to feed it to gurobi as a start solution. Maybe your knowledge can help you to decide which variables should be the same as in the old solution and which ones you set to undefined. If this is not possible maybe just randomized selection of variables might sill be possible.

    A concrete example is always beneficial, so if you can post an example here, it would be great.

    A difference of 0.1 should pose no problem. Note that relative numbers are more relevant for tolerances than absolute ones.

    0
    Comment actions Permalink
  • Daniel Espinoza

    Hi Curt,

     

    What I mean is that you can have constraints like

    x1 + x2 <= 1

    1.00001x1 + 0.99999x2 >= 1.00001

    which by themselves are fine.... but where they induce a very thin feasible region (and a large condition number for the system of equations). Now, if you are talking 9.5 and 9.6 as coefficients for same variables.... that shouldn't be too bad. As Jacob also suggested, giving some incomplete mip-starts and/or a trivially valid (but never optimal) solution to start with should also help. Finally, for tuning, there is the tuning tool grbtune still, please spend some time reading the guide about tuning.

     

    Daniel

    0
    Comment actions Permalink

Please sign in to leave a comment.

Powered by Zendesk