Topic
• 2 replies
• Latest Post - ‏2013-06-20T01:11:15Z by EdKlotz
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
229 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
15 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.

• DanielJunglas
229 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
15 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.