1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB) */ 7 /* */ 8 /* Licensed under the Apache License, Version 2.0 (the "License"); */ 9 /* you may not use this file except in compliance with the License. */ 10 /* You may obtain a copy of the License at */ 11 /* */ 12 /* http://www.apache.org/licenses/LICENSE-2.0 */ 13 /* */ 14 /* Unless required by applicable law or agreed to in writing, software */ 15 /* distributed under the License is distributed on an "AS IS" BASIS, */ 16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */ 17 /* See the License for the specific language governing permissions and */ 18 /* limitations under the License. */ 19 /* */ 20 /* You should have received a copy of the Apache-2.0 license */ 21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */ 22 /* */ 23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 24 25 /**@file reader_ccg.c 26 * @ingroup DEFPLUGINS_READER 27 * @brief Graph file reader (actually, only a writer) 28 * @author Marc Pfetsch 29 * 30 * Write a weighted column/variable graph, i.e., the nodes correspond to the columns (variables) of 31 * the constraint matrix. Two nodes are adjacent if the corresponding columns/variables appear 32 * in a common row/constraint (with nonzero coefficient). The weight is obtained by summing for 33 * each row that produces an edge the absolute values of coefficients in the row; hence, we avoid 34 * parallel edges. 35 * 36 * This graph gives an indication of the connectivity structure of the constraint matrix. 37 * 38 * The graph is output in DIMACS graph format. 39 */ 40 41 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 42 43 #include "blockmemshell/memory.h" 44 #include "scip/cons_knapsack.h" 45 #include "scip/cons_linear.h" 46 #include "scip/cons_logicor.h" 47 #include "scip/cons_setppc.h" 48 #include "scip/cons_varbound.h" 49 #include "scip/pub_cons.h" 50 #include "scip/pub_message.h" 51 #include "scip/pub_reader.h" 52 #include "scip/pub_var.h" 53 #include "scip/reader_ccg.h" 54 #include "scip/scip_cons.h" 55 #include "scip/scip_mem.h" 56 #include "scip/scip_message.h" 57 #include "scip/scip_reader.h" 58 #include "scip/scip_var.h" 59 #include <string.h> 60 61 #define READER_NAME "ccgreader" 62 #define READER_DESC "file writer for column connectivity graph file format" 63 #define READER_EXTENSION "ccg" 64 65 /* 66 * Data structures 67 */ 68 69 70 /* graph data structure */ 71 struct sparseGraph 72 { 73 unsigned int n; /**< number of nodes */ 74 unsigned int m; /**< number of edges */ 75 int** A; /**< adjacency list (= adjacent nodes) for each node (-1 for end of list) */ 76 SCIP_Real** W; /**< weights for each edge */ 77 unsigned int* deg; /**< degree each node */ 78 unsigned int* size; /**< size of A/w for each node */ 79 }; 80 81 typedef struct sparseGraph SparseGraph; 82 83 84 /* 85 * Local methods (for writing) 86 */ 87 88 /** initialize graph */ 89 static 90 SCIP_RETCODE initGraph( 91 SCIP* scip, /**< SCIP data structure */ 92 SparseGraph* G, /**< graph to free */ 93 unsigned int nNodes, /**< number of nodes */ 94 unsigned int initSize /**< initial size of lists */ 95 ) 96 { 97 unsigned int i; 98 99 G->n = nNodes; 100 G->m = 0; 101 102 SCIP_CALL( SCIPallocBufferArray(scip, &G->deg, (int) nNodes) ); 103 SCIP_CALL( SCIPallocBufferArray(scip, &G->size, (int) nNodes) ); 104 SCIP_CALL( SCIPallocBufferArray(scip, &G->A, (int) nNodes) ); 105 SCIP_CALL( SCIPallocBufferArray(scip, &G->W, (int) nNodes) ); 106 107 for( i = 0; i < nNodes; ++i ) 108 { 109 G->deg[i] = 0; 110 G->size[i] = initSize; 111 112 SCIP_CALL( SCIPallocBufferArray(scip, &(G->A[i]), (int) initSize) ); /*lint !e866 */ 113 SCIP_CALL( SCIPallocBufferArray(scip, &(G->W[i]), (int) initSize) ); /*lint !e866 */ 114 115 G->A[i][0] = -1; 116 } 117 118 return SCIP_OKAY; 119 } 120 121 122 /** frees graph */ 123 static 124 void freeGraph( 125 SCIP* scip, /**< SCIP data structure */ 126 SparseGraph* G /**< graph to free */ 127 ) 128 { 129 unsigned int i; 130 131 for( i = 0; i < G->n; ++i ) 132 { 133 SCIPfreeBufferArray(scip, &G->A[i]); 134 SCIPfreeBufferArray(scip, &G->W[i]); 135 } 136 137 SCIPfreeBufferArray(scip, &G->W); 138 SCIPfreeBufferArray(scip, &G->A); 139 SCIPfreeBufferArray(scip, &G->size); 140 SCIPfreeBufferArray(scip, &G->deg); 141 } 142 143 144 /** check whether there is enough capacity for one additional edge in the given adjacency list */ 145 static 146 SCIP_RETCODE ensureEdgeCapacity( 147 SCIP* scip, /**< SCIP data structure */ 148 SparseGraph* G, /**< graph */ 149 unsigned int node /**< list for node */ 150 ) 151 { 152 if( G->deg[node] + 2 > G->size[node] ) 153 { 154 unsigned int newSize; 155 newSize = G->size[node] * 2; 156 SCIP_CALL( SCIPreallocBufferArray(scip, &(G->A[node]), (int) newSize) ); /*lint !e866 */ 157 SCIP_CALL( SCIPreallocBufferArray(scip, &(G->W[node]), (int) newSize) ); /*lint !e866 */ 158 G->size[node] = newSize; 159 } 160 161 return SCIP_OKAY; 162 } 163 164 165 /** transforms given variables, scalars, and constant to the corresponding active variables, scalars, and constant */ 166 static 167 SCIP_RETCODE getActiveVariables( 168 SCIP* scip, /**< SCIP data structure */ 169 SCIP_VAR** vars, /**< vars array to get active variables for */ 170 SCIP_Real* scalars, /**< scalars a_1, ..., a_n inrc/scip/reader_graph.c linear sum a_1*x_1 + ... + a_n*x_n + c */ 171 int* nvars, /**< pointer to number of variables and values in vars and vals array */ 172 SCIP_Real* constant, /**< pointer to constant c in linear sum a_1*x_1 + ... + a_n*x_n + c */ 173 SCIP_Bool transformed /**< transformed constraint? */ 174 ) 175 { 176 int requiredsize; 177 int v; 178 179 assert( scip != NULL ); 180 assert( vars != NULL ); 181 assert( scalars != NULL ); 182 assert( nvars != NULL ); 183 assert( constant != NULL ); 184 185 if( transformed ) 186 { 187 SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, scalars, nvars, *nvars, constant, &requiredsize, TRUE) ); 188 189 if( requiredsize > *nvars ) 190 { 191 SCIP_CALL( SCIPreallocBufferArray(scip, &vars, requiredsize) ); 192 SCIP_CALL( SCIPreallocBufferArray(scip, &scalars, requiredsize) ); 193 194 SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, scalars, nvars, requiredsize, constant, &requiredsize, TRUE) ); 195 assert( requiredsize <= *nvars ); 196 } 197 } 198 else 199 { 200 for( v = 0; v < *nvars; ++v ) 201 SCIP_CALL( SCIPvarGetOrigvarSum(&vars[v], &scalars[v], constant) ); 202 } 203 return SCIP_OKAY; 204 } 205 206 207 /* Generate edges from given row 208 * 209 * We avoid parallel edges. Each row generates a clique in the graph. 210 */ 211 static 212 SCIP_RETCODE createEdgesFromRow( 213 SCIP* scip, /**< SCIP data structure */ 214 SCIP_VAR** vars, /**< array of constraint variables */ 215 SCIP_Real* vals, /**< array of constraint values */ 216 int nvars, /**< number of constraint variables */ 217 SparseGraph* G /**< graph */ 218 ) 219 { 220 int i, j; 221 SCIP_Real w; 222 223 assert( scip != NULL ); 224 assert( nvars > 0 ); 225 226 /* compute weight */ 227 w = 0; 228 for( i = 0; i < nvars; ++i ) 229 w += ABS(vals[i]); 230 231 /* generate edges */ 232 for( i = 0; i < nvars; ++i ) 233 { 234 int s; 235 s = SCIPvarGetProbindex(vars[i]); 236 assert( s >= 0 ); 237 238 for( j = i+1; j < nvars; ++j ) 239 { 240 unsigned int k; 241 int t; 242 int a; 243 t = SCIPvarGetProbindex(vars[j]); 244 assert( t >= 0 ); 245 246 /* search whether edge is already present */ 247 k = 0; 248 a = G->A[s][k]; 249 while( a >= 0 ) 250 { 251 /* if we found edge, add weight */ 252 if( a == t ) 253 { 254 G->W[s][k] += w; 255 break; 256 } 257 a = G->A[s][++k]; 258 assert( k <= G->size[s] ); 259 } 260 261 /* add new edge */ 262 if( a < 0 ) 263 { 264 /* forward edge */ 265 SCIP_CALL( ensureEdgeCapacity(scip, G, (unsigned int) s) ); 266 k = G->deg[s]; 267 assert( G->A[s][k] == -1 ); 268 269 G->A[s][k] = t; 270 G->W[s][k] = w; 271 272 G->A[s][k+1] = -1; /*lint !e679*/ 273 ++G->deg[s]; 274 275 /* backward edge */ 276 SCIP_CALL( ensureEdgeCapacity(scip, G, (unsigned int) t) ); 277 k = G->deg[t]; 278 assert( G->A[t][k] == -1 ); 279 280 G->A[t][k] = s; 281 G->W[t][k] = w; 282 283 G->A[t][k+1] = -1; /*lint !e679*/ 284 ++G->deg[t]; 285 286 /* increase number of edges */ 287 ++G->m; 288 } 289 } 290 } 291 292 return SCIP_OKAY; 293 } 294 295 296 /** handle given linear constraint information */ 297 static 298 SCIP_RETCODE handleLinearCons( 299 SCIP* scip, /**< SCIP data structure */ 300 SCIP_VAR** vars, /**< array of variables */ 301 SCIP_Real* vals, /**< array of coefficients values (or NULL if all coefficient values are 1) */ 302 int nvars, /**< number of variables */ 303 SCIP_Bool transformed, /**< transformed constraint? */ 304 SparseGraph* G /**< graph */ 305 ) 306 { 307 int v; 308 SCIP_VAR** activevars; 309 SCIP_Real* activevals; 310 int nactivevars; 311 SCIP_Real activeconstant = 0.0; 312 313 assert( scip != NULL ); 314 assert( nvars > 0 ); 315 316 /* duplicate variable and value array */ 317 nactivevars = nvars; 318 SCIP_CALL( SCIPduplicateBufferArray(scip, &activevars, vars, nactivevars ) ); 319 if( vals != NULL ) 320 SCIP_CALL( SCIPduplicateBufferArray(scip, &activevals, vals, nactivevars ) ); 321 else 322 { 323 SCIP_CALL( SCIPallocBufferArray(scip, &activevals, nactivevars) ); 324 325 for( v = 0; v < nactivevars; ++v ) 326 activevals[v] = 1.0; 327 } 328 329 /* retransform given variables to active variables */ 330 SCIP_CALL( getActiveVariables(scip, activevars, activevals, &nactivevars, &activeconstant, transformed) ); 331 332 /* print constraint */ 333 SCIP_CALL( createEdgesFromRow(scip, activevars, activevals, nactivevars, G) ); 334 335 /* free buffer arrays */ 336 SCIPfreeBufferArray(scip, &activevars); 337 SCIPfreeBufferArray(scip, &activevals); 338 339 return SCIP_OKAY; 340 } 341 342 343 /* 344 * Callback methods of reader 345 */ 346 347 /** copy method for reader plugins (called when SCIP copies plugins) */ 348 static 349 SCIP_DECL_READERCOPY(readerCopyCcg) 350 { /*lint --e{715}*/ 351 assert(scip != NULL); 352 assert(reader != NULL); 353 assert(strcmp(SCIPreaderGetName(reader), READER_NAME) == 0); 354 355 /* call inclusion method of reader */ 356 SCIP_CALL( SCIPincludeReaderCcg(scip) ); 357 358 return SCIP_OKAY; 359 } 360 361 362 /** problem writing method of reader */ 363 static 364 SCIP_DECL_READERWRITE(readerWriteCcg) 365 { /*lint --e{715}*/ 366 367 SCIP_CALL( SCIPwriteCcg(scip, file, name, transformed, vars, nvars, conss, nconss, result) ); 368 369 return SCIP_OKAY; 370 } 371 372 /* 373 * reader specific interface methods 374 */ 375 376 /** includes the ccg file reader in SCIP */ 377 SCIP_RETCODE SCIPincludeReaderCcg( 378 SCIP* scip /**< SCIP data structure */ 379 ) 380 { 381 SCIP_READER* reader; 382 383 /* include reader */ 384 SCIP_CALL( SCIPincludeReaderBasic(scip, &reader, READER_NAME, READER_DESC, READER_EXTENSION, NULL) ); 385 386 assert(reader != NULL); 387 388 /* set non-fundamental callbacks via setter functions */ 389 SCIP_CALL( SCIPsetReaderCopy(scip, reader, readerCopyCcg) ); 390 SCIP_CALL( SCIPsetReaderWrite(scip, reader, readerWriteCcg) ); 391 392 return SCIP_OKAY; 393 } 394 395 396 /** writes problem to file */ 397 SCIP_RETCODE SCIPwriteCcg( 398 SCIP* scip, /**< SCIP data structure */ 399 FILE* file, /**< output file, or NULL if standard output should be used */ 400 const char* name, /**< problem name */ 401 SCIP_Bool transformed, /**< TRUE iff problem is the transformed problem */ 402 SCIP_VAR** vars, /**< array with active variables ordered binary, integer, implicit, continuous */ 403 int nvars, /**< number of active variables in the problem */ 404 SCIP_CONS** conss, /**< array with constraints of the problem */ 405 int nconss, /**< number of constraints in the problem */ 406 SCIP_RESULT* result /**< pointer to store the result of the file writing call */ 407 ) 408 { /*lint --e{715}*/ 409 int c; 410 int v; 411 int i; 412 413 SCIP_CONSHDLR* conshdlr; 414 const char* conshdlrname; 415 SCIP_CONS* cons; 416 417 SCIP_VAR** consvars; 418 SCIP_Real* consvals; 419 int nconsvars; 420 421 SparseGraph G; 422 423 assert( scip != NULL ); 424 assert( vars != NULL ); 425 assert( nvars >= 0 ); 426 427 /* initialize graph */ 428 SCIP_CALL( initGraph(scip, &G, (unsigned int) nvars, 10) ); 429 430 /* check all constraints */ 431 for( c = 0; c < nconss; ++c) 432 { 433 cons = conss[c]; 434 assert( cons != NULL); 435 436 /* in case the transformed is written only constraint are posted which are enabled in the current node */ 437 assert(!transformed || SCIPconsIsEnabled(cons)); 438 439 conshdlr = SCIPconsGetHdlr(cons); 440 assert( conshdlr != NULL ); 441 442 conshdlrname = SCIPconshdlrGetName(conshdlr); 443 assert( transformed == SCIPconsIsTransformed(cons) ); 444 445 if( strcmp(conshdlrname, "linear") == 0 ) 446 { 447 consvars = SCIPgetVarsLinear(scip, cons); 448 nconsvars = SCIPgetNVarsLinear(scip, cons); 449 assert( consvars != NULL || nconsvars == 0 ); 450 451 if( nconsvars > 0 ) 452 { 453 SCIP_CALL( handleLinearCons(scip, SCIPgetVarsLinear(scip, cons), SCIPgetValsLinear(scip, cons), 454 SCIPgetNVarsLinear(scip, cons), transformed, &G) ); 455 } 456 } 457 else if( strcmp(conshdlrname, "setppc") == 0 ) 458 { 459 consvars = SCIPgetVarsSetppc(scip, cons); 460 nconsvars = SCIPgetNVarsSetppc(scip, cons); 461 assert( consvars != NULL || nconsvars == 0 ); 462 463 if( nconsvars > 0 ) 464 { 465 SCIP_CALL( handleLinearCons(scip, consvars, NULL, nconsvars, transformed, &G) ); 466 } 467 } 468 else if( strcmp(conshdlrname, "logicor") == 0 ) 469 { 470 consvars = SCIPgetVarsLogicor(scip, cons); 471 nconsvars = SCIPgetNVarsLogicor(scip, cons); 472 assert( consvars != NULL || nconsvars == 0 ); 473 474 if( nconsvars > 0 ) 475 { 476 SCIP_CALL( handleLinearCons(scip, SCIPgetVarsLogicor(scip, cons), NULL, SCIPgetNVarsLogicor(scip, cons), transformed, &G) ); 477 } 478 } 479 else if( strcmp(conshdlrname, "knapsack") == 0 ) 480 { 481 SCIP_Longint* w; 482 483 consvars = SCIPgetVarsKnapsack(scip, cons); 484 nconsvars = SCIPgetNVarsKnapsack(scip, cons); 485 assert( consvars != NULL || nconsvars == 0 ); 486 487 /* copy Longint array to SCIP_Real array */ 488 w = SCIPgetWeightsKnapsack(scip, cons); 489 SCIP_CALL( SCIPallocBufferArray(scip, &consvals, nconsvars) ); 490 for( v = 0; v < nconsvars; ++v ) 491 consvals[v] = (SCIP_Real)w[v]; 492 493 if( nconsvars > 0 ) 494 { 495 SCIP_CALL( handleLinearCons(scip, consvars, consvals, nconsvars, transformed, &G) ); 496 } 497 SCIPfreeBufferArray(scip, &consvals); 498 } 499 else if( strcmp(conshdlrname, "varbound") == 0 ) 500 { 501 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, 2) ); 502 SCIP_CALL( SCIPallocBufferArray(scip, &consvals, 2) ); 503 504 consvars[0] = SCIPgetVarVarbound(scip, cons); 505 consvars[1] = SCIPgetVbdvarVarbound(scip, cons); 506 507 consvals[0] = 1.0; 508 consvals[1] = SCIPgetVbdcoefVarbound(scip, cons); 509 510 SCIP_CALL( handleLinearCons(scip, consvars, consvals, 2, transformed, &G) ); 511 512 SCIPfreeBufferArray(scip, &consvars); 513 SCIPfreeBufferArray(scip, &consvals); 514 } 515 else 516 { 517 SCIPwarningMessage(scip, "constraint handler <%s> cannot print requested format\n", conshdlrname ); 518 SCIPinfoMessage(scip, file, "\\ "); 519 SCIP_CALL( SCIPprintCons(scip, cons, file) ); 520 SCIPinfoMessage(scip, file, ";\n"); 521 } 522 } 523 524 /* output graph */ 525 SCIPinfoMessage(scip, file, "c graph generated from %s\n", name); 526 SCIPinfoMessage(scip, file, "p edge %d %u\n", nvars, G.m); 527 528 for( i = 0; i < nvars; ++i ) 529 { 530 unsigned int k; 531 int a; 532 533 k = 0; 534 a = G.A[i][k]; 535 while( a >= 0 ) 536 { 537 /* only output edges from lower to higher number */ 538 if( i < a ) 539 { 540 /* note: node numbers start with 1 in the DIMACS format */ 541 SCIPinfoMessage(scip, file, "e %d %d %f\n", i+1, a+1, G.W[i][k]); 542 } 543 544 a = G.A[i][++k]; 545 assert( k <= G.size[i] ); 546 } 547 assert( k == G.deg[i] ); 548 } 549 550 freeGraph(scip, &G); 551 552 *result = SCIP_SUCCESS; 553 554 return SCIP_OKAY; 555 } 556