Originally posted by: NSopt

Hi.

We are solving Set Partitioning Problem that has the form Ax = e where A is all {0,1} matrix.

If we turn on Presolve option, aggregator did some substitutions and reduced A matrix will have -1 element.

Since we don't want it we turn off the aggregator by setting CPX_PARAM_AGGIND to 0.

But, it is observed that reduced matrix A still have -1 even though we didn't do any substitutions.

Is there any other presolve option to be turned off other than aggregator? (we want to use overall presolve option though)

Thank you.

NS

Originally posted by: TobiasAchterberg

I would have to take a closer look, but I guess there are other presolve reductions that can do this. When you see -1 coefficients, do you then also see right hand side values different from 1?

If you want me to dig deeper, then you have to provide a (preferably small) example where you see this behavior even with disabled aggregator.

But the main question to me is why you want to have this property. Can you briefly explain?

Additionally, if this property is required for you, then you could probably get it in a postprocessing step: extract the presolved model and for any variable x that has at least one -1 entry in the matrix create a new variable x' with objective function value 0. Then replace all -1 coefficients of x by +1 for x' and increment the right hand side of the row by 1. Finally, add a row x + x' = 1. This way, you have explicitly added the complement of x to the model and expressed all your constraints with positive coefficients using the original variables and their complements.

Tobias

Originally posted by: NSopt

Thank you for your answer.

I checked that RHS of the row which has -1 in reduced A matrix is 1. It seems like it did substitution even with aggregator turned off.

And it turned out that it only happens when CPLEX do 'repeating presolve'.

If you are available to run 'air04.mps', you will be able to observe this.

NS

Originally posted by: TobiasAchterberg

Sorry for the late reply.

I took a look at the air04 model. I disabled the aggregator, launched the optimization, aborted it after the repeated presolve and wrote out the presolved model. Then I looked at this presolved model.

There are indeed some -1 coefficients, but whenever such a coefficient appears, the rhs value is no longer 1. Instead, the rhs is always equal to 1 minus the number of -1 coefficients in the row, which is exactly what you would expect for set partitioning constraints. Are you sure that you get a -1 coefficient in a row that has a +1 right hand side value?

The -1 coefficients can come from probing. Namely, probing is able to identify aggregations of the form x = y and x = 1 - y. It would substitute the x variable for y, and in the latter case this would yield -y entries in the matrix (but at the same time reducing the rhs by 1).

If I disable probing then I don't get any -1 coefficients anymore. But note that there is no guarantee that disabling the aggregator and probing will always yield this property. There might be other places in the code that could detect x = 1-y aggregations.

Tobias

Originally posted by: NSopt

Thank you very much for your answer.

I will ask again if there's another issue with this.

NS