We want to use the C or Python API of CPLEX to generate and record cutting planes when solving a Mixed Integer Linear Program (MILP). Our goal is to utilize CPLEX as a pure cutting plane algorithm and obtain the cuts that are added to the root node during the solving process.

Since the solving time for a MILP can sometimes be quite long, we would like to retrieve the cuts at the root node before the algorithm stops. For example, after 500 cuts have been added to the root node, we want to stop CPLEX and obtain a new model file (with .mps, .lp, or .sav extension) that contains both the original LP relaxation (the original root node) and the 500 added cuts. By solving this new model file, we hope to obtain a solution that is closer to the optimal solution of the original MILP compared to the solution obtained by solving the original LP relaxation.

Is it possible to obtain such a file? If so, how can we achieve this?

Thank you!

Hi

could https://community.ibm.com/community/user/ai-datascience/discussion/accessing-to-cuts-added-by-cplex?ReturnUrl=%2Fcommunity%2Fuser%2Fdatascience%2Fparticipate%2Fforums help ?

We want to use the C or Python API of CPLEX to generate and record cutting planes when solving a Mixed Integer Linear Program (MILP). Our goal is to utilize CPLEX as a pure cutting plane algorithm and obtain the cuts that are added to the root node during the solving process.

Since the solving time for a MILP can sometimes be quite long, we would like to retrieve the cuts at the root node before the algorithm stops. For example, after 500 cuts have been added to the root node, we want to stop CPLEX and obtain a new model file (with .mps, .lp, or .sav extension) that contains both the original LP relaxation (the original root node) and the 500 added cuts. By solving this new model file, we hope to obtain a solution that is closer to the optimal solution of the original MILP compared to the solution obtained by solving the original LP relaxation.

Is it possible to obtain such a file? If so, how can we achieve this?

Thank you!

Hi,

Thank you for sharing the information. We have reviewed the link, and actually, we obtain cuts from CPLEX using the CPXgetcallbacknodelp function (we use the code provided by IBM Support: Sample C Program to Retrieve Cuts Added by CPLEX During MIP Optimization).

However, it seems that CPLEX employs a combination of cutting planes and branch-and-bound algorithms to solve MILPs, rather than using a pure cutting plane method. As a result, the code utilizing CPXgetcallbacknodelp may yield cuts that are added to non-root nodes, especially if we terminate the algorithm before it has fully solved the MILP (since solving times can sometimes be quite long).

What we would like to achieve is the cuts that are specifically added to the root node. Is it possible to obtain these cuts?

Thank you!

Hi

could https://community.ibm.com/community/user/ai-datascience/discussion/accessing-to-cuts-added-by-cplex?ReturnUrl=%2Fcommunity%2Fuser%2Fdatascience%2Fparticipate%2Fforums help ?

We want to use the C or Python API of CPLEX to generate and record cutting planes when solving a Mixed Integer Linear Program (MILP). Our goal is to utilize CPLEX as a pure cutting plane algorithm and obtain the cuts that are added to the root node during the solving process.

Since the solving time for a MILP can sometimes be quite long, we would like to retrieve the cuts at the root node before the algorithm stops. For example, after 500 cuts have been added to the root node, we want to stop CPLEX and obtain a new model file (with .mps, .lp, or .sav extension) that contains both the original LP relaxation (the original root node) and the 500 added cuts. By solving this new model file, we hope to obtain a solution that is closer to the optimal solution of the original MILP compared to the solution obtained by solving the original LP relaxation.

Is it possible to obtain such a file? If so, how can we achieve this?

Thank you!

Hi Paul,

Many thanks for your response! The approach unfortunately doesn't quite solve the problem -- let me clarify the issue I'm having.

We have a MIP, and we want to retrieve the first (say) 100 cuts generated by a typical (pure) cutting plane algorithm. The resulting LP is still a relaxation of the MIP, but is better than just dropping the integrality constraint from the MIP.

In more detail:

1. Pure Cutting Plane Algorithm: Is it possible to configure CPLEX to operate solely as a cutting plane algorithm for solving a mixed integer linear program (MILP)? It seems that CPLEX typically employs a combination of cutting planes and branch-and-bound algorithms to solve MILPs.

