Skip to main content

Crossover impact on duals in a LP

Awaiting user input

Comments

3 comments

  • Official comment
    Yuriy Zinchenko
    Gurobi Staff Gurobi Staff

    Hi Elena,

    to chirp in here, most likely your dual is what is called degenerate, that is, admits several solutions, in which case you may see some surpassing values coming up as well as should probably not focus on getting much meaning out of the duals anyways.

    Here is a simple example illustrating dramatic duals, along the sides of "normal" ones. 

    Consider a "primal" LP of the form

    max y1
      s.t.
             -y2 <= 0
               y1 + y2 <= 1
    10^-6 y1 + y2 <= 10^-6

    which can be graphed, to convince oneself that the optimal solution is (1,0) with obj value of 1.
    Note that all the three constraints are active at the optimum, i.e., met with equality. So, the model admits 
    multiple optimal basis, e.g., we can identify the solution by setting either 1st and 2nd, or 1st and 3rd constraints
    as equalities and ignoring the rest.

    Now, its corresponding dual can written as

    min x2 + 10^-6 x3
      s.t.
             x2 + 10^-6 x3 = 1
    -x1 + x2 +           x3 = 0
    x1, x2, x3 >= 0

    where two alternative optima exists, namely (1, 1, 0) and (10^6, 0, 10^6).  This is what we call degenerate dual, 
    and in this case is a direct consequence of having multiple alternative optimal basises in the primal.
     
    There is an intuitive explanation here if we recall that the dual optimal values serve as the so-called sub-gradient to the constraints, that is, they (sort of) predict how fats the optimal objective will change with the right-hand side. Here though, since there 3 inequalities that meet at a single point on a plane (for the primal), the "sub" part comes into play, that is, the dual values loose the predictive value as there is more than one solution possible.

    One should probably draw out the primal feasible region on a piece of paper to make this more evident.  One hyperplane --third inequality-- is really shallow, and thus potentially can change the objective by a lot with a minute change of its RHS, but alas, this may or may not happen after all, depending what other constraints are doing.

    Bottom line is, if there are multiple dual solutions, maybe one should not get stuck on the respective values as they may not be that meaningful anymore in a more "traditional" sense, namely, the use of such values to analyze the objective may be a wasted effort.

    Hope this is helpful.

  • Mario Ruthmair
    Gurobi Staff Gurobi Staff

    Hi Elena,

    Are you observing any numerical issues, i.e., that there are violations in the optimal solution that are larger than the tolerances (1e-6)?

    If the solution looks "clean", then you probably just observe an alternative dual optimal solution. Often, even for the same primal optimal solution there can be multiple dual optimal solutions (in case of degeneracy). Based on your experience you might say that some dual solution is "better" than another one, but from the solver point of view, all are equivalent.

    You said that changing the parameter Crossover leads to different duals. This parameter is only relevant for the barrier algorithm, not for simplex. If you are using barrier then different values for Crossover can lead to different dual optimal solutions. Which value did you use for Crossover (0-4)?

    You could post your Gurobi output to clarify a few things.

    Best regards,
    Mario

    0
  • Yuriy Zinchenko
    Gurobi Staff Gurobi Staff

    ps: with respect how the crossover comes into play, if the model is degenerate, the algorithmic path alone will determine the values here. From a user point of view this may seem like the outcome depends on a roll of a dice, while in reality you just arrive to an alternative optima.

    You should probably confirm that the values are correct, by writing out the dual, confirming the values are feasible (modulo round-off errors), etc.

    0

Please sign in to leave a comment.