Decision Optimization

Hello all,

I've got a question with regard to the Infeasibility/Unboundedness status of my model.

I'm implementing a Benders decomposition in which I have a master problem and a sub problem. Once the subproblem is solved by CPLEX, the infeasible status is announced by CPLEX. However, based on my understanding, the subproblem should be feasible unbounded. This is because I know a feasible solution that always satisfies all the constraints. Also, when I limit the bounds of a given variable (limiting it to be within (0,1) as opposed to (0, 10^15)) and solving the subproblem again, CPLEX announces the status as feasible. Interestingly, even when CPLEX announces the subproblem as infeasible, it is able to give me the objective function value and the values of all variables once the subproblem is solved. The bigger issue for me is that I cannot ask for the unboundedness ray (to build a feasibility cut) since the subproblem is announced as infeasible. 

So, my question is: What can be done to receive a feasible unbounded status from CPLEX (so that I could then ask for the unboundedness ray).

Thanks

------------------------------
Hassan Sarhadi
------------------------------

#DecisionOptimization

The actual subproblem should either be infeasible or have an optimal solution. The dual of the subproblem should either be unbounded or have an optimal solution. So, are you solving the original subproblem (variables and constraints a subset of what was in the problem before decomposition), or are you formulating and solving the dual of the subproblem?

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

Original Message:
Sent: Mon February 21, 2022 01:08 PM
From: Hassan Sarhadi
Subject: CPLEX Infeasibility/Unboundedness

Hello all,

I've got a question with regard to the Infeasibility/Unboundedness status of my model.

I'm implementing a Benders decomposition in which I have a master problem and a sub problem. Once the subproblem is solved by CPLEX, the infeasible status is announced by CPLEX. However, based on my understanding, the subproblem should be feasible unbounded. This is because I know a feasible solution that always satisfies all the constraints. Also, when I limit the bounds of a given variable (limiting it to be within (0,1) as opposed to (0, 10^15)) and solving the subproblem again, CPLEX announces the status as feasible. Interestingly, even when CPLEX announces the subproblem as infeasible, it is able to give me the objective function value and the values of all variables once the subproblem is solved. The bigger issue for me is that I cannot ask for the unboundedness ray (to build a feasibility cut) since the subproblem is announced as infeasible. 

So, my question is: What can be done to receive a feasible unbounded status from CPLEX (so that I could then ask for the unboundedness ray).

Thanks

------------------------------
Hassan Sarhadi
------------------------------

#DecisionOptimization

Hi Paul,

Thanks for the reply.  I'm solving the dual of the subproblem.

I'm quite sure that the dual of the subproblem is feasible and unbounded but CPLEX considers it as infeasible (even if it gives me the optimal objective function value and the optimal values of all variables).

Thanks,
Hassan

------------------------------
Hassan Sarhadi
------------------------------

Original Message:
Sent: Mon February 21, 2022 06:27 PM
From: Paul Rubin
Subject: CPLEX Infeasibility/Unboundedness

The actual subproblem should either be infeasible or have an optimal solution. The dual of the subproblem should either be unbounded or have an optimal solution. So, are you solving the original subproblem (variables and constraints a subset of what was in the problem before decomposition), or are you formulating and solving the dual of the subproblem?

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

Original Message:
Sent: Mon February 21, 2022 01:08 PM
From: Hassan Sarhadi
Subject: CPLEX Infeasibility/Unboundedness

Hello all,

I've got a question with regard to the Infeasibility/Unboundedness status of my model.

I'm implementing a Benders decomposition in which I have a master problem and a sub problem. Once the subproblem is solved by CPLEX, the infeasible status is announced by CPLEX. However, based on my understanding, the subproblem should be feasible unbounded. This is because I know a feasible solution that always satisfies all the constraints. Also, when I limit the bounds of a given variable (limiting it to be within (0,1) as opposed to (0, 10^15)) and solving the subproblem again, CPLEX announces the status as feasible. Interestingly, even when CPLEX announces the subproblem as infeasible, it is able to give me the objective function value and the values of all variables once the subproblem is solved. The bigger issue for me is that I cannot ask for the unboundedness ray (to build a feasibility cut) since the subproblem is announced as infeasible. 

So, my question is: What can be done to receive a feasible unbounded status from CPLEX (so that I could then ask for the unboundedness ray).

Thanks

------------------------------
Hassan Sarhadi
------------------------------

#DecisionOptimization

I can't picture how CPLEX could come up with a feasible solution while saying the problem is infeasible. If it thinks the problem is unbounded, it could give you the last basic feasible solution encountered before it detected the unboundedness.

How is CPLEX communicating infeasibility? Are you checking the solver status (and if so, what exact status does it return)? Is it something in the output log (in which case please post the relevant portion of the log here).

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