2. Retrieving Cuts: If the above is indeed possible, can we obtain some cuts before the algorithm completes its solving process?

Any pointers you could give me would be greatly appreciated!

Eliza,

I'm not positive, but I do not think you can get CPLEX to use a pure cutting plane approach to solve a model to optimality (which, if I understand you correctly, is not what you really want to do). You might be able to approximate that behavior. I'll use Java parameter names in what follows, but you should have no trouble translating them to your API of choice. What you can do is the following.

• Set the MIP node limit (IloCplex.Param.MIP.Limits.Nodes) to 0, so that CPLEX does no branching.
• Set some or all of the cut parameters (too many to list here; see https://www.ibm.com/docs/en/icos/22.1.1?topic=m-mip-cuts) to aggressive levels.
• Possibly set the cut factor limit (IloCplex.Param.MIP.Limits.CutsFactor) to a large positive value.
• Set the cutting plane pass limit (IloCplex.Param.MIP.Limits.CutPasses) to a big honking integer value.
• Set the probing time limit (IloCplex.Param.MIP.Limits.ProbeTime) to zero.

Since CPLEX has approximately 10^100 parameters, I can't swear those are all the ones that should concern you, but it is a starting point.

Hi Paul,

Many thanks for your response! The approach unfortunately doesn't quite solve the problem -- let me clarify the issue I'm having.

We have a MIP, and we want to retrieve the first (say) 100 cuts generated by a typical (pure) cutting plane algorithm. The resulting LP is still a relaxation of the MIP, but is better than just dropping the integrality constraint from the MIP.

In more detail:

1. Pure Cutting Plane Algorithm: Is it possible to configure CPLEX to operate solely as a cutting plane algorithm for solving a mixed integer linear program (MILP)? It seems that CPLEX typically employs a combination of cutting planes and branch-and-bound algorithms to solve MILPs.

2. Retrieving Cuts: If the above is indeed possible, can we obtain some cuts before the algorithm completes its solving process?

Any pointers you could give me would be greatly appreciated!

Hi Paul,
Thank you for your response! Your suggestions have been very helpful, and we can now use CPLEX to solve the MILP quickly. However, it seems that the way CPLEX solves the MILP is not purely through a cutting-plane algorithm. Let me describe the new issue I'm encountering.
 
To solve a MILP, CPLEX generates a series of LP-relaxation problems and solves them one by one until it obtains an optimal solution that satisfies all integrality constraints.
 
Following your suggestions, I configured the CPLEX parameters as follows:
·      CPXPARAM_MIP_Limits_Nodes is set to: 0
·      CPXPARAM_MIP_Cuts_Gomory is set to: 2
·      CPXPARAM_MIP_Cuts_MIRCut is set to: 2
·      CPXPARAM_MIP_Cuts_Disjunctive is set to: 3
·      CPXPARAM_MIP_Limits_CutsFactor is set to: 100000.000000
·      CPXPARAM_MIP_Limits_CutPasses is set to: 100000
·      CPX_PARAM_PROBETIME is set to: 0.000000
 
We are now solving a minimization problem. Figure 1 shows the objective values of all LP-relaxation problems generated by CPLEX during the solving process. The x-axis represents the number of LP-relaxation problems solved by CPLEX, while the y-axis represents the objective value of the corresponding LP-relaxation problem. The green line represents the objective values of the LP-relaxation problems, and the blue line is the optimal objective value of the original MILP. If CPLEX were using a pure cutting-plane algorithm, the green line would be monotonically increasing and would eventually reach the blue line. However, it is unusual that the objective values of some LP relaxations (e.g., the 2nd and 3rd ones) are higher than the original MILP.
 
Considering that disjunctive cuts may function similarly to branching, I disabled the generation of disjunctive cuts:
·      CPXPARAM_MIP_Cuts_Disjunctive is set to: -1
 
Figure 2 shows the objective values of all LP-relaxation problems generated by this new setting of CPLEX during the solving process. However, the objective values of some LP relaxations are still higher than the original MILP.
 
Do you know why this phenomenon occurs? How can we configure CPLEX to work as a pure cutting-plane algorithm? Any pointers you could provide would be greatly appreciated!
 
Thank you!

Eliza,

I'm not positive, but I do not think you can get CPLEX to use a pure cutting plane approach to solve a model to optimality (which, if I understand you correctly, is not what you really want to do). You might be able to approximate that behavior. I'll use Java parameter names in what follows, but you should have no trouble translating them to your API of choice. What you can do is the following.

• Set the MIP node limit (IloCplex.Param.MIP.Limits.Nodes) to 0, so that CPLEX does no branching.
• Set some or all of the cut parameters (too many to list here; see https://www.ibm.com/docs/en/icos/22.1.1?topic=m-mip-cuts) to aggressive levels.
• Possibly set the cut factor limit (IloCplex.Param.MIP.Limits.CutsFactor) to a large positive value.
• Set the cutting plane pass limit (IloCplex.Param.MIP.Limits.CutPasses) to a big honking integer value.
• Set the probing time limit (IloCplex.Param.MIP.Limits.ProbeTime) to zero.

Since CPLEX has approximately 10^100 parameters, I can't swear those are all the ones that should concern you, but it is a starting point.

Hi Paul,

Many thanks for your response! The approach unfortunately doesn't quite solve the problem -- let me clarify the issue I'm having.

We have a MIP, and we want to retrieve the first (say) 100 cuts generated by a typical (pure) cutting plane algorithm. The resulting LP is still a relaxation of the MIP, but is better than just dropping the integrality constraint from the MIP.

In more detail:

1. Pure Cutting Plane Algorithm: Is it possible to configure CPLEX to operate solely as a cutting plane algorithm for solving a mixed integer linear program (MILP)? It seems that CPLEX typically employs a combination of cutting planes and branch-and-bound algorithms to solve MILPs.

2. Retrieving Cuts: If the above is indeed possible, can we obtain some cuts before the algorithm completes its solving process?

Any pointers you could give me would be greatly appreciated!

Eliza,

Assuming that you are retrieving the LP relaxation objective values correctly, I have no explanation for what you are seeing. I agree that the LP value should monotonically approach the IP optimum from below. If cuts were being applied cumulatively, it would be impossible for the objective value to decrease. So it appears that CPLEX is doing some trial and error cutting (adding cuts that push the objective past the optimum and then subsequently dropping them). Maybe there is another parameter that needs a nondefault setting? Unfortunately, CPLEX has way more parameters than I can keep track of.

Hi Paul,
Thank you for your response! Your suggestions have been very helpful, and we can now use CPLEX to solve the MILP quickly. However, it seems that the way CPLEX solves the MILP is not purely through a cutting-plane algorithm. Let me describe the new issue I'm encountering.
 
To solve a MILP, CPLEX generates a series of LP-relaxation problems and solves them one by one until it obtains an optimal solution that satisfies all integrality constraints.
 
Following your suggestions, I configured the CPLEX parameters as follows:
·      CPXPARAM_MIP_Limits_Nodes is set to: 0
·      CPXPARAM_MIP_Cuts_Gomory is set to: 2
·      CPXPARAM_MIP_Cuts_MIRCut is set to: 2
·      CPXPARAM_MIP_Cuts_Disjunctive is set to: 3
·      CPXPARAM_MIP_Limits_CutsFactor is set to: 100000.000000
·      CPXPARAM_MIP_Limits_CutPasses is set to: 100000
·      CPX_PARAM_PROBETIME is set to: 0.000000
 
We are now solving a minimization problem. Figure 1 shows the objective values of all LP-relaxation problems generated by CPLEX during the solving process. The x-axis represents the number of LP-relaxation problems solved by CPLEX, while the y-axis represents the objective value of the corresponding LP-relaxation problem. The green line represents the objective values of the LP-relaxation problems, and the blue line is the optimal objective value of the original MILP. If CPLEX were using a pure cutting-plane algorithm, the green line would be monotonically increasing and would eventually reach the blue line. However, it is unusual that the objective values of some LP relaxations (e.g., the 2nd and 3rd ones) are higher than the original MILP.
 
Considering that disjunctive cuts may function similarly to branching, I disabled the generation of disjunctive cuts:
·      CPXPARAM_MIP_Cuts_Disjunctive is set to: -1
 
Figure 2 shows the objective values of all LP-relaxation problems generated by this new setting of CPLEX during the solving process. However, the objective values of some LP relaxations are still higher than the original MILP.
 
Do you know why this phenomenon occurs? How can we configure CPLEX to work as a pure cutting-plane algorithm? Any pointers you could provide would be greatly appreciated!
 
Thank you!

Eliza,

I'm not positive, but I do not think you can get CPLEX to use a pure cutting plane approach to solve a model to optimality (which, if I understand you correctly, is not what you really want to do). You might be able to approximate that behavior. I'll use Java parameter names in what follows, but you should have no trouble translating them to your API of choice. What you can do is the following.

• Set the MIP node limit (IloCplex.Param.MIP.Limits.Nodes) to 0, so that CPLEX does no branching.
• Set some or all of the cut parameters (too many to list here; see https://www.ibm.com/docs/en/icos/22.1.1?topic=m-mip-cuts) to aggressive levels.
• Possibly set the cut factor limit (IloCplex.Param.MIP.Limits.CutsFactor) to a large positive value.
• Set the cutting plane pass limit (IloCplex.Param.MIP.Limits.CutPasses) to a big honking integer value.
• Set the probing time limit (IloCplex.Param.MIP.Limits.ProbeTime) to zero.

Since CPLEX has approximately 10^100 parameters, I can't swear those are all the ones that should concern you, but it is a starting point.

Hi Paul,

Many thanks for your response! The approach unfortunately doesn't quite solve the problem -- let me clarify the issue I'm having.

We have a MIP, and we want to retrieve the first (say) 100 cuts generated by a typical (pure) cutting plane algorithm. The resulting LP is still a relaxation of the MIP, but is better than just dropping the integrality constraint from the MIP.

In more detail:

1. Pure Cutting Plane Algorithm: Is it possible to configure CPLEX to operate solely as a cutting plane algorithm for solving a mixed integer linear program (MILP)? It seems that CPLEX typically employs a combination of cutting planes and branch-and-bound algorithms to solve MILPs.

2. Retrieving Cuts: If the above is indeed possible, can we obtain some cuts before the algorithm completes its solving process?

Any pointers you could give me would be greatly appreciated!

Hi Paul,

Thank you for your thoughtful response. I appreciate your insights and observations about CPLEX's behaviors.

Your explanation about the cumulative cuts and the possibility of trial-and-error cutting provides valuable context for my understanding. I will consider the potential need to adjust parameters and look into the documentation for guidance.

Thank you once again for your help!

Eliza,

Assuming that you are retrieving the LP relaxation objective values correctly, I have no explanation for what you are seeing. I agree that the LP value should monotonically approach the IP optimum from below. If cuts were being applied cumulatively, it would be impossible for the objective value to decrease. So it appears that CPLEX is doing some trial and error cutting (adding cuts that push the objective past the optimum and then subsequently dropping them). Maybe there is another parameter that needs a nondefault setting? Unfortunately, CPLEX has way more parameters than I can keep track of.

Hi Paul,
Thank you for your response! Your suggestions have been very helpful, and we can now use CPLEX to solve the MILP quickly. However, it seems that the way CPLEX solves the MILP is not purely through a cutting-plane algorithm. Let me describe the new issue I'm encountering.
 
To solve a MILP, CPLEX generates a series of LP-relaxation problems and solves them one by one until it obtains an optimal solution that satisfies all integrality constraints.
 
Following your suggestions, I configured the CPLEX parameters as follows:
·      CPXPARAM_MIP_Limits_Nodes is set to: 0
·      CPXPARAM_MIP_Cuts_Gomory is set to: 2
·      CPXPARAM_MIP_Cuts_MIRCut is set to: 2
·      CPXPARAM_MIP_Cuts_Disjunctive is set to: 3
·      CPXPARAM_MIP_Limits_CutsFactor is set to: 100000.000000
·      CPXPARAM_MIP_Limits_CutPasses is set to: 100000
·      CPX_PARAM_PROBETIME is set to: 0.000000
 
We are now solving a minimization problem. Figure 1 shows the objective values of all LP-relaxation problems generated by CPLEX during the solving process. The x-axis represents the number of LP-relaxation problems solved by CPLEX, while the y-axis represents the objective value of the corresponding LP-relaxation problem. The green line represents the objective values of the LP-relaxation problems, and the blue line is the optimal objective value of the original MILP. If CPLEX were using a pure cutting-plane algorithm, the green line would be monotonically increasing and would eventually reach the blue line. However, it is unusual that the objective values of some LP relaxations (e.g., the 2nd and 3rd ones) are higher than the original MILP.
 
Considering that disjunctive cuts may function similarly to branching, I disabled the generation of disjunctive cuts:
·      CPXPARAM_MIP_Cuts_Disjunctive is set to: -1
 
Figure 2 shows the objective values of all LP-relaxation problems generated by this new setting of CPLEX during the solving process. However, the objective values of some LP relaxations are still higher than the original MILP.
 
Do you know why this phenomenon occurs? How can we configure CPLEX to work as a pure cutting-plane algorithm? Any pointers you could provide would be greatly appreciated!
 
Thank you!

Eliza,

I'm not positive, but I do not think you can get CPLEX to use a pure cutting plane approach to solve a model to optimality (which, if I understand you correctly, is not what you really want to do). You might be able to approximate that behavior. I'll use Java parameter names in what follows, but you should have no trouble translating them to your API of choice. What you can do is the following.

• Set the MIP node limit (IloCplex.Param.MIP.Limits.Nodes) to 0, so that CPLEX does no branching.
• Set some or all of the cut parameters (too many to list here; see https://www.ibm.com/docs/en/icos/22.1.1?topic=m-mip-cuts) to aggressive levels.
• Possibly set the cut factor limit (IloCplex.Param.MIP.Limits.CutsFactor) to a large positive value.
• Set the cutting plane pass limit (IloCplex.Param.MIP.Limits.CutPasses) to a big honking integer value.
• Set the probing time limit (IloCplex.Param.MIP.Limits.ProbeTime) to zero.

Since CPLEX has approximately 10^100 parameters, I can't swear those are all the ones that should concern you, but it is a starting point.

Hi Paul,

Many thanks for your response! The approach unfortunately doesn't quite solve the problem -- let me clarify the issue I'm having.

We have a MIP, and we want to retrieve the first (say) 100 cuts generated by a typical (pure) cutting plane algorithm. The resulting LP is still a relaxation of the MIP, but is better than just dropping the integrality constraint from the MIP.

In more detail:

1. Pure Cutting Plane Algorithm: Is it possible to configure CPLEX to operate solely as a cutting plane algorithm for solving a mixed integer linear program (MILP)? It seems that CPLEX typically employs a combination of cutting planes and branch-and-bound algorithms to solve MILPs.

2. Retrieving Cuts: If the above is indeed possible, can we obtain some cuts before the algorithm completes its solving process?

Any pointers you could give me would be greatly appreciated!

While I agree that it could be very difficult to make CPLEX  solve an instance of a model only by cutting planes and retrieve them all, there are a few other attempts to be done. 

Note: I don't know how CPLEX works actually under the cover. Anyway, you should also look at heuristics: at node 0 (and sometimes at any node) CPLEX will run heuristics (implying B&B) which could find solutions. There are parameters to avoid them. I would add at least CPXPARAM_MIP_Strategy_HeuristicEffort=0, which should avoid the usage of heuristics even at node 0.

------------------------------
Stefano Gliozzi

Original Message:
Sent: Sun September 29, 2024 10:16 AM
From: Eliza Hu
Subject: Use CPLEX to generate and record cutting planes

Hi Paul,

Thank you for your thoughtful response. I appreciate your insights and observations about CPLEX's behaviors.

Your explanation about the cumulative cuts and the possibility of trial-and-error cutting provides valuable context for my understanding. I will consider the potential need to adjust parameters and look into the documentation for guidance.

Thank you once again for your help!

------------------------------
Eliza Hu

Original Message:
Sent: Fri September 27, 2024 03:40 PM
From: Paul Rubin
Subject: Use CPLEX to generate and record cutting planes

Eliza,

Assuming that you are retrieving the LP relaxation objective values correctly, I have no explanation for what you are seeing. I agree that the LP value should monotonically approach the IP optimum from below. If cuts were being applied cumulatively, it would be impossible for the objective value to decrease. So it appears that CPLEX is doing some trial and error cutting (adding cuts that push the objective past the optimum and then subsequently dropping them). Maybe there is another parameter that needs a nondefault setting? Unfortunately, CPLEX has way more parameters than I can keep track of.

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University

Original Message:
Sent: Fri September 27, 2024 11:12 AM
From: Eliza Hu
Subject: Use CPLEX to generate and record cutting planes

Hi Paul,
Thank you for your response! Your suggestions have been very helpful, and we can now use CPLEX to solve the MILP quickly. However, it seems that the way CPLEX solves the MILP is not purely through a cutting-plane algorithm. Let me describe the new issue I'm encountering.
 
To solve a MILP, CPLEX generates a series of LP-relaxation problems and solves them one by one until it obtains an optimal solution that satisfies all integrality constraints.
 
Following your suggestions, I configured the CPLEX parameters as follows:
·      CPXPARAM_MIP_Limits_Nodes is set to: 0
·      CPXPARAM_MIP_Cuts_Gomory is set to: 2
·      CPXPARAM_MIP_Cuts_MIRCut is set to: 2
·      CPXPARAM_MIP_Cuts_Disjunctive is set to: 3
·      CPXPARAM_MIP_Limits_CutsFactor is set to: 100000.000000
·      CPXPARAM_MIP_Limits_CutPasses is set to: 100000
·      CPX_PARAM_PROBETIME is set to: 0.000000
 
We are now solving a minimization problem. Figure 1 shows the objective values of all LP-relaxation problems generated by CPLEX during the solving process. The x-axis represents the number of LP-relaxation problems solved by CPLEX, while the y-axis represents the objective value of the corresponding LP-relaxation problem. The green line represents the objective values of the LP-relaxation problems, and the blue line is the optimal objective value of the original MILP. If CPLEX were using a pure cutting-plane algorithm, the green line would be monotonically increasing and would eventually reach the blue line. However, it is unusual that the objective values of some LP relaxations (e.g., the 2nd and 3rd ones) are higher than the original MILP.
 
Considering that disjunctive cuts may function similarly to branching, I disabled the generation of disjunctive cuts:
·      CPXPARAM_MIP_Cuts_Disjunctive is set to: -1
 
Figure 2 shows the objective values of all LP-relaxation problems generated by this new setting of CPLEX during the solving process. However, the objective values of some LP relaxations are still higher than the original MILP.
 
Do you know why this phenomenon occurs? How can we configure CPLEX to work as a pure cutting-plane algorithm? Any pointers you could provide would be greatly appreciated!
 
Thank you!

------------------------------
Eliza Hu

Original Message:
Sent: Tue September 10, 2024 12:30 PM
From: Paul Rubin
Subject: Use CPLEX to generate and record cutting planes

Eliza,

I'm not positive, but I do not think you can get CPLEX to use a pure cutting plane approach to solve a model to optimality (which, if I understand you correctly, is not what you really want to do). You might be able to approximate that behavior. I'll use Java parameter names in what follows, but you should have no trouble translating them to your API of choice. What you can do is the following.

• Set the MIP node limit (IloCplex.Param.MIP.Limits.Nodes) to 0, so that CPLEX does no branching.
• Set some or all of the cut parameters (too many to list here; see https://www.ibm.com/docs/en/icos/22.1.1?topic=m-mip-cuts) to aggressive levels.
• Possibly set the cut factor limit (IloCplex.Param.MIP.Limits.CutsFactor) to a large positive value.
• Set the cutting plane pass limit (IloCplex.Param.MIP.Limits.CutPasses) to a big honking integer value.
• Set the probing time limit (IloCplex.Param.MIP.Limits.ProbeTime) to zero.

Since CPLEX has approximately 10^100 parameters, I can't swear those are all the ones that should concern you, but it is a starting point.

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University

Original Message:
Sent: Tue September 10, 2024 12:53 AM
From: Eliza Hu
Subject: Use CPLEX to generate and record cutting planes

Hi Paul,

Many thanks for your response! The approach unfortunately doesn't quite solve the problem -- let me clarify the issue I'm having.

We have a MIP, and we want to retrieve the first (say) 100 cuts generated by a typical (pure) cutting plane algorithm. The resulting LP is still a relaxation of the MIP, but is better than just dropping the integrality constraint from the MIP.

In more detail:

1. Pure Cutting Plane Algorithm: Is it possible to configure CPLEX to operate solely as a cutting plane algorithm for solving a mixed integer linear program (MILP)? It seems that CPLEX typically employs a combination of cutting planes and branch-and-bound algorithms to solve MILPs.

2. Retrieving Cuts: If the above is indeed possible, can we obtain some cuts before the algorithm completes its solving process?

Any pointers you could give me would be greatly appreciated!

Hi Stefano,

Thank you for your helpful response! Your suggestion worked perfectly. By setting CPXPARAM_MIP_Strategy_HeuristicEffort = 0, we can now use CPLEX as a pure cutting-plane algorithm to solve MILPs.

For reference, I have attached a new figure showing the objective values of all LP-relaxation problems generated by CPLEX during the solving process. As described in my previous reply, the green line represents the objective values of the LP-relaxation problems, while the blue line denotes the optimal objective value of the original MILP. The green line is now monotonically increasing and eventually reaches the blue line, suggesting that CPLEX is effectively utilizing a pure cutting-plane algorithm.

Thank you once again for your help!

------------------------------
Eliza Hu

Original Message:
Sent: Tue October 01, 2024 03:56 AM
From: Stefano Gliozzi
Subject: Use CPLEX to generate and record cutting planes

While I agree that it could be very difficult to make CPLEX  solve an instance of a model only by cutting planes and retrieve them all, there are a few other attempts to be done. 

Note: I don't know how CPLEX works actually under the cover. Anyway, you should also look at heuristics: at node 0 (and sometimes at any node) CPLEX will run heuristics (implying B&B) which could find solutions. There are parameters to avoid them. I would add at least CPXPARAM_MIP_Strategy_HeuristicEffort=0, which should avoid the usage of heuristics even at node 0.

------------------------------
Stefano Gliozzi

Original Message:
Sent: Sun September 29, 2024 10:16 AM
From: Eliza Hu
Subject: Use CPLEX to generate and record cutting planes

Hi Paul,

Thank you for your thoughtful response. I appreciate your insights and observations about CPLEX's behaviors.

Your explanation about the cumulative cuts and the possibility of trial-and-error cutting provides valuable context for my understanding. I will consider the potential need to adjust parameters and look into the documentation for guidance.

Thank you once again for your help!

------------------------------
Eliza Hu

Original Message:
Sent: Fri September 27, 2024 03:40 PM
From: Paul Rubin
Subject: Use CPLEX to generate and record cutting planes

Eliza,

Assuming that you are retrieving the LP relaxation objective values correctly, I have no explanation for what you are seeing. I agree that the LP value should monotonically approach the IP optimum from below. If cuts were being applied cumulatively, it would be impossible for the objective value to decrease. So it appears that CPLEX is doing some trial and error cutting (adding cuts that push the objective past the optimum and then subsequently dropping them). Maybe there is another parameter that needs a nondefault setting? Unfortunately, CPLEX has way more parameters than I can keep track of.

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University

Original Message:
Sent: Fri September 27, 2024 11:12 AM
From: Eliza Hu
Subject: Use CPLEX to generate and record cutting planes

Hi Paul,
Thank you for your response! Your suggestions have been very helpful, and we can now use CPLEX to solve the MILP quickly. However, it seems that the way CPLEX solves the MILP is not purely through a cutting-plane algorithm. Let me describe the new issue I'm encountering.
 
To solve a MILP, CPLEX generates a series of LP-relaxation problems and solves them one by one until it obtains an optimal solution that satisfies all integrality constraints.
 
Following your suggestions, I configured the CPLEX parameters as follows:
·      CPXPARAM_MIP_Limits_Nodes is set to: 0
·      CPXPARAM_MIP_Cuts_Gomory is set to: 2
·      CPXPARAM_MIP_Cuts_MIRCut is set to: 2
·      CPXPARAM_MIP_Cuts_Disjunctive is set to: 3
·      CPXPARAM_MIP_Limits_CutsFactor is set to: 100000.000000
·      CPXPARAM_MIP_Limits_CutPasses is set to: 100000
·      CPX_PARAM_PROBETIME is set to: 0.000000
 
We are now solving a minimization problem. Figure 1 shows the objective values of all LP-relaxation problems generated by CPLEX during the solving process. The x-axis represents the number of LP-relaxation problems solved by CPLEX, while the y-axis represents the objective value of the corresponding LP-relaxation problem. The green line represents the objective values of the LP-relaxation problems, and the blue line is the optimal objective value of the original MILP. If CPLEX were using a pure cutting-plane algorithm, the green line would be monotonically increasing and would eventually reach the blue line. However, it is unusual that the objective values of some LP relaxations (e.g., the 2nd and 3rd ones) are higher than the original MILP.
 
Considering that disjunctive cuts may function similarly to branching, I disabled the generation of disjunctive cuts:
·      CPXPARAM_MIP_Cuts_Disjunctive is set to: -1
 
Figure 2 shows the objective values of all LP-relaxation problems generated by this new setting of CPLEX during the solving process. However, the objective values of some LP relaxations are still higher than the original MILP.
 
Do you know why this phenomenon occurs? How can we configure CPLEX to work as a pure cutting-plane algorithm? Any pointers you could provide would be greatly appreciated!
 
Thank you!

------------------------------
Eliza Hu

Original Message:
Sent: Tue September 10, 2024 12:30 PM
From: Paul Rubin
Subject: Use CPLEX to generate and record cutting planes

Eliza,

I'm not positive, but I do not think you can get CPLEX to use a pure cutting plane approach to solve a model to optimality (which, if I understand you correctly, is not what you really want to do). You might be able to approximate that behavior. I'll use Java parameter names in what follows, but you should have no trouble translating them to your API of choice. What you can do is the following.

• Set the MIP node limit (IloCplex.Param.MIP.Limits.Nodes) to 0, so that CPLEX does no branching.
• Set some or all of the cut parameters (too many to list here; see https://www.ibm.com/docs/en/icos/22.1.1?topic=m-mip-cuts) to aggressive levels.
• Possibly set the cut factor limit (IloCplex.Param.MIP.Limits.CutsFactor) to a large positive value.
• Set the cutting plane pass limit (IloCplex.Param.MIP.Limits.CutPasses) to a big honking integer value.
• Set the probing time limit (IloCplex.Param.MIP.Limits.ProbeTime) to zero.

Since CPLEX has approximately 10^100 parameters, I can't swear those are all the ones that should concern you, but it is a starting point.

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University

Original Message:
Sent: Tue September 10, 2024 12:53 AM
From: Eliza Hu
Subject: Use CPLEX to generate and record cutting planes

Hi Paul,

Many thanks for your response! The approach unfortunately doesn't quite solve the problem -- let me clarify the issue I'm having.

We have a MIP, and we want to retrieve the first (say) 100 cuts generated by a typical (pure) cutting plane algorithm. The resulting LP is still a relaxation of the MIP, but is better than just dropping the integrality constraint from the MIP.

In more detail:

1. Pure Cutting Plane Algorithm: Is it possible to configure CPLEX to operate solely as a cutting plane algorithm for solving a mixed integer linear program (MILP)? It seems that CPLEX typically employs a combination of cutting planes and branch-and-bound algorithms to solve MILPs.

2. Retrieving Cuts: If the above is indeed possible, can we obtain some cuts before the algorithm completes its solving process?

Any pointers you could give me would be greatly appreciated!