Intermediate infeasible

[Jean]

Hello

I am trying to linearize and solve a nonlinear integer program. The nonlinear term(s) is a result of multiplication of two binary variables (X_ikmj and Y_lnr).

I substituted the X_ikmj *Y_lnr by a new binary variable of Z_ikmjlnr i.e.,

Z_ikmjlnr =X_ikmj *Y_lnr

And added the following three new constraints:

Z_ikmjlnr<= X_ikmj

Z_ikmjlnr<= Y_lnr

Z_ikmjlnr>= X_ikmj+ Y_lnr-1

Trying to solve the model I receive the following message:

“Warning: After zero iterations CPLEX 12.3 was interrupted and LeastCost is still infeasible”

Please note that this is a part of larger math program with other nonlinear terms. The model works (and can be solved nicely) when I do the same procedure described above for the other nonlinear terms (ignoring the above described part). But as soon as I add this section I got the error.

Please let me know if you have any suggestion to resolve this issue.

Thank you,

Jean

[Guido Diepen]

Hi Jean,

could you check if there is more information available in the messages window after you see this warning?. You can the messages window in AIMMS with CTRL-M or via Windows > Messages window.

Guido Diepen

AIMMS Specialist

[Jean]

Hi Guido,

Many thanks for your reply. Here is the complete message copied from AIMMS message window:

 

“There is 29.695 Mb in use.

CPLEX Error  1001: Out of memory.

Warning: After zero iterations CPLEX 12.3 was interrupted and LeastCostHubandSpoke is still infeasible.”

 

Regards,

Nader

[Guido Diepen]

Hi Nader,

looking back at your original post, it might be due to the following variable:

Z_ikmjlnr

This particular variable is defined over 7 indices, which has the potential to explode the number of actual variables: If every dimension only has 10 elements, you already have 10 million combinations for which an actual variable is generated.

You can verify if this is the problem by opening the Progress Window (either by pressing CTRL-P or Window > Progress Window)  before you solve your problem. After the error message, in this progress window you should be able to see the number of variables and constraints that were actually generated (and also the number of non-zeros in the matrix). My guess is that you have very large numbers here, which result in you hitting memory bounds.

If this is indeed the case, please verify if you can eliminate combinations of indices from generation by introducing a domain condition on the index domain of the Z variable (and possibly also any other higher dimensional parameter/variable you have in your model). 

Guido Diepen

AIMMS Specialist

[Jean]

Hi Guido,

 

The problem instance that I was able to solve has 325704 variables and 303428 constraints (according to the info posted at progress report window). As I added the new three constraints (mentioned above), the number of variables and constraints raised to 456384 and 1334479 respectively. I did what you said (i.e., eliminating combinations of indices from generation by introducing a domain condition on the index domain). And as a result, the number of variables reduces to about 330000. Since the error is still there, perhaps the error is being generated because of  the number of constraints . Please let me know if you have any suggestion.

Thank you,

Nader

[Marcel Hunting]

Hi,

How many nonzero’s does the model have?

The number of variables and constraints in your model is not very
large. Normally CPLEX should be able to handle such a model without
immediately returning that it is running out of memory (at least that
is what I assume; can you confirm that CPLEX quits immediately?)

Probably it does not resolve the memory issue, but you can change the
range of variable Zikmjlnr into [0,1] (so continuous) instead of
binary; the other constraints enforce this variable to be either 0 or
1.

An option is to use the so-called proxy stub interface of AIMMS which
increases the amount of memory available to CPLEX; see the
Troubleshooting section of the AIMMS-CPLEX help for more information.

You also might want to try setting CPLEX option ‘aggregator’ to 0.

Marcel Hunting
AIMMS Software Developer

[Jean]

Hi Marcel,

Here are the info about the variables and constraints:

#of constraints: 985193

#variables: 340404

#nonzeros: 2595447

CPLEX quits in about 3 min after execution begins. For changing the range of Variable Z, I have already done that for all Auxiliary variables of type Z. As expected the number of variables reduced significantly but still I can’t get any results. I tried setting CPLEX option “aggregator” to 0; it didn’t help either.

Thank you,

Nader

[Jean]

Hi,

I changed the range of variable Zikmjlnr and other auxiliary variables into [0,1] and solver to CPLEX (ps).  Here is some info reported in progress report after 50 sec:

#Constraints: 985192

#Variables: 2598

#Nonzero: 1320810

Infeasibility: na

Best solution: na

Program status: Integer infeasible

Any suggestion to resolve this issue is appreciated in advance.

Nader

[Marcel Hunting]

Hi Nader,

The number of nonzero’s is not very large. With the last run, do you
still get the message that CPLEX is out of memory?

Maybe the CPLEX output file gives more information. To print that file
you should set the general solvers option ‘Solver Listing Messages’ to
‘Remark’ and the CPLEX option ‘MIP Display’ to, e.g., ‘Display each
nth node’. The output file will be printed as 'CPLEX 12.x.sta' in the
‘log’ directory of your AIMMS project. Can you copy the output?

[Jean]

Hi Marcel,

Many thanks for your reply.

I don’t get the message that CPLEX is out of memory any more. Here is the copy of the CEPLEX 12.x.sta:

“Tried aggregator 1 time.

Infeasibility row 'NumberOfOpenHubs':  0  = 3.

Presolve time =    4.66 sec.

Memory in use by CPLEX 12.3.0.1: 77111944 bytes.”

 

Thanks you,

Nader

[Marcel Hunting]

Hi Nader,

Your model now contains an inconsistency in constraint
‘NumberOfOpenHubs’. Apparently the left-hand-side evaluates to 0 while
the right-hand-side evaluates to 3 which makes the model infeasible
because constraint ‘NumberOfOpenHubs’ is an equality.

Marcel