Topic
  • 2 replies
  • Latest Post - ‏2013-06-20T01:11:15Z by EdKlotz
HadiUON
HadiUON
1 Post

Pinned topic Checking feasibility of a MIP

‏2013-06-19T07:39:31Z |

Assume that we only want to prove that a problem is feasible or infeasible.

1-What is the best way of checking feasibility or infeasibility of a MIP ?

2-What does Cplex do, if we do not define objective function for our model and solve it when we write it in C++?

  • DanielJunglas
    DanielJunglas
    145 Posts
    ACCEPTED ANSWER

    Re: Checking feasibility of a MIP

    ‏2013-06-19T14:15:17Z  

    If you do not define an objective function then the objective function is constantly zero. This means that any feasible solution is optimal and CPLEX will stop immediately as soon as it finds a feasible solution.

    So if you are only after proving (in)feasibility then clearing out the objective function is usually a good idea.

    Another strategy that is sometimes helpful is to use feasopt. Once feasopt has proven that the minimal penalty to render the model feasible is larger than 0 you know that the model is infeasible.

    What works best depends on the model, but first thing I would try is clearing out the objective. If that is not fast enough then maybe crank up some of the presolve parameters, like probing.

  • EdKlotz
    EdKlotz
    13 Posts
    ACCEPTED ANSWER

    Re: Checking feasibility of a MIP

    ‏2013-06-20T01:11:15Z  

    If you do not define an objective function then the objective function is constantly zero. This means that any feasible solution is optimal and CPLEX will stop immediately as soon as it finds a feasible solution.

    So if you are only after proving (in)feasibility then clearing out the objective function is usually a good idea.

    Another strategy that is sometimes helpful is to use feasopt. Once feasopt has proven that the minimal penalty to render the model feasible is larger than 0 you know that the model is infeasible.

    What works best depends on the model, but first thing I would try is clearing out the objective. If that is not fast enough then maybe crank up some of the presolve parameters, like probing.

    Note that with feasopt, sometimes you don't even need to wait until it
    has calculated the minimal penalty.  As soon as the best node value
    for the minimal penalty exceeds 0, you know that the model is
    infeasible.  You can tell CPLEX to stop as soon as the best node is
    positive by querying the best node value in an informational callback.

    One other challenge regarding finding a feasible solution or proving
    infeasibility is that the CPLEX parameter settings most suited for
    finding feasible solutions often differ from the ones best suited for
    proving infeasibility.  Finding feasible solutions typically involves
    settings such as heavier application of heuristics and best estimate
    node selection that tend to make less progress in pruning nodes of the
    tree, which is needed to prove infeasibility.  Proving infeasibility
    typically involves settings designed to focus on moving the best node
    value, such as strong branching, aggressive application of cuts, heavy
    probing, and disabling the heuristics.  So, if you know whether you
    want to find a feasible solution or prove infeasibility, that may
    enable you to do either one faster.  If you don't know, I think a good
    compromise would be to leave heuristics enabled, crank up cuts and
    probing as Daniel mentioned (either on the zero objective version of
    the model or the original one, depending on which has fewer integer
    infeasibilities in the node relaxation solutions).  This tighter
    formulation should help with the best node, but it also may reduce the
    integer infeasibilities in the node relaxation solutions, making a
    feasible solution easier to find.  Strong branching (i.e. setting
    variableselect to 3) is a riskier proposition for finding feasibles,
    although it can help prove infeasibility.


    Note that if you decide that the model with a zeroed objective
    function is more challenging, you can also run on the regular
    objective function with a solution limit of 1.  CPLEX will either stop
    with the first solution or when it has proven
     infeasibility.


     

  • DanielJunglas
    DanielJunglas
    145 Posts

    Re: Checking feasibility of a MIP

    ‏2013-06-19T14:15:17Z  

    If you do not define an objective function then the objective function is constantly zero. This means that any feasible solution is optimal and CPLEX will stop immediately as soon as it finds a feasible solution.

    So if you are only after proving (in)feasibility then clearing out the objective function is usually a good idea.

    Another strategy that is sometimes helpful is to use feasopt. Once feasopt has proven that the minimal penalty to render the model feasible is larger than 0 you know that the model is infeasible.

    What works best depends on the model, but first thing I would try is clearing out the objective. If that is not fast enough then maybe crank up some of the presolve parameters, like probing.

  • EdKlotz
    EdKlotz
    13 Posts

    Re: Checking feasibility of a MIP

    ‏2013-06-20T01:11:15Z  

    If you do not define an objective function then the objective function is constantly zero. This means that any feasible solution is optimal and CPLEX will stop immediately as soon as it finds a feasible solution.

    So if you are only after proving (in)feasibility then clearing out the objective function is usually a good idea.

    Another strategy that is sometimes helpful is to use feasopt. Once feasopt has proven that the minimal penalty to render the model feasible is larger than 0 you know that the model is infeasible.

    What works best depends on the model, but first thing I would try is clearing out the objective. If that is not fast enough then maybe crank up some of the presolve parameters, like probing.

    Note that with feasopt, sometimes you don't even need to wait until it
    has calculated the minimal penalty.  As soon as the best node value
    for the minimal penalty exceeds 0, you know that the model is
    infeasible.  You can tell CPLEX to stop as soon as the best node is
    positive by querying the best node value in an informational callback.

    One other challenge regarding finding a feasible solution or proving
    infeasibility is that the CPLEX parameter settings most suited for
    finding feasible solutions often differ from the ones best suited for
    proving infeasibility.  Finding feasible solutions typically involves
    settings such as heavier application of heuristics and best estimate
    node selection that tend to make less progress in pruning nodes of the
    tree, which is needed to prove infeasibility.  Proving infeasibility
    typically involves settings designed to focus on moving the best node
    value, such as strong branching, aggressive application of cuts, heavy
    probing, and disabling the heuristics.  So, if you know whether you
    want to find a feasible solution or prove infeasibility, that may
    enable you to do either one faster.  If you don't know, I think a good
    compromise would be to leave heuristics enabled, crank up cuts and
    probing as Daniel mentioned (either on the zero objective version of
    the model or the original one, depending on which has fewer integer
    infeasibilities in the node relaxation solutions).  This tighter
    formulation should help with the best node, but it also may reduce the
    integer infeasibilities in the node relaxation solutions, making a
    feasible solution easier to find.  Strong branching (i.e. setting
    variableselect to 3) is a riskier proposition for finding feasibles,
    although it can help prove infeasibility.


    Note that if you decide that the model with a zeroed objective
    function is more challenging, you can also run on the regular
    objective function with a solution limit of 1.  CPLEX will either stop
    with the first solution or when it has proven
     infeasibility.