Possible `block_elimination` bug

[stevenan5]

Hi there,

I've observed some behavior with cdd.block_elimination that potentially points to it being broken.

I have a polytope (with H-rep in hand) where I want to remove some variables.

To do this, I've tried a variety of different methods that should all provide equivalent outputs:

1. Use pycddlib's block_elimination to remove the variables
2. Use pycddlib to convert to V-rep, remove the variables I don't want by removing the associated columns, then recover H-rep
3. Directly use cdd's dd_blockElimination method via projection.c. click me.
4. Directly use cdd's dd_FourierElimination method via fourier.c. click me. This was repeated until all desired variables were removed.
5. Use the lrs library's own fourier elimination method. click me. Here, the library repeats fourier elimination until the desired variables are removed.

The above was done with the following variations:

1. Columns of my H-rep were permuted. I.e. the position of the variables in the input files were permuted.
2. For (1,2), the pycddlib experiments, use import cdd and import cdd.gmp.

I observed that methods (2-5) all gave equivalent answers regardless of the permutation of the columns, while the result from (1) differed from the results of (2-5). Moreover, (1)'s output differed depending on the permutation of the columns. This leads me to believe that the problem lies with pycddlib's block_elimination.

Below is the information that one can hopefully reproduce the issue with. Please see pycddlib_testing.zip for the complete inputs/outputs & code that does (1,2) from above.

Setup and version info

Here is my environment.yml file. pip was used to install pycddlib.

name: test_pycddlib_block
channels:
  - defaults
dependencies:
  - numpy=2.4.1
  - gmpy2=2.2.2
  - pip=26.0.1
  - python=3.14.2
  - pip:
      - pycddlib==3.0.2

---

• cdd version: 0.94n
  • (I know pycddlib uses 0.94m still, but when looking in cddlib's commits, I don't see any changes between 0.94m/0.94n that would explain my observed behavior)
• lrslib version: 7.3
• gmp version: 6.3.0

Polytope in question

The last line is for lrs. This is inputs/polytope_with_linearity.ine in the attached file. There are no redundancies in this representation.

H-representation
linearity 8 1 2 3 4 5 6 7 8
begin
 16 13 rational
 600 -1 -1 -1 -1 0 1 0 1 1 0 1 0
 600 -1 -1 -1 -1 0 1 1 0 0 1 1 0
 500 -1 -1 -1 -1 0 1 0 1 0 1 0 1
 500 -1 -1 -1 -1 1 0 1 0 1 0 1 0
 1000 -1 -1 -1 -1 0 0 0 0 0 0 0 0
 0 -1 0 0 0 1 1 0 0 0 0 0 0
 0 0 -1 0 0 0 0 1 1 0 0 0 0
 0 0 0 -1 0 0 0 0 0 1 1 0 0
 0 0 0 0 0 1 0 0 0 0 0 0 0
 0 0 0 0 0 0 1 0 0 0 0 0 0
 0 0 0 0 0 0 0 1 0 0 0 0 0
 0 0 0 0 0 0 0 0 1 0 0 0 0
 0 0 0 0 0 0 0 0 0 1 0 0 0
 0 0 0 0 0 0 0 0 0 0 1 0 0
 0 0 0 0 0 0 0 0 0 0 0 1 0
 0 0 0 0 0 0 0 0 0 0 0 0 1
end
eliminate 8 5 6 7 8 9 10 11 12

Polytope with permuted indices

This is inputs/polytope_with_linearity_permuted_cols.ine in the attached file. There are no redundancies in this representation.

H-representation
linearity 8 1 2 3 4 5 6 7 8
begin
 16 13 rational
 600 -1 0 1 -1 0 1 -1 1 0 -1 1 0
 600 -1 0 1 -1 1 0 -1 0 1 -1 1 0
 500 -1 0 1 -1 0 1 -1 0 1 -1 0 1
 500 -1 1 0 -1 1 0 -1 1 0 -1 1 0
 1000 -1 0 0 -1 0 0 -1 0 0 -1 0 0
 0 -1 1 1 0 0 0 0 0 0 0 0 0
 0 0 0 0 -1 1 1 0 0 0 0 0 0
 0 0 0 0 0 0 0 -1 1 1 0 0 0
 0 0 1 0 0 0 0 0 0 0 0 0 0
 0 0 0 1 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 1 0 0 0 0 0 0 0
 0 0 0 0 0 0 1 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 1 0 0 0 0
 0 0 0 0 0 0 0 0 0 1 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 1 0
 0 0 0 0 0 0 0 0 0 0 0 0 1
