Row- and Col id in edge of BiparteRepresentation might not match order in features

[Engberg-Jacob]

This might not be unexpected behaviour, but I thought I'd report it nonetheless. When using the getBipartiteGraphRepresentation in the coming release, the order of variables in col_features and constraints in row_features doesn't match the col_idx and row_idx numbers in edge.

To Reproduce I've included a small working example in a zip-folder. It'll create a text folder with the first entry in col_features, row_features, and edge. The col_features corresponds to y_1 and row_features corresponds to demand_1. However the first edge indicates that variable 0, in constraint 0, should have a coefficient of -73. However, y_1 only has that coefficient in 2 other constraints (namely capacity_1 and total_capacity).

Expected behavior That the edge indexes correspond to the order in col_features and row_features.

System

• OS: Ubuntu
• Version 20.04.6
• SCIP 9.1.0
• pyscipopt was compiled from source, from the mt/add_bipartite_graph branch, against the libscip_linux from https://github.com/scipopt/scipoptsuite-deploy/releases/tag/v0.4.0

This might not be unexpected behaviour, or there might be intricacies in how the rows and columns are referenced which I might not get. code-and-instance.zip

[Opt-Mucca]

Thanks for including the example! That made it much easier to understand what's going on.

I think there has been a misunderstanding. I think the most helpful thing to do is to read the definition of the transformed problem, a column, and a row in the following documentation: https://pyscipopt.readthedocs.io/en/latest/tutorials/vartypes.html# https://pyscipopt.readthedocs.io/en/latest/tutorials/constypes.html#

What I believe the three points of confusion are:

• It is very difficult to relate the bipartite graph to the original constraints. The problem goes through presolve, so some variables may be deleted or added, and some coefficient values might change. Therefore the problem is different at that stage of the solving process compared to the modelling step (which the user thinks in).
• A constraint is not a row. A row is how the constraint is represented in the LP relaxation. While this is often identical for MILPs with standard constraints (such as your problem) from a users perspective with how they've modelled the constraint, some transformations can still happen.
• The order of the rows does not need to match the order of the constraints. Therefore cons[0] has no guaranteed relationship to the ordering in the bipartite graph.

After checking through your instance: edge_features[0] is holding information about the transformed variable corresponding to y_1 (because the name of the variable is t_y_1) and I'd probably bet it's for the row representation of the capacity_1 constraint.

[Engberg-Jacob]

Alright, perfect! I'd imagined that it was simply transformation, but I wanted to be sure that row_idx and col_idx matched order of columns in col_features and rows in row_features. Thank you!