Scippy

SCIP

Solving Constraint Integer Programs

reader_cnf.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_cnf.c
26 * @ingroup DEFPLUGINS_READER
27 * @brief CNF file reader
28 * @author Thorsten Koch
29 * @author Tobias Achterberg
30 *
31 * The DIMACS CNF (conjunctive normal form) is a file format used for example for SAT problems. For a detailed description of
32 * this format see http://people.sc.fsu.edu/~jburkardt/data/cnf/cnf.html .
33 */
34
35/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
36
38#include "scip/cons_linear.h"
39#include "scip/cons_logicor.h"
40#include "scip/cons_setppc.h"
41#include "scip/pub_fileio.h"
42#include "scip/pub_message.h"
43#include "scip/pub_misc.h"
44#include "scip/pub_reader.h"
45#include "scip/reader_cnf.h"
46#include "scip/scip_cons.h"
47#include "scip/scip_mem.h"
48#include "scip/scip_message.h"
49#include "scip/scip_numerics.h"
50#include "scip/scip_param.h"
51#include "scip/scip_prob.h"
52#include "scip/scip_reader.h"
53#include "scip/scip_var.h"
54#include <string.h>
55
56#define READER_NAME "cnfreader"
57#define READER_DESC "file reader for SAT problems in conjunctive normal form"
58#define READER_EXTENSION "cnf"
59
60#define MAXLINELEN 65536
61
62
63/*
64 * cnf reader internal methods
65 */
66
67static
69 SCIP* scip, /**< SCIP data structure */
70 int linecount, /**< line number of error */
71 const char* errormsg /**< error message */
72 )
73{
74 assert( scip != NULL );
75 SCIPerrorMessage("read error in line <%d>: %s\n", linecount, errormsg);
76}
77
78static
80 SCIP* scip, /**< SCIP data structure */
81 int linecount, /**< line number of error */
82 const char* warningmsg /**< warning message */
83 )
84{
85 SCIPwarningMessage(scip, "Line <%d>: %s\n", linecount, warningmsg);
86}
87
88/** reads the next non-empty non-comment line of a cnf file */
89static
91 SCIP* scip, /**< SCIP data structure */
92 SCIP_FILE* file, /**< input file */
93 char* buffer, /**< buffer for storing the input line */
94 int size, /**< size of the buffer */
95 int* linecount /**< pointer to the line number counter */
96 )
97{
98 char* line;
99 int linelen;
100
101 assert(file != NULL);
102 assert(buffer != NULL);
103 assert(size >= 2);
104 assert(linecount != NULL);
105
106 do
107 {
108 (*linecount)++;
109 line = SCIPfgets(buffer, size, file);
110 if( line != NULL )
111 {
112 linelen = (int)strlen(line);
113 if( linelen == size-1 )
114 {
115 char s[SCIP_MAXSTRLEN];
116 (void) SCIPsnprintf(s, SCIP_MAXSTRLEN, "line too long (exceeds %d characters)", size-2);
117 readError(scip, *linecount, s);
118 return SCIP_READERROR;
119 }
120 }
121 else
122 linelen = 0;
123 }
124 while( line != NULL && (*line == 'c' || *line == '\n') );
125
126 if( line != NULL && linelen >= 2 && line[linelen-2] == '\n' )
127 line[linelen-2] = '\0';
128 else if( linelen == 0 )
129 *buffer = '\0';
130
131 assert((line == NULL) == (*buffer == '\0'));
132
133 return SCIP_OKAY;
134}
135
136/* Read SAT formula in "CNF File Format".
137 *
138 * The specification is taken from the
139 *
140 * Satisfiability Suggested Format
141 *
142 * Online available at http://www.intellektik.informatik.tu-darmstadt.de/SATLIB/Benchmarks/SAT/satformat.ps
143 *
144 * The method reads all files of CNF format. Other formats (SAT, SATX, SATE) are not supported.
145 */
146static
148 SCIP* scip, /**< SCIP data structure */
149 SCIP_FILE* file /**< input file */
150 )
151{
152 SCIP_RETCODE retcode;
153 SCIP_VAR** vars;
154 SCIP_VAR** clausevars;
155 SCIP_CONS* cons;
156 int* varsign;
157 char* tok;
158 char* nexttok;
159 char line[MAXLINELEN];
160 char format[SCIP_MAXSTRLEN];
161 char varname[SCIP_MAXSTRLEN];
162 char s[SCIP_MAXSTRLEN];
163 SCIP_Bool initialconss;
164 SCIP_Bool dynamicconss;
165 SCIP_Bool dynamiccols;
166 SCIP_Bool dynamicrows;
167 SCIP_Bool useobj;
168 int linecount;
169 int clauselen;
170 int clausenum;
171 int nvars;
172 int nclauses;
173 int varnum;
174 int v;
175
176 assert(scip != NULL);
177 assert(file != NULL);
178
179 linecount = 0;
180
181 /* read header */
182 SCIP_CALL( readCnfLine(scip, file, line, (int) sizeof(line), &linecount) );
183 if( *line != 'p' )
184 {
185 readError(scip, linecount, "problem declaration line expected");
186 return SCIP_READERROR;
187 }
188 /* cppcheck-suppress invalidScanfFormatWidth_smaller */
189 if( sscanf(line, "p %8s %d %d", format, &nvars, &nclauses) != 3 )
190 {
191 readError(scip, linecount, "invalid problem declaration (must be 'p cnf <nvars> <nclauses>')");
192 return SCIP_READERROR;
193 }
194 if( strcmp(format, "cnf") != 0 )
195 {
196 (void) SCIPsnprintf(s, SCIP_MAXSTRLEN, "invalid format tag <%s> (must be 'cnf')", format);
197 readError(scip, linecount, s);
198 return SCIP_READERROR;
199 }
200 if( nvars <= 0 )
201 {
202 (void) SCIPsnprintf(s, SCIP_MAXSTRLEN, "invalid number of variables <%d> (must be positive)", nvars);
203 readError(scip, linecount, s);
204 return SCIP_READERROR;
205 }
206 if( nclauses <= 0 )
207 {
208 (void) SCIPsnprintf(s, SCIP_MAXSTRLEN, "invalid number of clauses <%d> (must be positive)", nclauses);
209 readError(scip, linecount, s);
210 return SCIP_READERROR;
211 }
212
213 /* get parameter values */
214 SCIP_CALL( SCIPgetBoolParam(scip, "reading/initialconss", &initialconss) );
215 SCIP_CALL( SCIPgetBoolParam(scip, "reading/dynamicconss", &dynamicconss) );
216 SCIP_CALL( SCIPgetBoolParam(scip, "reading/dynamiccols", &dynamiccols) );
217 SCIP_CALL( SCIPgetBoolParam(scip, "reading/dynamicrows", &dynamicrows) );
218 SCIP_CALL( SCIPgetBoolParam(scip, "reading/cnfreader/useobj", &useobj) );
219
220 /* get temporary memory */
221 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
222 SCIP_CALL( SCIPallocBufferArray(scip, &clausevars, nvars) );
223 SCIP_CALL( SCIPallocBufferArray(scip, &varsign, nvars) );
224
225 /* create the variables */
226 for( v = 0; v < nvars; ++v )
227 {
228 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "x%d", v+1);
229 SCIP_CALL( SCIPcreateVar(scip, &vars[v], varname, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY, !dynamiccols, dynamiccols,
230 NULL, NULL, NULL, NULL, NULL) );
231 SCIP_CALL( SCIPaddVar(scip, vars[v]) );
232 varsign[v] = 0;
233 }
234
235 /* read clauses */
236 clausenum = 0;
237 clauselen = 0;
238 do
239 {
240 retcode = readCnfLine(scip, file, line, (int) sizeof(line), &linecount);
241 if( retcode != SCIP_OKAY )
242 goto TERMINATE;
243
244 if( *line != '\0' && *line != '%' )
245 {
246 tok = SCIPstrtok(line, " \f\n\r\t", &nexttok);
247 while( tok != NULL )
248 {
249 /* parse literal and check for errors */
250 /* coverity[secure_coding] */
251 if( sscanf(tok, "%d", &v) != 1 )
252 {
253 (void) SCIPsnprintf(s, SCIP_MAXSTRLEN, "invalid literal <%s>", tok);
254 readError(scip, linecount, s);
255 retcode = SCIP_READERROR;
256 goto TERMINATE;
257 }
258
259 /* interpret literal number: v == 0: end of clause, v < 0: negated literal, v > 0: positive literal */
260 if( v == 0 )
261 {
262 /* end of clause: construct clause and add it to SCIP */
263 if( clauselen == 0 )
264 readWarning(scip, linecount, "empty clause detected in line -- problem infeasible");
265
266 clausenum++;
267 (void) SCIPsnprintf(s, SCIP_MAXSTRLEN, "c%d", clausenum);
268
269 if( SCIPfindConshdlr(scip, "logicor") != NULL )
270 {
271 /* if the constraint handler logicor exit create a logicor constraint */
272 SCIP_CALL( SCIPcreateConsLogicor(scip, &cons, s, clauselen, clausevars,
273 initialconss, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, dynamicconss, dynamicrows, FALSE) );
274 }
275 else if( SCIPfindConshdlr(scip, "setppc") != NULL )
276 {
277 /* if the constraint handler logicor does not exit but constraint
278 * handler setppc create a setppc constraint */
279 SCIP_CALL( SCIPcreateConsSetcover(scip, &cons, s, clauselen, clausevars,
280 initialconss, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, dynamicconss, dynamicrows, FALSE) );
281 }
282 else
283 {
284 /* if none of the previous constraint handler exits create a linear
285 * constraint */
286 SCIP_Real* vals;
287 int i;
288
289 SCIP_CALL( SCIPallocBufferArray(scip, &vals, clauselen) );
290
291 for( i = 0; i < clauselen; ++i )
292 vals[i] = 1.0;
293
294 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, s, clauselen, clausevars, vals, 1.0, SCIPinfinity(scip),
295 initialconss, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, dynamicconss, dynamicrows, FALSE) );
296
298 }
299
300 SCIP_CALL( SCIPaddCons(scip, cons) );
301 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
302 clauselen = 0;
303 }
304 else if( v >= -nvars && v <= nvars )
305 {
306 if( clauselen >= nvars )
307 {
308 readError(scip, linecount, "too many literals in clause");
309 retcode = SCIP_READERROR;
310 goto TERMINATE;
311 }
312
313 /* add literal to clause */
314 varnum = ABS(v)-1;
315 if( v < 0 )
316 {
317 SCIP_CALL( SCIPgetNegatedVar(scip, vars[varnum], &clausevars[clauselen]) );
318 varsign[varnum]--;
319 }
320 else
321 {
322 clausevars[clauselen] = vars[varnum];
323 varsign[varnum]++;
324 }
325 clauselen++;
326 }
327 else
328 {
329 (void) SCIPsnprintf(s, SCIP_MAXSTRLEN, "invalid variable number <%d>", ABS(v));
330 readError(scip, linecount, s);
331 retcode = SCIP_READERROR;
332 goto TERMINATE;
333 }
334
335 /* get next token */
336 tok = SCIPstrtok(NULL, " \f\n\r\t", &nexttok);
337 }
338 }
339 }
340 while( *line != '\0' && *line != '%' );
341
342 /* check for additional literals */
343 if( clauselen > 0 )
344 {
345 SCIPwarningMessage(scip, "found %d additional literals after last clause\n", clauselen);
346 }
347
348 /* check number of clauses */
349 if( clausenum != nclauses )
350 {
351 SCIPwarningMessage(scip, "expected %d clauses, but found %d\n", nclauses, clausenum);
352 }
353
354 TERMINATE:
355 /* change objective values and release variables */
357 for( v = 0; v < nvars; ++v )
358 {
359 if( useobj )
360 {
361 SCIP_CALL( SCIPchgVarObj(scip, vars[v], (SCIP_Real)varsign[v]) );
362 }
363 SCIP_CALL( SCIPreleaseVar(scip, &vars[v]) );
364 }
365
366 /* free temporary memory */
367 SCIPfreeBufferArray(scip, &varsign);
368 SCIPfreeBufferArray(scip, &clausevars);
370
371 return retcode;
372}
373
374
375/*
376 * Callback methods
377 */
378
379/** copy method for reader plugins (called when SCIP copies plugins) */
380static
382{ /*lint --e{715}*/
383 assert(scip != NULL);
384 assert(reader != NULL);
385 assert(strcmp(SCIPreaderGetName(reader), READER_NAME) == 0);
386
387 /* call inclusion method of reader */
389
390 return SCIP_OKAY;
391}
392
393
394/** problem reading method of reader */
395static
397{ /*lint --e{715}*/
398 SCIP_FILE* f;
399 SCIP_RETCODE retcode;
400
401 assert(reader != NULL);
402 assert(strcmp(SCIPreaderGetName(reader), READER_NAME) == 0);
403 assert(filename != NULL);
404 assert(result != NULL);
405
406 /* open file */
407 f = SCIPfopen(filename, "r");
408 if( f == NULL )
409 {
410 SCIPerrorMessage("cannot open file <%s> for reading\n", filename);
411 SCIPprintSysError(filename);
412 return SCIP_NOFILE;
413 }
414
415 /* create problem */
416 retcode = SCIPcreateProb(scip, filename, NULL, NULL, NULL, NULL, NULL, NULL, NULL);
417 if( retcode != SCIP_OKAY )
418 {
419 SCIPerrorMessage("Error creating problem for filename <%s>\n", filename);
420 SCIPfclose(f);
421 return retcode;
422 }
423
424 /* read cnf file */
425 retcode = readCnf(scip, f);
426
427 /* close file */
428 SCIPfclose(f);
429
430 *result = SCIP_SUCCESS;
431
432 return retcode;
433}
434
435
436/*
437 * cnf file reader specific interface methods
438 */
439
440/** includes the cnf file reader in SCIP */
442 SCIP* scip /**< SCIP data structure */
443 )
444{
445 SCIP_READER* reader;
446
447 /* include reader */
449
450 /* set non fundamental callbacks via setter functions */
451 SCIP_CALL( SCIPsetReaderCopy(scip, reader, readerCopyCnf) );
452 SCIP_CALL( SCIPsetReaderRead(scip, reader, readerReadCnf) );
453
454 /* add cnf reader parameters */
456 "reading/cnfreader/useobj", "should an artificial objective, depending on the number of clauses a variable appears in, be used?",
457 NULL, FALSE, FALSE, NULL, NULL) );
458
459 return SCIP_OKAY;
460}
461
Constraint handler for linear constraints in their most general form, .
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
Constraint handler for the set partitioning / packing / covering constraints .
#define NULL
Definition: def.h:267
#define SCIP_MAXSTRLEN
Definition: def.h:288
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
#define ABS(x)
Definition: def.h:235
#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
int SCIPfclose(SCIP_FILE *fp)
Definition: fileio.c:232
char * SCIPfgets(char *s, int size, SCIP_FILE *stream)
Definition: fileio.c:200
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPcreateConsLogicor(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPcreateConsSetcover(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_setppc.c:9467
SCIP_RETCODE SCIPincludeReaderCnf(SCIP *scip)
Definition: reader_cnf.c:441
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1668
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2770
SCIP_RETCODE SCIPsetObjsense(SCIP *scip, SCIP_OBJSENSE objsense)
Definition: scip_prob.c:1242
SCIP_RETCODE SCIPcreateProb(SCIP *scip, const char *name, SCIP_DECL_PROBDELORIG((*probdelorig)), SCIP_DECL_PROBTRANS((*probtrans)), SCIP_DECL_PROBDELTRANS((*probdeltrans)), SCIP_DECL_PROBINITSOL((*probinitsol)), SCIP_DECL_PROBEXITSOL((*probexitsol)), SCIP_DECL_PROBCOPY((*probcopy)), SCIP_PROBDATA *probdata)
Definition: scip_prob.c:117
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:250
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:941
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1174
#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_Real SCIPinfinity(SCIP *scip)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1248
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition: scip_var.c:1527
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 SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip_var.c:4513
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
void SCIPprintSysError(const char *message)
Definition: misc.c:10769
char * SCIPstrtok(char *s, const char *delim, char **ptrptr)
Definition: misc.c:10818
memory allocation routines
wrapper functions to map file i/o to standard or zlib file i/o
struct SCIP_File SCIP_FILE
Definition: pub_fileio.h:43
public methods for message output
#define SCIPerrorMessage
Definition: pub_message.h:64
public data structures and miscellaneous methods
public methods for input file readers
static void readError(SCIP *scip, int linecount, const char *errormsg)
Definition: reader_cnf.c:68
static SCIP_DECL_READERCOPY(readerCopyCnf)
Definition: reader_cnf.c:381
static SCIP_DECL_READERREAD(readerReadCnf)
Definition: reader_cnf.c:396
#define MAXLINELEN
Definition: reader_cnf.c:60
#define READER_DESC
Definition: reader_cnf.c:57
static SCIP_RETCODE readCnfLine(SCIP *scip, SCIP_FILE *file, char *buffer, int size, int *linecount)
Definition: reader_cnf.c:90
#define READER_EXTENSION
Definition: reader_cnf.c:58
#define READER_NAME
Definition: reader_cnf.c:56
static SCIP_RETCODE readCnf(SCIP *scip, SCIP_FILE *file)
Definition: reader_cnf.c:147
static void readWarning(SCIP *scip, int linecount, const char *warningmsg)
Definition: reader_cnf.c:79
CNF file reader.
public methods for constraint handler plugins and constraints
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for reader plugins
public methods for SCIP variables
@ SCIP_OBJSENSE_MAXIMIZE
Definition: type_prob.h:47
@ 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_VARTYPE_BINARY
Definition: type_var.h:62