end
eliminate 8 2 3 5 6 8 9 11 12

Expected output from eliminating last 8 variables

Below is an example of the expected output. Outputs from methods (2-5) from above give equivalent H-reps. There are no redundancies in this representation.

H-representation
linearity 1 1
begin
 10 5 real
 1000 -1 -1 -1 -1
 0  1  0  0  0
 0  0  1  0  0
 0  0  0  1  0
 -100  1  1  0  0
 -100  1  0  1  0
 -1000  1  1  1  2
 -1100  1  1  2  2
 -1100  1  2  1  2
 -1200  2  1  1  2
end

pycddlib output for above polytope using block_elimination

The following representation has no redundancies.

 H-representation
begin
 8 5 rational
 1200 0 -1 -1 -2
 -1200 2 1 1 2
 -1100 1 2 1 2
 1100 -1 0 -1 -2
 -1100 1 1 2 2
 1100 -1 -1 0 -2
 1000 -1 -1 -1 -1
 0 0 0 0 1
end

The number of inequalities is wrong, 8 here instead of the expected 10 and there is no linearity constraint on the second to last constraint.

pycddlib output for polytope with permuted indices using block_elimination

Similar story here. There are no redundancies and there different number of constraints.

 H-representation
linearity 1  1
begin
 7 5 rational
 500 -1 -1 -1 -1
 -100 0 1 0 1
 -100 0 0 1 1
 0 1 0 0 0
 0 0 1 0 0
 0 0 0 1 0
 0 0 0 0 1
end

[mcmtroffaes]

Thanks for the careful analysis. The implementation really just calls dd_BlockElimination and does not much do much of anything else:

https://github.com/mcmtroffaes/pycddlib/blob/develop/cython/pycddlib.pxi#L1174

My first thought is: is it possible something's gone wrong with the lin_set? pycddlib uses indexing starting from 0 (consistently), whereas cddlib uses indexing from 1.

[stevenan5]

Yes, I think there is an off by 1 error when dd_colset is given to dd_blockElimination.

By using projection.c on inputs/polytope_with_linearity.ine and inputs/polytope_with_linearity_permuted_cols.ine, I get the same result as pycddlib. See below for outputs.

Actually, it turns out if I use 1-indexed indices for pycddlib's block_elimination function I get the right answers! See last section.

I'm looking at the code a bit more carefully now and will report back if I can find the bug by inspection.

cdd projection.c on polytope, inds off by 1

input file inputs/polytope_with_linearity.ine is open
How many variables to eliminate? (max 12): 8
1 th deletion variable): 4
2 th deletion variable): 5
3 th deletion variable): 6
4 th deletion variable): 7
5 th deletion variable): 8
6 th deletion variable): 9
7 th deletion variable): 10
8 th deletion variable): 11

H-representation
begin
 8 5 real
 1200  0 -1 -1 -2
 -1200  2  1  1  2
 -1100  1  2  1  2
 1100 -1  0 -1 -2
 -1100  1  1  2  2
 1100 -1 -1  0 -2
 1000 -1 -1 -1 -1
  0  0  0  0  1
end

Redundant rows: 

H-representation
begin
 8 5 real
 1200  0 -1 -1 -2
 -1200  2  1  1  2
 -1100  1  2  1  2
 1100 -1  0 -1 -2
 -1100  1  1  2  2
 1100 -1 -1  0 -2
 1000 -1 -1 -1 -1
  0  0  0  0  1
end

cdd projection.c on polytope with permuted cols, inds off by 1

input file inputs/polytope_with_linearity_permuted_cols.ine is open
How many variables to eliminate? (max 12): 8
1 th deletion variable): 1
2 th deletion variable): 2
3 th deletion variable): 4
4 th deletion variable): 5
5 th deletion variable): 7
6 th deletion variable): 8
7 th deletion variable): 10
8 th deletion variable): 11

