Scippy

SCIP

Solving Constraint Integer Programs

reader_csol.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2024 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_csol.c
26 * @brief file reader and writer for vertex coloring solutions
27 * @author Gerald Gamrath
28 *
29 * This file implements the reader and writer for coloring solution files.
30 *
31 * These files have the following structure:@n The first line contains the name of the problem, the
32 * number of colors used in the solution, and - optional - the name of the algorithm that computed
33 * this solution. The second line lists the colors of the nodes, separated by spaces. It is sorted
34 * increasingly by the node indices. The numbers for the colors start with 0.
35 */
36
37/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
38
39#include <assert.h>
40#include <string.h>
41#include <ctype.h>
42#include <stdlib.h>
43
44#include "reader_csol.h"
45#include "reader_col.h"
46#include "probdata_coloring.h"
47
48
49#define READER_NAME "csolreader"
50#define READER_DESC "file reader which reads and writes csol-files"
51#define READER_EXTENSION "csol"
52
53#define COL_MAX_LINELEN 65535
54
55
56
57/*
58 * Local methods
59 */
60
61/** get next number from string s */
62static
64 char** s /**< pointer to the pointer of the current position in the string */
65 )
66{
67 long tmp;
68 /* skip whitespaces */
69 while ( isspace(**s) )
70 ++(*s);
71 /* read number */
72 tmp = atol(*s);
73 /* skip whitespaces */
74 while ( (**s != 0) && (!isspace(**s)) )
75 ++(*s);
76 return tmp;
77}
78
79
80/* put your local methods here, and declare them static */
81
82/** copy method for reader plugins (called when SCIP copies plugins) */
83static
84SCIP_DECL_READERCOPY(readerCopyCsol)
85{ /*lint --e{715}*/
86 assert(scip != NULL);
87 assert(reader != NULL);
88 assert(strcmp(SCIPreaderGetName(reader), READER_NAME) == 0);
89
90 return SCIP_OKAY;
91}
92
93/** problem reading method of reader */
94static
95SCIP_DECL_READERREAD(readerReadCsol)
96{
97 SCIP_FILE* fp; /* file-reader */
98 char buf[COL_MAX_LINELEN]; /* maximal length of line */
99 char* char_p;
100 char* solprobname;
101 const char* probname;
102
103 SCIP_Bool correctinstance;
104 TCLIQUE_GRAPH* graph;
105 SCIP_VAR* var;
106 SCIP_CONS** constraints;
107
108 int** sets;
109 int* setlengths;
110 int nsets;
111 int setindex;
112
113 int i;
114 int j;
115 int k;
116 int color;
117 int node;
118
119 assert(reader != NULL);
120 assert(strcmp(SCIPreaderGetName(reader), READER_NAME) == 0);
121 assert(scip != NULL);
122 assert(result != NULL);
123 assert(filename != NULL);
124 *result = SCIP_SUCCESS;
125
127 {
128 SCIPerrorMessage("Please read in problem before reading the solution!\n");
129 return SCIP_OKAY;
130 }
131
132 if (NULL == (fp = SCIPfopen(filename, "r")))
133 {
134 SCIPerrorMessage("cannot open file <%s> for reading\n", filename);
135 perror(filename);
136 return SCIP_NOFILE;
137 }
138
139 /* Read out the name of the problem belonging to this solution*/
140 if( SCIPfgets(buf, (int) sizeof(buf), fp) == NULL )
141 return SCIP_READERROR;
142
143 i = 1;
144 while ( !isspace(buf[i]) )
145 {
146 i++;
147 }
148 SCIP_CALL( SCIPallocBufferArray(scip, &solprobname, i+2) );
149 SCIPstrncpy(solprobname, buf, i);
150
151 printf("Reading solution for %s...\n", solprobname);
152
153 /* get the name of the current problem */
154 probname = SCIPgetProbName(scip);
155
156 /* check whether the solution belongs to the current problem */
157 correctinstance = TRUE;
158 for ( j = 0; j <= i; j++ )
159 {
160 if ( solprobname[j] != probname[j] )
161 {
162 correctinstance = FALSE;
163 }
164 }
165 if ( !correctinstance )
166 {
167 SCIPerrorMessage("The selected solution file doesn't belong to the current problem!\n");
168 return SCIP_OKAY;
169 }
170
171 /* get the graph of the current problem */
172 graph = COLORprobGetGraph(scip);
173 assert(graph != NULL);
174
175 /* read out number of colors */
176 char_p = &buf[i];
177 nsets = (int) getNextNumber(&char_p);
178 assert(nsets > 0);
179
180 /* allocate memory for the stable sets */
181 SCIP_CALL( SCIPallocBufferArray(scip, &sets, nsets) );
182 SCIP_CALL( SCIPallocBufferArray(scip, &setlengths, nsets) );
183 for ( i = 0; i < nsets; i++ )
184 {
185 int size;
186
188 SCIP_CALL( SCIPallocBufferArray(scip, &(sets[i]), size) ); /*lint !e866*/
189 setlengths[i] = 0;
190 }
191
192 /* read out the colors for the nodes */
193 SCIPfgets(buf, (int) sizeof(buf), fp); /*lint !e534*/
194 char_p = &buf[0];
195 for ( i = 0; i < COLORprobGetOriginalNNodes(scip); i++ )
196 {
197 color = (int) getNextNumber(&char_p);
198 sets[color][setlengths[color]] = i;
199 sets[color][setlengths[color]+1] = -1;
200 setlengths[color]++;
201 }
202
203 /* the given coloring is a coloring for the original graph, now transform it into a coloring for the transformed graph */
204 for ( i = 0; i < nsets; i++ )
205 {
206 j = 0;
207 k = 0;
208 while ( sets[i][j] != -1 )
209 {
210 node = COLORprobGetNewNodeForOriginalNode(scip, sets[i][j]);
211 if ( node == -1 )
212 {
213 j++;
214 }
215 else
216 {
217 sets[i][k] = node;
218 setlengths[i] = k+1;
219 k++;
220 j++;
221 }
222 }
223 while ( k < j )
224 {
225 sets[i][k] = -1;
226 k++;
227 }
228 }
229
230 printf("testing validity...\n");
231 /* check solution */
232 for ( i = 0; i < nsets; i++ )
233 {
234 for ( j = 0; j < setlengths[i]; j++ )
235 {
236 for ( k = j+1; k < setlengths[i]; k++ )
237 {
238 if ( tcliqueIsEdge(graph, sets[i][j], sets[i][k]) )
239 {
240 SCIPerrorMessage("The solution is not valid!\n");
241 return SCIP_OKAY;
242 }
243 }
244 }
245 }
246 printf("valid!\n");
247
248 /* get the node-constraits */
249 constraints = COLORprobGetConstraints(scip);
250 assert(constraints != NULL);
251 /* try to add nodes to the stable sets */
252 for ( i = 0; i < nsets; i++ )
253 {
254 for ( node = 0; node < COLORprobGetNNodes(scip); node++ )
255 {
256 for ( j = 0; j < setlengths[i]; j++ )
257 {
258 if ( sets[i][j] == node )
259 {
260 break;
261 }
262 if ( tcliqueIsEdge(graph, sets[i][j], node) )
263 {
264 break;
265 }
266 }
267 if ( j == setlengths[i] )
268 {
269 sets[i][setlengths[i]] = node;
270 sets[i][setlengths[i]+1] = -1;
271 setlengths[i]++;
272 }
273 }
274 }
275
276 /* sort the sets and add them to the problem, creating one variable for each set */
277 for ( i = 0; i < nsets; i++ )
278 {
279 SCIPsortDownInt(sets[i], setlengths[i]);
280 SCIP_CALL( COLORprobAddNewStableSet(scip, sets[i], setlengths[i], &setindex) );
281 assert(setindex == i);
282
283 SCIP_CALL( SCIPcreateVar(scip, &var, NULL, 0.0, 1.0, 1.0, SCIP_VARTYPE_BINARY,
284 TRUE, FALSE, NULL, NULL, NULL, NULL, (SCIP_VARDATA*)(size_t)setindex) ); /*lint !e571*/
285
286 SCIP_CALL( COLORprobAddVarForStableSet(scip, setindex, var) );
287 SCIP_CALL( SCIPaddVar(scip, var) );
288 SCIP_CALL( SCIPchgVarUbLazy(scip, var, 1.0) );
289
290 /* add variable to node constraints of nodes in the set */
291 for ( j = 0; j < setlengths[i]; j++ )
292 {
293 SCIP_CALL( SCIPaddCoefSetppc(scip, constraints[sets[i][j]], var) );
294 }
295
296 }
297
298
299 /* free memory for the stable sets */
300 for ( i = nsets-1; i >= 0; i-- )
301 {
302 SCIPfreeBufferArray(scip, &(sets[i]));
303 }
304 SCIPfreeBufferArray(scip, &setlengths);
306 SCIPfreeBufferArray(scip, &solprobname);
307
308 return SCIP_OKAY;
309}
310
311
312
313
314/*
315 * Callback methods of reader
316 */
317
318/** problem writing method of reader */
319static
320SCIP_DECL_READERWRITE(readerWriteCsol)
321{
322 SCIP_SOL* sol;
323 SCIP_Bool colorpossible;
324 TCLIQUE_GRAPH* oldgraph;
325 int** sets;
326 int* nsetelements;
327 int nsets;
328 int nnodes;
329 int i;
330 int j;
331 int actcolor;
332 int node;
333 int* originalnodes;
334 int* deletednodes;
335 int* firstedge;
336 int* lastedge;
337 int* colors;
338
339 *result = SCIP_DIDNOTRUN;
340
341 /* get the data of the original graph, the preprocessing information and the array stable sets in the preprocessed graph */
344 assert(originalnodes != NULL);
345 deletednodes = COLORprobGetDeletedNodes(scip);
346 assert(deletednodes != NULL);
348 COLORprobGetStableSets(scip, &sets, &nsetelements, &nsets);
349 assert(sets != NULL && nsetelements != NULL);
350
351 /* get the solution */
352 sol = SCIPgetBestSol(scip);
353
354 /* create array for the colors of the nodes and initialize it with -1 */
356 for ( i = 0; i < nnodes; i++ )
357 {
358 colors[i] = -1;
359 }
360
361 /* for all stable sets in the solution, color all nodes, that are in the set and not yet colored with the same, new color */
362 actcolor = 0;
363 for ( i = 0; i < nsets; i++ )
364 {
366 {
367 assert(SCIPgetSolVal( scip, sol, COLORprobGetVarForStableSet(scip, i)) == 1);
368 for ( j = 0; j < nsetelements[i]; j++ )
369 {
370 if ( colors[originalnodes[sets[i][j]]] == -1 )
371 {
372 colors[originalnodes[sets[i][j]]] = actcolor;
373 }
374 }
375 actcolor++;
376 }
377 }
378
379 /* set i to the index of the last node deleted during preprocessing */
381 while ( deletednodes[i] == -1 )
382 {
383 i--;
384 }
385
386 /*compute colors for nodes deleted during preprocessing */
387 while ( i >= 0 )
388 {
389 node = deletednodes[i];
390 j = 0;
391 while ( colors[node] == -1 )
392 {
393 colorpossible = TRUE;
394 firstedge = tcliqueGetFirstAdjedge(oldgraph, node);
395 lastedge = tcliqueGetLastAdjedge(oldgraph, node);
396 while ( firstedge <= lastedge )
397 {
398 if ( colors[*firstedge] == j )
399 {
400 colorpossible = FALSE;
401 break;
402 }
403 firstedge++;
404 }
405 if ( colorpossible == TRUE )
406 {
407 colors[node] = j;
408 }
409 else
410 {
411 j++;
412 }
413 }
414 i--;
415 }
416
417 SCIPinfoMessage(scip, file, "%s %d generated by ColumnGenerationColoring\n", name, actcolor);
418 for ( i = 0; i < nnodes; i++ )
419 {
420 SCIPinfoMessage(scip, file, "%d ", colors[i]);
421 }
422
423 SCIPfreeBufferArray(scip, &colors);
424
425 *result = SCIP_SUCCESS;
426
427 return SCIP_OKAY;
428}/*lint !e715*/
429
430
431/*
432 * reader specific interface methods
433 */
434
435/** includes the csol file reader in SCIP */
437 SCIP* scip /**< SCIP data structure */
438 )
439{
440 SCIP_READERDATA* readerdata;
441 SCIP_READER* reader;
442
443 /* create csol reader data */
444 readerdata = NULL;
445
446 /* include csol reader */
448 readerdata) );
449
450 SCIP_CALL( SCIPsetReaderCopy(scip, reader, readerCopyCsol) );
451 SCIP_CALL( SCIPsetReaderRead(scip, reader, readerReadCsol) );
452 SCIP_CALL( SCIPsetReaderWrite(scip, reader, readerWriteCsol) );
453
454 return SCIP_OKAY;
455}
#define NULL
Definition: def.h:267
#define SCIP_Bool
Definition: def.h:91
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_FILE * SCIPfopen(const char *path, const char *mode)
Definition: fileio.c:153
char * SCIPfgets(char *s, int size, SCIP_FILE *stream)
Definition: fileio.c:200
#define nnodes
Definition: gastrans.c:74
SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_setppc.c:9522
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:380
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1668
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1067
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
SCIP_RETCODE SCIPincludeReaderBasic(SCIP *scip, SCIP_READER **readerptr, const char *name, const char *desc, const char *extension, SCIP_READERDATA *readerdata)
Definition: scip_reader.c:109
SCIP_RETCODE SCIPsetReaderCopy(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERCOPY((*readercopy)))
Definition: scip_reader.c:147
const char * SCIPreaderGetName(SCIP_READER *reader)
Definition: reader.c:557
SCIP_RETCODE SCIPsetReaderRead(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERREAD((*readerread)))
Definition: scip_reader.c:195
SCIP_RETCODE SCIPsetReaderWrite(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERWRITE((*readerwrite)))
Definition: scip_reader.c:219
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2169
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
Definition: scip_var.c:114
SCIP_RETCODE SCIPchgVarUbLazy(SCIP *scip, SCIP_VAR *var, SCIP_Real lazyub)
Definition: scip_var.c:5164
void SCIPsortDownInt(int *intarray, int len)
int SCIPstrncpy(char *t, const char *s, int size)
Definition: misc.c:10919
int COLORprobGetNewNodeForOriginalNode(SCIP *scip, int node)
TCLIQUE_GRAPH * COLORprobGetOriginalGraph(SCIP *scip)
SCIP_CONS ** COLORprobGetConstraints(SCIP *scip)
SCIP_RETCODE COLORprobAddNewStableSet(SCIP *scip, int *stablesetnodes, int nstablesetnodes, int *setindex)
int * COLORprobGetOriginalNodesForNewNodes(SCIP *scip)
int COLORprobGetNNodes(SCIP *scip)
int COLORprobGetOriginalNNodes(SCIP *scip)
SCIP_VAR * COLORprobGetVarForStableSet(SCIP *scip, int setindex)
void COLORprobGetStableSets(SCIP *scip, int ***stablesets, int **nelements, int *nstablesets)
TCLIQUE_GRAPH * COLORprobGetGraph(SCIP *scip)
SCIP_RETCODE COLORprobAddVarForStableSet(SCIP *scip, int setindex, SCIP_VAR *var)
int * COLORprobGetDeletedNodes(SCIP *scip)
problem data for vertex coloring algorithm
struct SCIP_File SCIP_FILE
Definition: pub_fileio.h:43
#define SCIPerrorMessage
Definition: pub_message.h:64
file reader for vertex coloring instances
static SCIP_DECL_READERWRITE(readerWriteCsol)
Definition: reader_csol.c:320
static SCIP_DECL_READERCOPY(readerCopyCsol)
Definition: reader_csol.c:84
#define READER_DESC
Definition: reader_csol.c:50
#define COL_MAX_LINELEN
Definition: reader_csol.c:53
#define READER_EXTENSION
Definition: reader_csol.c:51
SCIP_RETCODE SCIPincludeReaderCsol(SCIP *scip)
Definition: reader_csol.c:436
#define READER_NAME
Definition: reader_csol.c:49
static SCIP_DECL_READERREAD(readerReadCsol)
Definition: reader_csol.c:95
static long getNextNumber(char **s)
Definition: reader_csol.c:63
file reader and writer for vertex coloring solutions
int * tcliqueGetLastAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
int * tcliqueGetFirstAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
struct TCLIQUE_Graph TCLIQUE_GRAPH
Definition: tclique.h:49
struct SCIP_ReaderData SCIP_READERDATA
Definition: type_reader.h:53
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_SUCCESS
Definition: type_result.h:58
@ SCIP_NOFILE
Definition: type_retcode.h:47
@ SCIP_READERROR
Definition: type_retcode.h:45
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_STAGE_INIT
Definition: type_set.h:44
struct SCIP_VarData SCIP_VARDATA
Definition: type_var.h:120
@ SCIP_VARTYPE_BINARY
Definition: type_var.h:62