Original Message:
Sent: Mon February 21, 2022 06:40 PM
From: Hassan Sarhadi
Subject: CPLEX Infeasibility/Unboundedness

Hi Paul,

Thanks for the reply.  I'm solving the dual of the subproblem.

I'm quite sure that the dual of the subproblem is feasible and unbounded but CPLEX considers it as infeasible (even if it gives me the optimal objective function value and the optimal values of all variables).

Thanks,
Hassan

------------------------------
Hassan Sarhadi

Original Message:
Sent: Mon February 21, 2022 06:27 PM
From: Paul Rubin
Subject: CPLEX Infeasibility/Unboundedness

The actual subproblem should either be infeasible or have an optimal solution. The dual of the subproblem should either be unbounded or have an optimal solution. So, are you solving the original subproblem (variables and constraints a subset of what was in the problem before decomposition), or are you formulating and solving the dual of the subproblem?

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

Original Message:
Sent: Mon February 21, 2022 01:08 PM
From: Hassan Sarhadi
Subject: CPLEX Infeasibility/Unboundedness

Hello all,

I've got a question with regard to the Infeasibility/Unboundedness status of my model.

I'm implementing a Benders decomposition in which I have a master problem and a sub problem. Once the subproblem is solved by CPLEX, the infeasible status is announced by CPLEX. However, based on my understanding, the subproblem should be feasible unbounded. This is because I know a feasible solution that always satisfies all the constraints. Also, when I limit the bounds of a given variable (limiting it to be within (0,1) as opposed to (0, 10^15)) and solving the subproblem again, CPLEX announces the status as feasible. Interestingly, even when CPLEX announces the subproblem as infeasible, it is able to give me the objective function value and the values of all variables once the subproblem is solved. The bigger issue for me is that I cannot ask for the unboundedness ray (to build a feasibility cut) since the subproblem is announced as infeasible. 

So, my question is: What can be done to receive a feasible unbounded status from CPLEX (so that I could then ask for the unboundedness ray).

Thanks

------------------------------
Hassan Sarhadi
------------------------------

#DecisionOptimization

Hi Paul,

I'm using GetStatus() method to find the status of the problem (and to print appropriate messages for me on the Console). Once I get the status, I use the GetRay() method to obtain the unboundedness ray. However, CPLEX error 1254 will be displayed as it already declared the problem as infeasible.

Now, if I abandon the idea of getting the unboundedness ray, and just ask for the objective function value (through cplex.objValue) then I will get access to the value of the objective function. In the same way, I can access to the values of variables.

I'm wondering if I'm missing anything or something needs to be changed, or some parameters, in the way that CPLEX is called. I'm not sure how to get the output log to fully understand what exactly is going on.  

Thanks,
Hassan

------------------------------
Hassan Sarhadi
------------------------------

Original Message:
Sent: Tue February 22, 2022 03:44 PM
From: Paul Rubin
Subject: CPLEX Infeasibility/Unboundedness

I can't picture how CPLEX could come up with a feasible solution while saying the problem is infeasible. If it thinks the problem is unbounded, it could give you the last basic feasible solution encountered before it detected the unboundedness.

How is CPLEX communicating infeasibility? Are you checking the solver status (and if so, what exact status does it return)? Is it something in the output log (in which case please post the relevant portion of the log here).

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

Original Message:
Sent: Mon February 21, 2022 06:40 PM
From: Hassan Sarhadi
Subject: CPLEX Infeasibility/Unboundedness

Hi Paul,

Thanks for the reply.  I'm solving the dual of the subproblem.

I'm quite sure that the dual of the subproblem is feasible and unbounded but CPLEX considers it as infeasible (even if it gives me the optimal objective function value and the optimal values of all variables).

Thanks,
Hassan

------------------------------
Hassan Sarhadi

Original Message:
Sent: Mon February 21, 2022 06:27 PM
From: Paul Rubin
Subject: CPLEX Infeasibility/Unboundedness

The actual subproblem should either be infeasible or have an optimal solution. The dual of the subproblem should either be unbounded or have an optimal solution. So, are you solving the original subproblem (variables and constraints a subset of what was in the problem before decomposition), or are you formulating and solving the dual of the subproblem?

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

Original Message:
Sent: Mon February 21, 2022 01:08 PM
From: Hassan Sarhadi
Subject: CPLEX Infeasibility/Unboundedness

Hello all,

I've got a question with regard to the Infeasibility/Unboundedness status of my model.

