Topic
4 replies Latest Post - ‏2012-12-13T14:38:07Z by SystemAdmin
CPXfanatic
CPXfanatic
20 Posts
ACCEPTED ANSWER

Pinned topic About the usage of the conflict refiner

‏2012-11-15T17:05:59Z |
Hi,

I'm using the conflict refiner with a small MIP model and I noticed that the time elapsed to solve the model is quite fewer than the time spent by the conflict refiner. For instance, the MIP optimization takes 0.01 seconds but the conflict refiner may take 15-20 seconds. Since I run this model over and over (thousands of times), I wish to know a brief of what the conflict refiner does and whether this discrepancy in the time is normal.

I also wonder if someone could tell me a web link or a paper that describes it a bit deeper.

Thanks in advance!
Daniel.
Updated on 2012-12-13T14:38:07Z at 2012-12-13T14:38:07Z by SystemAdmin
  • SystemAdmin
    SystemAdmin
    7929 Posts
    ACCEPTED ANSWER

    Re: About the usage of the conflict refiner

    ‏2012-11-15T23:28:45Z  in response to CPXfanatic
    I take it the MIP is infeasible? The conflict refiner looks for a minimal set of constraints, bounds and integrality conditions that are mutually inconsistent. Minimality implies that deleting any of those restrictions means that the subset of constraints/bounds/integer restrictions becomes feasible (although the overall model may remain infeasible). Winnowing the entire model down to an irreducible conflict is where the extra time is burned. This is entirely normal.

    Paul

    Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
    • SystemAdmin
      SystemAdmin
      7929 Posts
      ACCEPTED ANSWER

      Re: About the usage of the conflict refiner

      ‏2012-12-13T14:38:07Z  in response to SystemAdmin
      Hi Friend,
      According to your response, we see clearly that there is no difference between the output and the conflict refiner output IIS finder. Normally and from what I've read the documentation CPLEX, the output of IIS finder is an irreducible inconsistent set so that the output of Conflict refiner is not necessarily an IIS (irreducible inconsistent set), the heuristic behind Conflict refiner "black box CPLEX" find the minimal inconsistent set of constraints (th set is not necessarily irreducible).
      Thank you :)
  • SystemAdmin
    SystemAdmin
    7929 Posts
    ACCEPTED ANSWER

    Re: About the usage of the conflict refiner

    ‏2012-11-16T17:00:04Z  in response to CPXfanatic
    The conflict refiner algorithm is basically a version of QuickXPlain by Ulrich Junker (2004).

    Tobias