H-representation
linearity 1  9
begin
 9 5 real
 100  1  0  1  0
 100  1  1  0  0
 -100  0  1  0  1
 -100  0  0  1  1
  0  1  0  0  0
  0  0  1  0  0
  0  0  0  1  0
  0  0  0  0  1
 500 -1 -1 -1 -1
end

Redundant rows: 1 2 

H-representation
linearity 1  1
begin
 7 5 real
 500 -1 -1 -1 -1
 -100  0  1  0  1
 -100  0  0  1  1
  0  1  0  0  0
  0  0  1  0  0
  0  0  0  1  0
  0  0  0  0  1
end

pycddlib with 1-indexing of columns to remove

New version of min_example.py where I've changed the indices of the columns to be removed by block_elimination to be 1-indexed: min_example.py

The output is as follows. I have permuted the rows so that it's easier to compare the results via block_elimination and the results from converting to V-rep then projecting.

Removing variables using Block elimination on  inputs/polytope_with_linearity.ine
Removal indices are  {5, 6, 7, 8, 9, 10, 11, 12}
Resulting cdd matrix is
 H-representation
linearity 1  1
begin
 10 5 real
 1000 -1 -1 -1 -1
  0  1  0  0  0
  0  0  1  0  0
  0  0  0  1  0
 -100  1  1  0  0
 -100  1  0  1  0
 -1200  2  1  1  2
 -1100  1  2  1  2
 -1100  1  1  2  2
 -1000  1  1  1  2
end 

Removing variables by converting to V-Rep then projecting (removing columns)
Indices kept were  [0 1 2 3]
H-representation
linearity 1  1
begin
 10 5 real
 -1000  1  1  1  1
  0  1  0  0  0
  0  0  1  0  0
  0  0  0  1  0
 -100  1  1  0  0
 -100  1  0  1  0
 800  0 -1 -1  0
 900 -1  0 -1  0
 900 -1 -1  0  0
 1000 -1 -1 -1  0
end 

Removing variables using Block elimination on  inputs/polytope_with_linearity_permuted_cols.ine
Removal indices are  {2, 3, 5, 6, 8, 9, 11, 12}
Resulting cdd matrix is
 H-representation
linearity 1  1
begin
 10 5 real
 1000 -1 -1 -1 -1
  0  1  0  0  0
  0  0  1  0  0
  0  0  0  1  0
 -100  1  1  0  0
 -100  1  0  1  0
 -1200  2  1  1  2
 -1100  1  2  1  2
 -1100  1  1  2  2
 -1000  1  1  1  2
end 

Removing variables by converting to V-Rep then projecting (removing columns)
Indices kept were  [0 3 6 9]
H-representation
linearity 1  1
begin
 10 5 real
 -1000  1  1  1  1
 0  1  0  0  0
 0  0  1  0  0
 0  0  0  1  0
 -100  1  1  0  0
 -100  1  0  1  0
 800  0 -1 -1  0
 900 -1  0 -1  0
 900 -1 -1  0  0
 1000 -1 -1 -1  0
end 

[stevenan5]

Okay so I looked into this more and figured out what's going on. Since cdd uses 1-indexing for rows and columns, index 1 of [b A] is the coefficient vector b. Thus, the index of the first variable is 2. When dealing with variables, we need to add 2 in _set_set rather than 1.

For example, in projection.c from cdd, after you provide the index t of the variable you want to delete (with 1 being the first variable), the element added to the set is t+1. click me

Working on a PR now.

[stevenan5]

I've created two different solutions for this problem.

1. Use 0-indexing for variables removed via block_elimination #91 changes the API so you pass in a set of 0-index indices of the variables you want to eliminate
2. Update block_elimination documentation and check for invalid index #92 updates the documentation to warn a person that the indices you need to pass into the col_set argument should begin with 1 for the 1st variable. Also, a check is added to ensure that you don't pass in an index of 0 to block_elimination.

[mcmtroffaes]

A huge thanks for these! I'm glad I could put you in the right direction. I prefer to stay as close as possible to the original API, so the second solution, pr #92, seems like the preferred solution to me.

[stevenan5]

Sure no problem. I'll go ahead and close #91. Please let me know if there's anything else I can do.

[mcmtroffaes]

Awesome, thanks for reporting and for the quick and excellent fix!