I'm implementing a Benders decomposition in which I have a master problem and a sub problem. Once the subproblem is solved by CPLEX, the infeasible status is announced by CPLEX. However, based on my understanding, the subproblem should be feasible unbounded. This is because I know a feasible solution that always satisfies all the constraints. Also, when I limit the bounds of a given variable (limiting it to be within (0,1) as opposed to (0, 10^15)) and solving the subproblem again, CPLEX announces the status as feasible. Interestingly, even when CPLEX announces the subproblem as infeasible, it is able to give me the objective function value and the values of all variables once the subproblem is solved. The bigger issue for me is that I cannot ask for the unboundedness ray (to build a feasibility cut) since the subproblem is announced as infeasible. 

So, my question is: What can be done to receive a feasible unbounded status from CPLEX (so that I could then ask for the unboundedness ray).

Thanks

------------------------------
Hassan Sarhadi
------------------------------

#DecisionOptimization

First, I want to confirm that what getStatus() returns is "Infeasible" and not "InfeasibleOrUnbounded" (which is an entirely different status).

Second, it might help to know what API you are using (and what version of CPLEX).

Third, you said you know a feasible solution to the dual problem. What happens if you fix all the variables at that solution (by setting lower bound = upper bound = solution value) and then try to solve the dual? If CPLEX reports the dual infeasible, it would be useful to run the conflict refiner and have it tell you which constraints are not satisfied by that solution.

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

Original Message:
Sent: Sat February 26, 2022 12:44 AM
From: Hassan Sarhadi
Subject: CPLEX Infeasibility/Unboundedness

Hi Paul,

I'm using GetStatus() method to find the status of the problem (and to print appropriate messages for me on the Console). Once I get the status, I use the GetRay() method to obtain the unboundedness ray. However, CPLEX error 1254 will be displayed as it already declared the problem as infeasible.

Now, if I abandon the idea of getting the unboundedness ray, and just ask for the objective function value (through cplex.objValue) then I will get access to the value of the objective function. In the same way, I can access to the values of variables.

I'm wondering if I'm missing anything or something needs to be changed, or some parameters, in the way that CPLEX is called. I'm not sure how to get the output log to fully understand what exactly is going on.  

Thanks,
Hassan

------------------------------
Hassan Sarhadi

Original Message:
Sent: Tue February 22, 2022 03:44 PM
From: Paul Rubin
Subject: CPLEX Infeasibility/Unboundedness

I can't picture how CPLEX could come up with a feasible solution while saying the problem is infeasible. If it thinks the problem is unbounded, it could give you the last basic feasible solution encountered before it detected the unboundedness.

How is CPLEX communicating infeasibility? Are you checking the solver status (and if so, what exact status does it return)? Is it something in the output log (in which case please post the relevant portion of the log here).

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

Original Message:
Sent: Mon February 21, 2022 06:40 PM
From: Hassan Sarhadi
Subject: CPLEX Infeasibility/Unboundedness

Hi Paul,

Thanks for the reply.  I'm solving the dual of the subproblem.

I'm quite sure that the dual of the subproblem is feasible and unbounded but CPLEX considers it as infeasible (even if it gives me the optimal objective function value and the optimal values of all variables).

Thanks,
Hassan

------------------------------
Hassan Sarhadi

Original Message:
Sent: Mon February 21, 2022 06:27 PM
From: Paul Rubin
Subject: CPLEX Infeasibility/Unboundedness

The actual subproblem should either be infeasible or have an optimal solution. The dual of the subproblem should either be unbounded or have an optimal solution. So, are you solving the original subproblem (variables and constraints a subset of what was in the problem before decomposition), or are you formulating and solving the dual of the subproblem?

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

Original Message:
Sent: Mon February 21, 2022 01:08 PM
From: Hassan Sarhadi
Subject: CPLEX Infeasibility/Unboundedness

Hello all,

I've got a question with regard to the Infeasibility/Unboundedness status of my model.

I'm implementing a Benders decomposition in which I have a master problem and a sub problem. Once the subproblem is solved by CPLEX, the infeasible status is announced by CPLEX. However, based on my understanding, the subproblem should be feasible unbounded. This is because I know a feasible solution that always satisfies all the constraints. Also, when I limit the bounds of a given variable (limiting it to be within (0,1) as opposed to (0, 10^15)) and solving the subproblem again, CPLEX announces the status as feasible. Interestingly, even when CPLEX announces the subproblem as infeasible, it is able to give me the objective function value and the values of all variables once the subproblem is solved. The bigger issue for me is that I cannot ask for the unboundedness ray (to build a feasibility cut) since the subproblem is announced as infeasible. 

So, my question is: What can be done to receive a feasible unbounded status from CPLEX (so that I could then ask for the unboundedness ray).

Thanks

------------------------------
Hassan Sarhadi
------------------------------

#DecisionOptimization