1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file reader_opb.c
17 * @ingroup DEFPLUGINS_READER
18 * @brief pseudo-Boolean file reader (opb format)
19 * @author Stefan Heinz
20 * @author Michael Winkler
21 *
22 * This file reader parses the @a opb format and is also used by the @a wbo reader for the @a wbo format. For a
23 * detailed description of this format see
24 *
25 * - http://www.cril.univ-artois.fr/PB07/solver_req.html
26 * - http://www.cril.univ-artois.fr/PB10/format.pdf
27 *
28 * The syntax of the input file format can be described by a simple Backus-Naur
29 * form. \<formula\> is the start symbol of this grammar.
30 *
31 * \<formula\>::= \<sequence_of_comments\>
32 * [\<objective\>] | [\<softheader\>]
33 * \<sequence_of_comments_or_constraints\>
34 *
35 * \<sequence_of_comments\>::= \<comment\> [\<sequence_of_comments\>]
36 * \<comment\>::= "*" \<any_sequence_of_characters_other_than_EOL\> \<EOL\>
37 * \<sequence_of_comments_or_constraints\>::=\<comment_or_constraint\> [\<sequence_of_comments_or_constraints\>]
38 * \<comment_or_constraint\>::=\<comment\>|\<constraint\>
39 *
40 * \<objective\>::= "min:" \<zeroOrMoreSpace\> \<sum\> ";"
41 * \<constraint\>::= \<sum\> \<relational_operator\> \<zeroOrMoreSpace\> \<integer\> \<zeroOrMoreSpace\> ";"
42 *
43 * \<sum\>::= \<weightedterm\> | \<weightedterm\> \<sum\>
44 * \<weightedterm\>::= \<integer\> \<oneOrMoreSpace\> \<term\> \<oneOrMoreSpace\>
45 *
46 * \<integer\>::= \<unsigned_integer\> | "+" \<unsigned_integer\> | "-" \<unsigned_integer\>
47 * \<unsigned_integer\>::= \<digit\> | \<digit\>\<unsigned_integer\>
48 *
49 * \<relational_operator\>::= "\>=" | "="
50 *
51 * \<variablename\>::= "x" \<unsigned_integer\>
52 *
53 * \<oneOrMoreSpace\>::= " " [\<oneOrMoreSpace\>]
54 * \<zeroOrMoreSpace\>::= [" " \<zeroOrMoreSpace\>]
55 *
56 * For linear pseudo-Boolean instances, \<term\> is defined as
57 *
58 * \<term\>::=\<variablename\>
59 *
60 * For non-linear instances, \<term\> is defined as
61 *
62 * \<term\>::= \<oneOrMoreLiterals\>
63 * \<oneOrMoreLiterals\>::= \<literal\> | \<literal\> \<oneOrMoreSpace\> \<oneOrMoreLiterals\>
64 * \<literal\>::= \<variablename\> | "~"\<variablename\>
65 *
66 * For wbo-files are the following additional/changed things possible.
67 *
68 * \<softheader\>::= "soft:" [\<unsigned integer\>] ";"
69 *
70 * \<comment_or_constraint\>::=\<comment\>|\<constraint\>|\<softconstraint\>
71 *
72 * \<softconstraint\>::= "[" \<zeroOrMoreSpace\> \<unsigned integer\> \<zeroOrMoreSpace\> "]" \<constraint\>
73 *
74 */
75
76 /* Our parser should also be lax by handling variable names and it's possible to read doubles instead of integer and
77 * possible some more :). */
78
79 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
80
81 #include "blockmemshell/memory.h"
82 #include <ctype.h>
83 #include "scip/cons_and.h"
84 #include "scip/cons_indicator.h"
85 #include "scip/cons_knapsack.h"
86 #include "scip/cons_linear.h"
87 #include "scip/cons_logicor.h"
88 #include "scip/cons_pseudoboolean.h"
89 #include "scip/cons_setppc.h"
90 #include "scip/cons_varbound.h"
91 #include "scip/debug.h"
92 #include "scip/pub_cons.h"
93 #include "scip/pub_fileio.h"
94 #include "scip/pub_message.h"
95 #include "scip/pub_misc.h"
96 #include "scip/pub_misc_sort.h"
97 #include "scip/pub_reader.h"
98 #include "scip/pub_var.h"
99 #include "scip/reader_opb.h"
100 #include "scip/scip_cons.h"
101 #include "scip/scip_mem.h"
102 #include "scip/scip_message.h"
103 #include "scip/scip_numerics.h"
104 #include "scip/scip_param.h"
105 #include "scip/scip_prob.h"
106 #include "scip/scip_reader.h"
107 #include "scip/scip_solvingstats.h"
108 #include "scip/scip_var.h"
109 #include <stdlib.h>
110 #include <string.h>
111
112 #if !defined(_WIN32) && !defined(_WIN64)
113 #include <strings.h> /*lint --e{766}*/ /* needed for strncasecmp() */
114 #endif
115
116 #define READER_NAME "opbreader"
117 #define READER_DESC "file reader for pseudo-Boolean problem in opb format"
118 #define READER_EXTENSION "opb"
119
120 #define GENCONSNAMES TRUE /* remove if no constraint names should be generated */
121 #define LINEAROBJECTIVE TRUE /* will all non-linear parts inside the objective function be linearized or will
122 * an artificial integer variable be created which will represent the objective
123 * function
124 */
125
126 #define INDICATORVARNAME "indicatorvar" /* standard part of name for all indicator variables */
127 #define INDICATORSLACKVARNAME "indslack" /* standard part of name for all indicator slack variables; should be the same in cons_indicator */
128 #define TOPCOSTCONSNAME "topcostcons" /* standard name for artificial topcost constraint in wbo problems */
129
130 /*
131 * Data structures
132 */
133 #define OPB_MAX_LINELEN 65536 /**< size of the line buffer for reading or writing */
134 #define OPB_MAX_PUSHEDTOKENS 2
135 #define OPB_INIT_COEFSSIZE 8192
136
137 /** Section in OPB File */
138 enum OpbExpType
139 {
140 OPB_EXP_NONE,
141 OPB_EXP_UNSIGNED,
142 OPB_EXP_SIGNED
143 };
144 typedef enum OpbExpType OPBEXPTYPE;
145
146 enum OpbSense
147 {
148 OPB_SENSE_NOTHING,
149 OPB_SENSE_LE,
150 OPB_SENSE_GE,
151 OPB_SENSE_EQ
152 };
153 typedef enum OpbSense OPBSENSE;
154
155 /** OPB reading data */
156 struct OpbInput
157 {
158 SCIP_FILE* file;
159 char* linebuf;
160 char* token;
161 char* tokenbuf;
162 char* pushedtokens[OPB_MAX_PUSHEDTOKENS];
163 int npushedtokens;
164 int linenumber;
165 int linepos;
166 int linebufsize;
167 SCIP_OBJSENSE objsense;
168 SCIP_Bool eof;
169 SCIP_Bool haserror;
170 int nproblemcoeffs;
171 SCIP_Bool wbo;
172 SCIP_Real topcost;
173 int nindvars;
174 #if GENCONSNAMES == TRUE
175 int consnumber;
176 #endif
177 };
178
179 typedef struct OpbInput OPBINPUT;
180
181 static const char commentchars[] = "*";
182 /*
183 * Local methods (for reading)
184 */
185
186 /** issues an error message and marks the OPB data to have errors */
187 static
188 void syntaxError(
189 SCIP* scip, /**< SCIP data structure */
190 OPBINPUT* opbinput, /**< OPB reading data */
191 const char* msg /**< error message */
192 )
193 {
194 assert(scip != NULL);
195 assert(opbinput != NULL);
196
197 SCIPerrorMessage("Syntax error in line %d: %s found <%s>\n", opbinput->linenumber, msg, opbinput->token);
198 if( opbinput->linebuf[opbinput->linebufsize - 1] == '\n' )
199 {
200 SCIPerrorMessage(" input: %s", opbinput->linebuf);
201 }
202 else
203 {
204 SCIPerrorMessage(" input: %s\n", opbinput->linebuf);
205 }
206
207 opbinput->haserror = TRUE;
208 }
209
210 /** returns whether a syntax error was detected */
211 static
212 SCIP_Bool hasError(
213 OPBINPUT* opbinput /**< OPB reading data */
214 )
215 {
216 assert(opbinput != NULL);
217
218 return opbinput->haserror;
219 }
220
221 /** returns whether the given character is a token delimiter */
222 static
223 SCIP_Bool isDelimChar(
224 char c /**< input character */
225 )
226 {
227 switch (c)
228 {
229 case ' ':
230 case '\f':
231 case '\n':
232 case '\r':
233 case '\t':
234 case '\v':
235 case '\0':
236 return TRUE;
237 default:
238 return FALSE;
239 }
240 }
241
242 /** returns whether the given character is a single token */
243 static
244 SCIP_Bool isTokenChar(
245 char c /**< input character */
246 )
247 {
248 switch (c)
249 {
250 case '-':
251 case '+':
252 case ':':
253 case '<':
254 case '>':
255 case '=':
256 case '[':
257 case ']':
258 case ';':
259 return TRUE;
260 default:
261 return FALSE;
262 }
263 }
264
265 /** returns whether the current character is member of a value string */
266 static
267 SCIP_Bool isValueChar(
268 char c, /**< input character */
269 char nextc, /**< next input character */
270 SCIP_Bool firstchar, /**< is the given character the first char of the token? */
271 SCIP_Bool* hasdot, /**< pointer to update the dot flag */
272 OPBEXPTYPE* exptype /**< pointer to update the exponent type */
273 )
274 {
275 assert(hasdot != NULL);
276 assert(exptype != NULL);
277
278 if( isdigit((unsigned char)c) )
279 return TRUE;
280 else if( (*exptype == OPB_EXP_NONE) && !(*hasdot) && (c == '.') )
281 {
282 *hasdot = TRUE;
283 return TRUE;
284 }
285 else if( !firstchar && (*exptype == OPB_EXP_NONE) && (c == 'e' || c == 'E') )
286 {
287 if( nextc == '+' || nextc == '-' )
288 {
289 *exptype = OPB_EXP_SIGNED;
290 return TRUE;
291 }
292 else if( isdigit((unsigned char)nextc) )
293 {
294 *exptype = OPB_EXP_UNSIGNED;
295 return TRUE;
296 }
297 }
298 else if( (*exptype == OPB_EXP_SIGNED) && (c == '+' || c == '-') )
299 {
300 *exptype = OPB_EXP_UNSIGNED;
301 return TRUE;
302 }
303
304 return FALSE;
305 }
306
307 /** reads the next line from the input file into the line buffer; skips comments;
308 * returns whether a line could be read
309 */
310 static
311 SCIP_Bool getNextLine(
312 SCIP* scip, /**< SCIP data structure */
313 OPBINPUT* opbinput /**< OPB reading data */
314 )
315 {
316 int i;
317
318 assert(opbinput != NULL);
319
320 /* read next line */
321 opbinput->linepos = 0;
322 opbinput->linebuf[opbinput->linebufsize - 2] = '\0';
323
324 if( SCIPfgets(opbinput->linebuf, opbinput->linebufsize, opbinput->file) == NULL )
325 return FALSE;
326
327 opbinput->linenumber++;
328
329 /* if line is too long for our buffer reallocate buffer */
330 while( opbinput->linebuf[opbinput->linebufsize - 2] != '\0' )
331 {
332 int newsize;
333
334 newsize = SCIPcalcMemGrowSize(scip, opbinput->linebufsize + 1);
335 SCIP_CALL_ABORT( SCIPreallocBlockMemoryArray(scip, &opbinput->linebuf, opbinput->linebufsize, newsize) );
336
337 opbinput->linebuf[newsize-2] = '\0';
338 if ( SCIPfgets(opbinput->linebuf + opbinput->linebufsize - 1, newsize - opbinput->linebufsize + 1, opbinput->file) == NULL )
339 return FALSE;
340 opbinput->linebufsize = newsize;
341 }
342
343 opbinput->linebuf[opbinput->linebufsize - 1] = '\0'; /* we want to use lookahead of one char -> we need two \0 at the end */
344
345 /* skip characters after comment symbol */
346 for( i = 0; commentchars[i] != '\0'; ++i )
347 {
348 char* commentstart;
349
350 commentstart = strchr(opbinput->linebuf, commentchars[i]);
351 if( commentstart != NULL )
352 {
353 *commentstart = '\0';
354 *(commentstart+1) = '\0'; /* we want to use lookahead of one char -> we need two \0 at the end */
355 break;
356 }
357 }
358
359 SCIPdebugMsg(scip, "%s\n", opbinput->linebuf);
360
361 return TRUE;
362 }
363
364 /** swaps the addresses of two pointers */
365 static
366 void swapPointers(
367 char** pointer1, /**< first pointer */
368 char** pointer2 /**< second pointer */
369 )
370 {
371 char* tmp;
372
373 tmp = *pointer1;
374 *pointer1 = *pointer2;
375 *pointer2 = tmp;
376 }
377
378 /** reads the next token from the input file into the token buffer; returns whether a token was read */
379 static
380 SCIP_Bool getNextToken(
381 SCIP* scip, /**< SCIP data structure */
382 OPBINPUT* opbinput /**< OPB reading data */
383 )
384 {
385 SCIP_Bool hasdot;
386 OPBEXPTYPE exptype;
387 char* buf;
388 int tokenlen;
389
390 assert(opbinput != NULL);
391 assert(opbinput->linepos < opbinput->linebufsize);
392
393 /* check the token stack */
394 if( opbinput->npushedtokens > 0 )
395 {
396 swapPointers(&opbinput->token, &opbinput->pushedtokens[opbinput->npushedtokens-1]);
397 opbinput->npushedtokens--;
398 SCIPdebugMsg(scip, "(line %d) read token again: '%s'\n", opbinput->linenumber, opbinput->token);
399 return TRUE;
400 }
401
402 /* skip delimiters */
403 buf = opbinput->linebuf;
404 while( isDelimChar(buf[opbinput->linepos]) )
405 {
406 if( buf[opbinput->linepos] == '\0' )
407 {
408 if( !getNextLine(scip, opbinput) )
409 {
410 SCIPdebugMsg(scip, "(line %d) end of file\n", opbinput->linenumber);
411 return FALSE;
412 }
413 assert(opbinput->linepos == 0);
414 /* update buf, because the linebuffer may have been reallocated */
415 buf = opbinput->linebuf;
416 }
417 else
418 opbinput->linepos++;
419 }
420 assert(opbinput->linepos < opbinput->linebufsize);
421 assert(!isDelimChar(buf[opbinput->linepos]));
422
423 /* check if the token is a value */
424 hasdot = FALSE;
425 exptype = OPB_EXP_NONE;
426 if( isValueChar(buf[opbinput->linepos], buf[opbinput->linepos+1], TRUE, &hasdot, &exptype) )
427 {
428 /* read value token */
429 tokenlen = 0;
430 do
431 {
432 assert(tokenlen < OPB_MAX_LINELEN);
433 assert(!isDelimChar(buf[opbinput->linepos]));
434 opbinput->token[tokenlen] = buf[opbinput->linepos];
435 tokenlen++;
436 opbinput->linepos++;
437 }
438 while( isValueChar(buf[opbinput->linepos], buf[opbinput->linepos+1], FALSE, &hasdot, &exptype) );
439 }
440 else
441 {
442 /* read non-value token */
443 tokenlen = 0;
444 do
445 {
446 assert(tokenlen < OPB_MAX_LINELEN);
447 opbinput->token[tokenlen] = buf[opbinput->linepos];
448 tokenlen++;
449 opbinput->linepos++;
450 if( tokenlen == 1 && isTokenChar(opbinput->token[0]) )
451 break;
452 }
453 while( !isDelimChar(buf[opbinput->linepos]) && !isTokenChar(buf[opbinput->linepos]) );
454
455 /* if the token is an equation sense '<', '>', or '=', skip a following '='
456 * if the token is an equality token '=' and the next character is a '<' or '>',
457 * replace the token by the inequality sense
458 */
459 if( tokenlen >= 1
460 && (opbinput->token[tokenlen-1] == '<' || opbinput->token[tokenlen-1] == '>' || opbinput->token[tokenlen-1] == '=')
461 && buf[opbinput->linepos] == '=' )
462 {
463 opbinput->linepos++;
464 }
465 else if( opbinput->token[tokenlen-1] == '=' && (buf[opbinput->linepos] == '<' || buf[opbinput->linepos] == '>') )
466 {
467 opbinput->token[tokenlen-1] = buf[opbinput->linepos];
468 opbinput->linepos++;
469 }
470 }
471 assert(tokenlen < OPB_MAX_LINELEN);
472 opbinput->token[tokenlen] = '\0';
473
474 SCIPdebugMsg(scip, "(line %d) read token: '%s'\n", opbinput->linenumber, opbinput->token);
475
476 return TRUE;
477 }
478
479 /** puts the current token on the token stack, such that it is read at the next call to getNextToken() */
480 static
481 void pushToken(
482 OPBINPUT* opbinput /**< OPB reading data */
483 )
484 {
485 assert(opbinput != NULL);
486 assert(opbinput->npushedtokens < OPB_MAX_PUSHEDTOKENS);
487
488 swapPointers(&opbinput->pushedtokens[opbinput->npushedtokens], &opbinput->token);
489 opbinput->npushedtokens++;
490 }
491
492 /** puts the buffered token on the token stack, such that it is read at the next call to getNextToken() */
493 static
494 void pushBufferToken(
495 OPBINPUT* opbinput /**< OPB reading data */
496 )
497 {
498 assert(opbinput != NULL);
499 assert(opbinput->npushedtokens < OPB_MAX_PUSHEDTOKENS);
500
501 swapPointers(&opbinput->pushedtokens[opbinput->npushedtokens], &opbinput->tokenbuf);
502 opbinput->npushedtokens++;
503 }
504
505 /** swaps the current token with the token buffer */
506 static
507 void swapTokenBuffer(
508 OPBINPUT* opbinput /**< OPB reading data */
509 )
510 {
511 assert(opbinput != NULL);
512
513 swapPointers(&opbinput->token, &opbinput->tokenbuf);
514 }
515
516 /** checks whether the current token is a section identifier, and if yes, switches to the corresponding section */
517 static
518 SCIP_Bool isEndLine(
519 OPBINPUT* opbinput /**< OPB reading data */
520 )
521 {
522 assert(opbinput != NULL);
523
524 if( *(opbinput->token) == ';')
525 return TRUE;
526
527 return FALSE;
528 }
529
530 /** returns whether the current token is a sign */
531 static
532 SCIP_Bool isSign(
533 OPBINPUT* opbinput, /**< OPB reading data */
534 int* sign /**< pointer to update the sign */
535 )
536 {
537 assert(opbinput != NULL);
538 assert(sign != NULL);
539 assert(*sign == +1 || *sign == -1);
540
541 if( strlen(opbinput->token) == 1 )
542 {
543 assert(opbinput->token[1] == '\0');
544
545 if( *opbinput->token == '+' )
546 return TRUE;
547 else if( *opbinput->token == '-' )
548 {
549 *sign *= -1;
550 return TRUE;
551 }
552 }
553
554 return FALSE;
555 }
556
557 /** returns whether the current token is a value */
558 static
559 SCIP_Bool isValue(
560 SCIP* scip, /**< SCIP data structure */
561 OPBINPUT* opbinput, /**< OPB reading data */
562 SCIP_Real* value /**< pointer to store the value (unchanged, if token is no value) */
563 )
564 {
565 assert(opbinput != NULL);
566 assert(value != NULL);
567
568 if( strcasecmp(opbinput->token, "INFINITY") == 0 || strcasecmp(opbinput->token, "INF") == 0 )
569 {
570 *value = SCIPinfinity(scip);
571 return TRUE;
572 }
573 else
574 {
575 double val;
576 char* endptr;
577
578 val = strtod(opbinput->token, &endptr);
579 if( endptr != opbinput->token && *endptr == '\0' )
580 {
581 *value = val;
582 if( strlen(opbinput->token) > 18 )
583 opbinput->nproblemcoeffs++;
584 return TRUE;
585 }
586 }
587
588 return FALSE;
589 }
590
591 /** returns whether the current token is an equation sense */
592 static
593 SCIP_Bool isSense(
594 OPBINPUT* opbinput, /**< OPB reading data */
595 OPBSENSE* sense /**< pointer to store the equation sense, or NULL */
596 )
597 {
598 assert(opbinput != NULL);
599
600 if( strcmp(opbinput->token, "<") == 0 )
601 {
602 if( sense != NULL )
603 *sense = OPB_SENSE_LE;
604 return TRUE;
605 }
606 else if( strcmp(opbinput->token, ">") == 0 )
607 {
608 if( sense != NULL )
609 *sense = OPB_SENSE_GE;
610 return TRUE;
611 }
612 else if( strcmp(opbinput->token, "=") == 0 )
613 {
614 if( sense != NULL )
615 *sense = OPB_SENSE_EQ;
616 return TRUE;
617 }
618
619 return FALSE;
620 }
621
622 /** returns whether the current token is a value */
623 static
624 SCIP_Bool isStartingSoftConstraintWeight(
625 SCIP* scip, /**< SCIP data structure */
626 OPBINPUT* opbinput /**< OPB reading data */
627 )
628 {
629 assert(scip != NULL);
630 assert(opbinput != NULL);
631
632 if( strcmp(opbinput->token, "[") == 0 )
633 return TRUE;
634
635 return FALSE;
636 }
637
638 /** returns whether the current token is a value */
639 static
640 SCIP_Bool isEndingSoftConstraintWeight(
641 SCIP* scip, /**< SCIP data structure */
642 OPBINPUT* opbinput /**< OPB reading data */
643 )
644 {
645 assert(scip != NULL);
646 assert(opbinput != NULL);
647
648 if( strcmp(opbinput->token, "]") == 0 )
649 return TRUE;
650
651 return FALSE;
652 }
653
654 /** create binary variable with given name */
655 static
656 SCIP_RETCODE createVariable(
657 SCIP* scip, /**< SCIP data structure */
658 SCIP_VAR** var, /**< pointer to store the variable */
659 char* name /**< name for the variable */
660 )
661 {
662 SCIP_VAR* newvar;
663 SCIP_Bool dynamiccols;
664 SCIP_Bool initial;
665 SCIP_Bool removable;
666
667 SCIP_CALL( SCIPgetBoolParam(scip, "reading/dynamiccols", &dynamiccols) );
668 initial = !dynamiccols;
669 removable = dynamiccols;
670
671 /* create new variable of the given name */
672 SCIPdebugMsg(scip, "creating new variable: <%s>\n", name);
673
674 SCIP_CALL( SCIPcreateVar(scip, &newvar, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY,
675 initial, removable, NULL, NULL, NULL, NULL, NULL) );
676 SCIP_CALL( SCIPaddVar(scip, newvar) );
677 *var = newvar;
678
679 /* because the variable was added to the problem, it is captured by SCIP and we
680 * can safely release it right now without making the returned *var invalid */
681 SCIP_CALL( SCIPreleaseVar(scip, &newvar) );
682
683 return SCIP_OKAY;
684 }
685
686 /** returns the variable with the given name, or creates a new variable if it does not exist */
687 static
688 SCIP_RETCODE getVariableOrTerm(
689 SCIP* scip, /**< SCIP data structure */
690 OPBINPUT* opbinput, /**< OPB reading data */
691 SCIP_VAR*** vars, /**< pointer to store the variables */
692 int* nvars, /**< pointer to store the number of variables */
693 int* varssize /**< pointer to store the varsize, if changed (should already be initialized) */
694 )
695 {
696 SCIP_Bool negated;
697 char* name;
698
699 assert(scip != NULL);
700 assert(opbinput != NULL);
701 assert(vars != NULL);
702 assert(nvars != NULL);
703 assert(varssize != NULL);
704 assert(*varssize >= 0);
705
706 *nvars = 0;
707
708 name = opbinput->token;
709 assert(name != NULL);
710
711 /* parse AND terms */
712 while(!isdigit((unsigned char) *name ) && !isTokenChar(*name) && !opbinput->haserror )
713 {
714 SCIP_VAR* var;
715
716 negated = FALSE;
717 if( *name == '~' )
718 {
719 negated = TRUE;
720 ++name;
721 }
722
723 var = SCIPfindVar(scip, name);
724 if( var == NULL )
725 {
726 SCIP_CALL( createVariable(scip, &var, name) );
727 }
728
729 if( negated )
730 {
731 SCIP_VAR* negvar;
732 SCIP_CALL( SCIPgetNegatedVar(scip, var, &negvar) );
733
734 var = negvar;
735 }
736
737 /* reallocated memory */
738 if( *nvars == *varssize )
739 {
740 *varssize = SCIPcalcMemGrowSize(scip, *varssize + 1);
741 SCIP_CALL( SCIPreallocBufferArray(scip, vars, *varssize) );
742 }
743
744 (*vars)[*nvars] = var;
745 ++(*nvars);
746
747 if( !getNextToken(scip, opbinput) )
748 opbinput->haserror = TRUE;
749
750 name = opbinput->token;
751 }
752
753 /* check if we found at least on variable */
754 if( *nvars == 0 )
755 syntaxError(scip, opbinput, "expected a variable name");
756
757 pushToken(opbinput);
758
759 return SCIP_OKAY;
760 }
761
762 /** reads an objective or constraint with name and coefficients */
763 static
764 SCIP_RETCODE readCoefficients(
765 SCIP*const scip, /**< SCIP data structure */
766 OPBINPUT*const opbinput, /**< OPB reading data */
767 char*const name, /**< pointer to store the name of the line; must be at least of size
768 * OPB_MAX_LINELEN */
769 SCIP_VAR*** linvars, /**< pointer to store the array with linear variables (must be freed by caller) */
770 SCIP_Real** lincoefs, /**< pointer to store the array with linear coefficients (must be freed by caller) */
771 int*const nlincoefs, /**< pointer to store the number of linear coefficients */
772 SCIP_VAR**** terms, /**< pointer to store the array with nonlinear variables (must be freed by caller) */
773 SCIP_Real** termcoefs, /**< pointer to store the array with nonlinear coefficients (must be freed by caller) */
774 int** ntermvars, /**< pointer to store the number of nonlinear variables in the terms (must be freed by caller) */
775 int*const ntermcoefs, /**< pointer to store the number of nonlinear coefficients */
776 SCIP_Bool*const newsection, /**< pointer to store whether a new section was encountered */
777 SCIP_Bool*const isNonlinear, /**< pointer to store if we have a nonlinear constraint */
778 SCIP_Bool*const issoftcons, /**< pointer to store whether it is a soft constraint (for wbo files) */
779 SCIP_Real*const weight /**< pointer to store the weight of the soft constraint */
780 )
781 {
782 SCIP_VAR** tmpvars;
783 SCIP_Real* tmpcoefs;
784 SCIP_Bool havesign;
785 SCIP_Bool havevalue;
786 SCIP_Bool haveweightstart;
787 SCIP_Bool haveweightend;
788 SCIP_Real coef;
789 int coefsign;
790 int lincoefssize;
791 int termcoefssize;
792 int tmpvarssize;
793 int ntmpcoefs;
794 int ntmpvars;
795
796 assert(opbinput != NULL);
797 assert(name != NULL);
798 assert(linvars != NULL);
799 assert(lincoefs != NULL);
800 assert(nlincoefs != NULL);
801 assert(terms != NULL);
802 assert(termcoefs != NULL);
803 assert(ntermvars != NULL);
804 assert(ntermcoefs != NULL);
805 assert(newsection != NULL);
806
807 *linvars = NULL;
808 *lincoefs = NULL;
809 *terms = NULL;
810 *termcoefs = NULL;
811 *ntermvars = NULL;
812 *name = '\0';
813 *nlincoefs = 0;
814 *ntermcoefs = 0;
815 *newsection = FALSE;
816 *isNonlinear = FALSE;
817 *issoftcons = FALSE;
818
819 SCIPdebugMsg(scip, "read coefficients\n");
820
821 /* read the first token, which may be the name of the line */
822 if( getNextToken(scip, opbinput) )
823 {
824 /* remember the token in the token buffer */
825 swapTokenBuffer(opbinput);
826
827 /* get the next token and check, whether it is a colon */
828 if( getNextToken(scip, opbinput) )
829 {
830 if( strcmp(opbinput->token, ":") == 0 )
831 {
832 /* the second token was a colon ':' the first token is a constraint name */
833 (void)SCIPmemccpy(name, opbinput->tokenbuf, '\0', SCIP_MAXSTRLEN);
834
835 name[SCIP_MAXSTRLEN-1] = '\0';
836 SCIPdebugMsg(scip, "(line %d) read constraint name: '%s'\n", opbinput->linenumber, name);
837
838 /* all but the first coefficient need a sign */
839 if( strcmp(name, "soft") == 0 && (SCIPgetNVars(scip) > 0 || SCIPgetNConss(scip) > 0) )
840 {
841 syntaxError(scip, opbinput, "Soft top cost line needs to be the first non-comment line, and without any objective function.\n");
842 return SCIP_OKAY;
843 }
844 }
845 else
846 {
847 /* the second token was no colon: push the tokens back onto the token stack and parse them as coefficients */
848 SCIPdebugMsg(scip, "(line %d) constraint has no name\n", opbinput->linenumber);
849 pushToken(opbinput);
850 pushBufferToken(opbinput);
851 }
852 }
853 else
854 {
855 /* there was only one token left: push it back onto the token stack and parse it as coefficient */
856 pushBufferToken(opbinput);
857 }
858 }
859 else
860 {
861 assert(SCIPfeof( opbinput->file ) );
862 opbinput->eof = TRUE;
863 return SCIP_OKAY;
864 }
865
866 /* initialize buffers for storing the coefficients */
867 lincoefssize = OPB_INIT_COEFSSIZE;
868 termcoefssize = OPB_INIT_COEFSSIZE;
869 tmpvarssize = OPB_INIT_COEFSSIZE;
870 SCIP_CALL( SCIPallocBufferArray(scip, linvars, lincoefssize) );
871 SCIP_CALL( SCIPallocBufferArray(scip, lincoefs, lincoefssize) );
872 SCIP_CALL( SCIPallocBufferArray(scip, terms, termcoefssize) );
873 SCIP_CALL( SCIPallocBufferArray(scip, termcoefs, termcoefssize) );
874 SCIP_CALL( SCIPallocBufferArray(scip, ntermvars, termcoefssize) );
875 SCIP_CALL( SCIPallocBufferArray(scip, &tmpvars, tmpvarssize) );
876 SCIP_CALL( SCIPallocBufferArray(scip, &tmpcoefs, tmpvarssize) );
877
878 /* read the coefficients */
879 coefsign = +1;
880 coef = 1.0;
881 havesign = FALSE;
882 havevalue = FALSE;
883 haveweightstart = FALSE;
884 haveweightend = FALSE;
885 ntmpcoefs = 0;
886 ntmpvars = 0;
887 while( getNextToken(scip, opbinput) && !hasError(opbinput) )
888 {
889 if( isEndLine(opbinput) )
890 {
891 *newsection = TRUE;
892 goto TERMINATE;
893 }
894
895 /* check if we reached an equation sense */
896 if( isSense(opbinput, NULL) )
897 {
898 /* put the sense back onto the token stack */
899 pushToken(opbinput);
900 goto TERMINATE;
901 }
902
903 /* check if we read a sign */
904 if( isSign(opbinput, &coefsign) )
905 {
906 SCIPdebugMsg(scip, "(line %d) read coefficient sign: %+d\n", opbinput->linenumber, coefsign);
907 havesign = TRUE;
908 continue;
909 }
910
911 /* check if we read a value */
912 if( isValue(scip, opbinput, &coef) )
913 {
914 /* coefficients without a sign are treated as "+" */
915 if( (*nlincoefs > 0 || *ntermcoefs > 0 || ntmpcoefs > 0) && !havesign )
916 {
917 coefsign = 1;
918 havesign = TRUE;
919 }
920
921 SCIPdebugMsg(scip, "(line %d) read coefficient value: %g with sign %+d\n", opbinput->linenumber, coef, coefsign);
922 if( havevalue )
923 {
924 syntaxError(scip, opbinput, "two consecutive values");
925 goto TERMINATE;
926 }
927 havevalue = TRUE;
928
929 /* if we read a wbo file, the first line should be something like "soft: <weight>;", where weight is a value or nothing */
930 if( strcmp(name, "soft") == 0 )
931 {
932 assert(ntmpcoefs == 0);
933
934 tmpcoefs[ntmpcoefs] = coefsign * coef;
935 ++ntmpcoefs;
936 }
937
938 continue;
939 }
940
941 /* check if we are reading a soft constraint line, it start with "[<weight>]", where weight is a value */
942 if( *nlincoefs == 0 && *ntermcoefs == 0 && ntmpcoefs == 0 && !havesign && !havevalue && strcmp(name, "soft") != 0 && isStartingSoftConstraintWeight(scip, opbinput) )
943 {
944 if( !opbinput->wbo )
945 {
946 SCIPwarningMessage(scip, "Found in line %d a soft constraint, without having read a starting top-cost line.\n", opbinput->linenumber);
947 }
948 haveweightstart = TRUE;
949
950 continue;
951 }
952 if( *nlincoefs == 0 && *ntermcoefs == 0 && ntmpcoefs == 0 && havevalue && haveweightstart && isEndingSoftConstraintWeight(scip, opbinput) )
953 {
954 *weight = coefsign * coef;
955 SCIPdebugMsg(scip, "(line %d) found soft constraint weight: %g\n", opbinput->linenumber, *weight);
956
957 coefsign = +1;
958 havesign = FALSE;
959 havevalue = FALSE;
960 haveweightend = TRUE;
961 *issoftcons = TRUE;
962
963 continue;
964 }
965
966 /* if we read a '[' we should already read a ']', which indicates that we read a soft constraint,
967 * we have a parsing error */
968 if( haveweightstart != haveweightend )
969 {
970 syntaxError(scip, opbinput, "Wrong soft constraint.");
971 goto TERMINATE;
972 }
973
974 /* if we read the first non-comment line of a wbo file we should never be here */
975 if( strcmp(name, "soft") == 0 )
976 {
977 syntaxError(scip, opbinput, "Wrong soft top cost line.");
978 goto TERMINATE;
979 }
980
981 /* the token is a variable name: get the corresponding variables (or create a new ones) */
982 SCIP_CALL( getVariableOrTerm(scip, opbinput, &tmpvars, &ntmpvars, &tmpvarssize) );
983
984 if( ntmpvars > 1 )
985 {
986 /* insert non-linear term */
987 *isNonlinear = TRUE;
988
989 SCIPdebugMsg(scip, "(line %d) found linear term: %+g", opbinput->linenumber, coefsign * coef);
990 #ifndef NDEBUG
991 {
992 int v;
993 for( v = 0; v < ntmpvars; ++v )
994 {
995 SCIPdebugMsgPrint(scip, " %s * ", SCIPvarGetName(tmpvars[v]));
996 }
997 SCIPdebugMsgPrint(scip, "\n");
998 }
999 #endif
1000 if( !SCIPisZero(scip, coef) )
1001 {
1002 assert(*ntermcoefs <= termcoefssize);
1003 /* resize the terms, ntermvars, and termcoefs array if needed */
1004 if( *ntermcoefs == termcoefssize )
1005 {
1006 termcoefssize = SCIPcalcMemGrowSize(scip, termcoefssize + 1);
1007 SCIP_CALL( SCIPreallocBufferArray(scip, terms, termcoefssize) );
1008 SCIP_CALL( SCIPreallocBufferArray(scip, termcoefs, termcoefssize) );
1009 SCIP_CALL( SCIPreallocBufferArray(scip, ntermvars, termcoefssize) );
1010 }
1011 assert(*ntermcoefs < termcoefssize);
1012
1013 /* get memory for the last term */
1014 SCIP_CALL( SCIPallocBufferArray(scip, &((*terms)[*ntermcoefs]), ntmpvars) ); /*lint !e866 */
1015
1016 /* set the number of variable in this term */
1017 (*ntermvars)[*ntermcoefs] = ntmpvars;
1018
1019 /* add all variables */
1020 for( --ntmpvars; ntmpvars >= 0; --ntmpvars )
1021 {
1022 (*terms)[*ntermcoefs][ntmpvars] = tmpvars[ntmpvars];
1023 }
1024 /* add coefficient */
1025 (*termcoefs)[*ntermcoefs] = coefsign * coef;
1026
1027 /***********************/
1028 if( !SCIPisIntegral(scip, (*termcoefs)[*ntermcoefs]) )
1029 {
1030 SCIPwarningMessage(scip, "coefficient %g in line %d not integral.\n", (*termcoefs)[*ntermcoefs], opbinput->linenumber);
1031 }
1032
1033 ++(*ntermcoefs);
1034 }
1035
1036 /* reset the flags and coefficient value for the next coefficient */
1037 coefsign = +1;
1038 coef = 1.0;
1039 havesign = FALSE;
1040 havevalue = FALSE;
1041 ntmpvars = 0;
1042 }
1043 else
1044 {
1045 assert(ntmpvars == 1);
1046 /* insert linear term */
1047 SCIPdebugMsg(scip, "(line %d) found linear term: %+g<%s>\n", opbinput->linenumber, coefsign * coef, SCIPvarGetName(tmpvars[0]));
1048 if( !SCIPisZero(scip, coef) )
1049 {
1050 assert(*nlincoefs <= lincoefssize);
1051 /* resize the vars and coefs array if needed */
1052 if( *nlincoefs >= lincoefssize )
1053 {
1054 lincoefssize = SCIPcalcMemGrowSize(scip, lincoefssize + 1);
1055 SCIP_CALL( SCIPreallocBufferArray(scip, linvars, lincoefssize) );
1056 SCIP_CALL( SCIPreallocBufferArray(scip, lincoefs, lincoefssize) );
1057 }
1058 assert(*nlincoefs < lincoefssize);
1059
1060 /* add coefficient */
1061 (*linvars)[*nlincoefs] = tmpvars[0];
1062 (*lincoefs)[*nlincoefs] = coefsign * coef;
1063
1064 /***********************/
1065 if( !SCIPisIntegral(scip, (*lincoefs)[*nlincoefs]) )
1066 {
1067 SCIPwarningMessage(scip, "coefficient %g in line %d not integral.\n", (*lincoefs)[*nlincoefs], opbinput->linenumber);
1068 }
1069
1070 ++(*nlincoefs);
1071 }
1072
1073 /* reset the flags and coefficient value for the next coefficient */
1074 coefsign = +1;
1075 coef = 1.0;
1076 havesign = FALSE;
1077 havevalue = FALSE;
1078 ntmpvars = 0;
1079 }
1080 }
1081
1082 TERMINATE:
1083 if( !opbinput->haserror )
1084 {
1085 /* all variables should be in the right arrays */
1086 assert(ntmpvars == 0);
1087 /* the following is only the case if we read topcost's of a wbo file, we need to move this topcost value to the
1088 * right array */
1089 if( ntmpcoefs > 0 )
1090 {
1091 /* maximal one topcost value is possible */
1092 assert(ntmpcoefs == 1);
1093 /* no other coefficient should be found here */
1094 assert(*nlincoefs == 0 && *ntermcoefs == 0);
1095
1096 /* copy value */
1097 (*lincoefs)[*nlincoefs] = tmpcoefs[0];
1098
1099 /***********************/
1100 if( !SCIPisIntegral(scip, (*lincoefs)[*nlincoefs]) )
1101 {
1102 SCIPwarningMessage(scip, "topcost not integral.\n");
1103 }
1104
1105 *nlincoefs = 1;
1106 }
1107 }
1108 /* clear memory */
1109 SCIPfreeBufferArray(scip, &tmpcoefs);
1110 SCIPfreeBufferArray(scip, &tmpvars);
1111
1112 return SCIP_OKAY;
1113 }
1114
1115 /** set the objective section */
1116 static
1117 SCIP_RETCODE setObjective(
1118 SCIP*const scip, /**< SCIP data structure */
1119 OPBINPUT*const opbinput, /**< OPB reading data */
1120 const char* sense, /**< objective sense */
1121 SCIP_VAR**const linvars, /**< array of linear variables */
1122 SCIP_Real*const coefs, /**< array of objective values for linear variables */
1123 int const ncoefs, /**< number of coefficients for linear part */
1124 SCIP_VAR***const terms, /**< array with nonlinear variables */
1125 SCIP_Real*const termcoefs, /**< array of objective values for nonlinear variables */
1126 int*const ntermvars, /**< number of nonlinear variables in the terms */
1127 int const ntermcoefs /**< number of nonlinear coefficients */
1128 )
1129 {
1130 assert(scip != NULL);
1131 assert(opbinput != NULL);
1132 assert(isEndLine(opbinput));
1133 assert(ncoefs == 0 || (linvars != NULL && coefs != NULL));
1134 assert(ntermcoefs == 0 || (terms != NULL && ntermvars != NULL && termcoefs != NULL));
1135
1136 if( !hasError(opbinput) )
1137 {
1138 SCIP_VAR* var;
1139 int v;
1140 char name[SCIP_MAXSTRLEN];
1141
1142 if( strcmp(sense, "max" ) == 0 )
1143 opbinput->objsense = SCIP_OBJSENSE_MAXIMIZE;
1144
1145 /* @todo: what todo with non-linear objectives, maybe create the necessary and-constraints and add the arising linear
1146 * objective (with and-resultants) or add a integer variable to this constraint and put only this variable in the
1147 * objective, for this we need to expand the pseudo-boolean constraints to handle integer variables
1148 *
1149 * integer variant is not implemented
1150 */
1151 if( ntermcoefs > 0 )
1152 {
1153 #if (LINEAROBJECTIVE == TRUE)
1154 /* all non-linear parts are created as and-constraints, even if the same non-linear part was already part of the objective function */
1155
1156 SCIP_VAR** vars;
1157 int nvars;
1158 int t;
1159 SCIP_CONS* andcons;
1160
1161 for( t = 0; t < ntermcoefs; ++t )
1162 {
1163 assert(terms != NULL); /* for lint */
1164 assert(ntermvars != NULL);
1165 assert(termcoefs != NULL);
1166
1167 vars = terms[t];
1168 nvars = ntermvars[t];
1169 assert(vars != NULL);
1170 assert(nvars > 1);
1171
1172 /* create auxiliary variable */
1173 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, ARTIFICIALVARNAMEPREFIX"obj_%d", t);
1174 SCIP_CALL( SCIPcreateVar(scip, &var, name, 0.0, 1.0, termcoefs[t], SCIP_VARTYPE_BINARY,
1175 TRUE, TRUE, NULL, NULL, NULL, NULL, NULL) );
1176
1177 /* @todo: check if it is better to change the branching priority for the artificial variables */
1178 #if 1
1179 /* change branching priority of artificial variable to -1 */
1180 SCIP_CALL( SCIPchgVarBranchPriority(scip, var, -1) );
1181 #endif
1182
1183 /* add auxiliary variable to the problem */
1184 SCIP_CALL( SCIPaddVar(scip, var) );
1185
1186 #ifdef WITH_DEBUG_SOLUTION
1187 if( SCIPdebugIsMainscip(scip) )
1188 {
1189 SCIP_Real val = 0.0;
1190
1191 for( v = nvars - 1; v >= 0; --v )
1192 {
1193 SCIP_CALL( SCIPdebugGetSolVal(scip, vars[v], &val) );
1194 assert(SCIPisFeasZero(scip, val) || SCIPisFeasEQ(scip, val, 1.0));
1195
1196 if( val < 0.5 )
1197 break;
1198 }
1199 SCIP_CALL( SCIPdebugAddSolVal(scip, var, (val < 0.5) ? 0.0 : 1.0) );
1200 }
1201 #endif
1202
1203 /* @todo: check whether all constraint creation flags are the best option */
1204 /* create and-constraint */
1205 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "obj_andcons_%d", t);
1206 SCIP_CALL( SCIPcreateConsAnd(scip, &andcons, name, var, nvars, vars,
1207 TRUE, TRUE, TRUE, TRUE, TRUE,
1208 FALSE, FALSE, FALSE, FALSE, FALSE) );
1209 SCIP_CALL( SCIPaddCons(scip, andcons) );
1210 SCIPdebugPrintCons(scip, andcons, NULL);
1211 SCIP_CALL( SCIPreleaseCons(scip, &andcons) );
1212
1213 SCIP_CALL( SCIPreleaseVar(scip, &var) );
1214 }
1215 #else /* now the integer variant */
1216 SCIP_CONS* pseudocons;
1217 SCIP_Real lb;
1218 SCIP_Real ub;
1219
1220 lb = 0.0;
1221 ub = 0.0;
1222
1223 /* add all non linear coefficients up */
1224 for( v = 0; v < ntermcoefs; ++v )
1225 {
1226 if( termcoefs[v] < 0 )
1227 lb += termcoefs[v];
1228 else
1229 ub += termcoefs[v];
1230 }
1231 /* add all linear coefficients up */
1232 for( v = 0; v < ncoefs; ++v )
1233 {
1234 if( coefs[v] < 0 )
1235 lb += coefs[v];
1236 else
1237 ub += coefs[v];
1238 }
1239 assert(lb < ub);
1240
1241 /* create auxiliary variable */
1242 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "artificial_int_obj");
1243 SCIP_CALL( SCIPcreateVar(scip, &var, name, lb, ub, 1.0, SCIP_VARTYPE_INTEGER,
1244 TRUE, TRUE, NULL, NULL, NULL, NULL, NULL) );
1245
1246 /* @todo: check if it is better to change the branching priority for the artificial variables */
1247 #if 1
1248 /* change branching priority of artificial variable to -1 */
1249 SCIP_CALL( SCIPchgVarBranchPriority(scip, var, -1) );
1250 #endif
1251 /* add auxiliary variable to the problem */
1252 SCIP_CALL( SCIPaddVar(scip, var) );
1253
1254 #ifdef WITH_DEBUG_SOLUTION
1255 if( SCIPdebugIsMainscip(scip) )
1256 {
1257 SCIP_Real artval = 0.0;
1258 SCIP_Real val;
1259
1260 for( t = 0; t < ntermcoefs; ++t )
1261 {
1262 vars = terms[t];
1263 nvars = ntermvars[t];
1264 assert(vars != NULL);
1265 assert(nvars > 1);
1266
1267 for( v = nvars - 1; v >= 0; --v )
1268 {
1269 SCIP_CALL( SCIPdebugGetSolVal(scip, vars[v], &val) );
1270 assert(SCIPisFeasZero(scip, val) || SCIPisFeasEQ(scip, val, 1.0));
1271
1272 if( val < 0.5 )
1273 break;
1274 }
1275
1276 artval += (((val < 0.5) ? 0.0 : 1.0) * termcoefs[t]);
1277 }
1278 assert(SCIPisFeasLE(scip, lb, artval) && SCIPisFeasGE(scip, ub, artval));
1279
1280 SCIP_CALL( SCIPdebugAddSolVal(scip, var, artval) );
1281 }
1282 #endif
1283
1284 /* create artificial objection function constraint containing the artificial integer variable */
1285 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "artificial_obj_cons");
1286 SCIP_CALL( SCIPcreateConsPseudoboolean(scip, &pseudocons, name, linvars, ncoefs, coefs, terms, ntermcoefs,
1287 ntermvars, termcoefs, NULL, 0.0, FALSE, var, 0.0, 0.0,
1288 TRUE, TRUE, TRUE, TRUE, TRUE,
1289 FALSE, FALSE, FALSE, FALSE, FALSE) );
1290
1291 SCIP_CALL( SCIPaddCons(scip, pseudocons) );
1292 SCIPdebugPrintCons(scip, pseudocons, NULL);
1293 SCIP_CALL( SCIPreleaseCons(scip, &pseudocons) );
1294
1295 SCIP_CALL( SCIPreleaseVar(scip, &var) );
1296
1297 return SCIP_OKAY;
1298 #endif
1299 }
1300 /* set the objective values */
1301 for( v = 0; v < ncoefs; ++v )
1302 {
1303 assert(linvars != NULL); /* for lint */
1304 assert(coefs != NULL);
1305
1306 if( SCIPvarIsNegated(linvars[v]) )
1307 {
1308 SCIP_VAR* negvar = SCIPvarGetNegationVar(linvars[v]);
1309
1310 SCIP_CALL( SCIPaddOrigObjoffset(scip, coefs[v]) );
1311 SCIP_CALL( SCIPchgVarObj(scip, negvar, SCIPvarGetObj(negvar) - coefs[v]) );
1312 }
1313 else
1314 {
1315 SCIP_CALL( SCIPchgVarObj(scip, linvars[v], SCIPvarGetObj(linvars[v]) + coefs[v]) );
1316 }
1317 }
1318 }
1319
1320 return SCIP_OKAY;
1321 }
1322
1323 /** reads the constraints section */
1324 static
1325 SCIP_RETCODE readConstraints(
1326 SCIP* scip, /**< SCIP data structure */
1327 OPBINPUT* opbinput, /**< OPB reading data */
1328 int* nNonlinearConss /**< pointer to store number of nonlinear constraints */
1329 )
1330 {
1331 char name[OPB_MAX_LINELEN];
1332 SCIP_CONS* cons;
1333 SCIP_VAR** linvars;
1334 SCIP_Real* lincoefs;
1335 int nlincoefs;
1336 SCIP_VAR*** terms;
1337 SCIP_Real* termcoefs;
1338 int* ntermvars;
1339 int ntermcoefs;
1340 OPBSENSE sense;
1341 SCIP_RETCODE retcode;
1342 SCIP_Real sidevalue;
1343 SCIP_Real lhs;
1344 SCIP_Real rhs;
1345 SCIP_Bool newsection;
1346 SCIP_Bool initialconss;
1347 SCIP_Bool dynamicconss;
1348 SCIP_Bool dynamicrows;
1349 SCIP_Bool initial;
1350 SCIP_Bool separate;
1351 SCIP_Bool enforce;
1352 SCIP_Bool check;
1353 SCIP_Bool propagate;
1354 SCIP_Bool local;
1355 SCIP_Bool modifiable;
1356 SCIP_Bool dynamic;
1357 SCIP_Bool removable;
1358 SCIP_Bool isNonlinear;
1359 int sidesign;
1360 SCIP_Bool issoftcons;
1361 SCIP_Real weight;
1362 SCIP_VAR* indvar;
1363 char indname[SCIP_MAXSTRLEN];
1364 int t;
1365
1366 assert(scip != NULL);
1367 assert(opbinput != NULL);
1368 assert(nNonlinearConss != NULL);
1369
1370 weight = -SCIPinfinity(scip);
1371 retcode = SCIP_OKAY;
1372
1373 /* read the objective coefficients */
1374 SCIP_CALL( readCoefficients(scip, opbinput, name, &linvars, &lincoefs, &nlincoefs, &terms, &termcoefs, &ntermvars, &ntermcoefs, &newsection, &isNonlinear, &issoftcons, &weight) );
1375
1376 if( hasError(opbinput) || opbinput->eof )
1377 goto TERMINATE;
1378 if( newsection )
1379 {
1380 if( strcmp(name, "min") == 0 || strcmp(name, "max") == 0 )
1381 {
1382 if( opbinput->wbo )
1383 {
1384 syntaxError(scip, opbinput, "Cannot have an objective function when having soft constraints.\n");
1385 goto TERMINATE;
1386 }
1387
1388 /* set objective function */
1389 SCIP_CALL( setObjective(scip, opbinput, name, linvars, lincoefs, nlincoefs, terms, termcoefs, ntermvars, ntermcoefs) );
1390 }
1391 else if( strcmp(name, "soft") == 0 )
1392 {
1393 /* we have a "weighted boolean optimization"-file(wbo) */
1394 opbinput->wbo = TRUE;
1395 if( nlincoefs == 0 )
1396 opbinput->topcost = SCIPinfinity(scip);
1397 else
1398 {
1399 assert(nlincoefs == 1);
1400 assert(lincoefs != NULL);
1401 opbinput->topcost = lincoefs[0];
1402 }
1403 SCIPdebugMsg(scip, "Weighted Boolean Optimization problem has topcost of %g\n", opbinput->topcost);
1404 }
1405 else if( nlincoefs > 0 )
1406 syntaxError(scip, opbinput, "expected constraint sense '=' or '>='");
1407 goto TERMINATE;
1408 }
1409
1410 /* read the constraint sense */
1411 if( !getNextToken(scip, opbinput) )
1412 {
1413 syntaxError(scip, opbinput, "expected constraint sense.");
1414 goto TERMINATE;
1415 }
1416 if( !isSense(opbinput, &sense) )
1417 {
1418 syntaxError(scip, opbinput, "expected constraint sense '=' or '>='.");
1419 goto TERMINATE;
1420 }
1421
1422 /* read the right hand side */
1423 sidesign = +1;
1424 if( !getNextToken(scip, opbinput) )
1425 {
1426 syntaxError(scip, opbinput, "missing right hand side");
1427 goto TERMINATE;
1428 }
1429 if( isSign(opbinput, &sidesign) )
1430 {
1431 if( !getNextToken(scip, opbinput) )
1432 {
1433 syntaxError(scip, opbinput, "missing value of right hand side");
1434 goto TERMINATE;
1435 }
1436 }
1437 if( !isValue(scip, opbinput, &sidevalue) )
1438 {
1439 syntaxError(scip, opbinput, "expected value as right hand side");
1440 goto TERMINATE;
1441 }
1442 sidevalue *= sidesign;
1443
1444 /* check if we reached the line end */
1445 if( !getNextToken(scip, opbinput) || !isEndLine(opbinput) )
1446 {
1447 syntaxError(scip, opbinput, "expected endline character ';'");
1448 goto TERMINATE;
1449 }
1450
1451 /* assign the left and right hand side, depending on the constraint sense */
1452 switch( sense ) /*lint !e530*/
1453 {
1454 case OPB_SENSE_GE:
1455 lhs = sidevalue;
1456 rhs = SCIPinfinity(scip);
1457 break;
1458 case OPB_SENSE_LE:
1459 lhs = -SCIPinfinity(scip);
1460 rhs = sidevalue;
1461 break;
1462 case OPB_SENSE_EQ:
1463 lhs = sidevalue;
1464 rhs = sidevalue;
1465 break;
1466 case OPB_SENSE_NOTHING:
1467 default:
1468 SCIPerrorMessage("invalid constraint sense <%d>\n", sense);
1469 return SCIP_INVALIDDATA;
1470 }
1471
1472 /* create and add the linear constraint */
1473 SCIP_CALL( SCIPgetBoolParam(scip, "reading/initialconss", &initialconss) );
1474 SCIP_CALL( SCIPgetBoolParam(scip, "reading/dynamicrows", &dynamicrows) );
1475 SCIP_CALL( SCIPgetBoolParam(scip, "reading/" READER_NAME "/dynamicconss", &dynamicconss) );
1476
1477 initial = initialconss;
1478 separate = TRUE;
1479 enforce = TRUE;
1480 check = TRUE;
1481 propagate = TRUE;
1482 local = FALSE;
1483 modifiable = FALSE;
1484 dynamic = FALSE;/*dynamicconss;*/
1485 removable = dynamicrows;
1486
1487 /* create corresponding constraint */
1488 if( issoftcons )
1489 {
1490 (void) SCIPsnprintf(indname, SCIP_MAXSTRLEN, INDICATORVARNAME"%d", opbinput->nindvars);
1491 ++(opbinput->nindvars);
1492 SCIP_CALL( createVariable(scip, &indvar, indname) );
1493
1494 assert(!SCIPisInfinity(scip, -weight));
1495 SCIP_CALL( SCIPchgVarObj(scip, indvar, weight) );
1496 }
1497 else
1498 indvar = NULL;
1499
1500 if( ntermcoefs > 0 || issoftcons )
1501 {
1502 #if GENCONSNAMES == TRUE
1503 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "pseudoboolean%d", opbinput->consnumber);
1504 ++(opbinput->consnumber);
1505 #else
1506 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "pseudoboolean");
1507 #endif
1508 retcode = SCIPcreateConsPseudoboolean(scip, &cons, name, linvars, nlincoefs, lincoefs, terms, ntermcoefs,
1509 ntermvars, termcoefs, indvar, weight, issoftcons, NULL, lhs, rhs,
1510 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, FALSE);
1511 if( retcode != SCIP_OKAY )
1512 goto TERMINATE;
1513 }
1514 else
1515 {
1516 #if GENCONSNAMES == TRUE
1517 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "linear%d", opbinput->consnumber);
1518 ++(opbinput->consnumber);
1519 #else
1520 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "linear");
1521 #endif
1522 retcode = SCIPcreateConsLinear(scip, &cons, name, nlincoefs, linvars, lincoefs, lhs, rhs,
1523 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, FALSE);
1524 if( retcode != SCIP_OKAY )
1525 goto TERMINATE;
1526 }
1527
1528 SCIP_CALL( SCIPaddCons(scip, cons) );
1529 SCIPdebugMsg(scip, "(line %d) created constraint: ", opbinput->linenumber);
1530 SCIPdebugPrintCons(scip, cons, NULL);
1531 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
1532
1533 if( isNonlinear )
1534 ++(*nNonlinearConss);
1535
1536 TERMINATE:
1537
1538 /* free memory */
1539 for( t = ntermcoefs - 1; t >= 0; --t )
1540 {
1541 assert(terms != NULL); /* for lint */
1542 SCIPfreeBufferArrayNull(scip, &(terms[t]));
1543 }
1544
1545 SCIPfreeBufferArrayNull(scip, &ntermvars);
1546 SCIPfreeBufferArrayNull(scip, &termcoefs);
1547 SCIPfreeBufferArrayNull(scip, &terms);
1548 SCIPfreeBufferArrayNull(scip, &lincoefs);
1549 SCIPfreeBufferArrayNull(scip, &linvars);
1550
1551 SCIP_CALL( retcode );
1552
1553 return SCIP_OKAY;
1554 }
1555
1556 /** tries to read the first comment line which usually contains information about the max size of "and" products */
1557 static
1558 SCIP_RETCODE getMaxAndConsDim(
1559 SCIP* scip, /**< SCIP data structure */
1560 OPBINPUT* opbinput, /**< OPB reading data */
1561 SCIP_Real* objoffset /**< pointer to store objective offset */
1562 )
1563 {
1564 SCIP_Bool stop;
1565 char* commentstart;
1566 char* nproducts;
1567 char* str;
1568 int i;
1569
1570 assert(scip != NULL);
1571 assert(opbinput != NULL);
1572 assert(objoffset != NULL);
1573
1574 stop = FALSE;
1575 commentstart = NULL;
1576 nproducts = NULL;
1577
1578 *objoffset = 0.0;
1579
1580 do
1581 {
1582 if( SCIPfgets(opbinput->linebuf, opbinput->linebufsize, opbinput->file) == NULL )
1583 {
1584 assert( SCIPfeof(opbinput->file) );
1585 break;
1586 }
1587
1588 /* read characters after comment symbol */
1589 for( i = 0; commentchars[i] != '\0'; ++i )
1590 {
1591 commentstart = strchr(opbinput->linebuf, commentchars[i]);
1592
1593 /* found a comment line */
1594 if( commentstart != NULL )
1595 {
1596 /* search for "#product= xyz" in comment line, where xyz represents the number of and constraints */
1597 nproducts = strstr(opbinput->linebuf, "#product= ");
1598 if( nproducts != NULL )
1599 {
1600 const char delimchars[] = " \t";
1601 char* pos;
1602
1603 nproducts += strlen("#product= ");
1604
1605 pos = strtok(nproducts, delimchars);
1606
1607 if( pos != NULL )
1608 {
1609 SCIPdebugMsg(scip, "%d products supposed to be in file.\n", atoi(pos));
1610 }
1611
1612 pos = strtok (NULL, delimchars);
1613
1614 if( pos != NULL && strcmp(pos, "sizeproduct=") == 0 )
1615 {
1616 pos = strtok (NULL, delimchars);
1617 if( pos != NULL )
1618 {
1619 SCIPdebugMsg(scip, "sizeproducts = %d\n", atoi(pos));
1620 }
1621 }
1622
1623 stop = TRUE;
1624 }
1625
1626 /* search for "Obj. offset : <number>" in comment line */
1627 str = strstr(opbinput->linebuf, "Obj. offset : ");
1628 if( str != NULL )
1629 {
1630 str += strlen("Obj. offset : ");
1631 *objoffset = atof(str);
1632 break;
1633 }
1634
1635 /* make sure that comment vanishes */
1636 *commentstart = '\0';
1637
1638 break;
1639 }
1640 }
1641 }
1642 while(commentstart != NULL && !stop);
1643
1644 return SCIP_OKAY;
1645 }
1646
1647 /** reads an OPB file */
1648 static
1649 SCIP_RETCODE readOPBFile(
1650 SCIP* scip, /**< SCIP data structure */
1651 OPBINPUT* opbinput, /**< OPB reading data */
1652 const char* filename /**< name of the input file */
1653 )
1654 {
1655 SCIP_Real objoffset;
1656 int nNonlinearConss;
1657 int i;
1658
1659 assert(scip != NULL);
1660 assert(opbinput != NULL);
1661
1662 /* open file */
1663 opbinput->file = SCIPfopen(filename, "r");
1664 if( opbinput->file == NULL )
1665 {
1666 SCIPerrorMessage("cannot open file <%s> for reading\n", filename);
1667 SCIPprintSysError(filename);
1668 return SCIP_NOFILE;
1669 }
1670
1671 /* @todo: reading additional information about the number of and constraints in comments to avoid reallocating
1672 * "opbinput.andconss"
1673 */
1674
1675 /* tries to read the first comment line which usually contains information about the max size of "and" products */
1676 SCIP_CALL( getMaxAndConsDim(scip, opbinput, &objoffset) );
1677
1678 /* create problem */
1679 SCIP_CALL( SCIPcreateProb(scip, filename, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
1680
1681 if( ! SCIPisZero(scip, objoffset) )
1682 {
1683 SCIP_CALL( SCIPaddOrigObjoffset(scip, objoffset) );
1684 }
1685
1686 nNonlinearConss = 0;
1687
1688 while( !SCIPfeof( opbinput->file ) && !hasError(opbinput) )
1689 {
1690 SCIP_CALL( readConstraints(scip, opbinput, &nNonlinearConss) );
1691 }
1692
1693 /* if we read a wbo file we need to make sure that the top cost won't be exceeded */
1694 if( opbinput->wbo )
1695 {
1696 SCIP_VAR** topcostvars;
1697 SCIP_Real* topcosts;
1698 SCIP_VAR** vars;
1699 int nvars;
1700 int ntopcostvars;
1701 SCIP_Longint topcostrhs;
1702 SCIP_CONS* topcostcons;
1703
1704 nvars = SCIPgetNVars(scip);
1705 vars = SCIPgetVars(scip);
1706 assert(nvars > 0 || vars != NULL);
1707
1708 SCIP_CALL( SCIPallocBufferArray(scip, &topcostvars, nvars) );
1709 SCIP_CALL( SCIPallocBufferArray(scip, &topcosts, nvars) );
1710
1711 ntopcostvars = 0;
1712 for( i = nvars - 1; i >= 0; --i )
1713 if( !SCIPisZero(scip, SCIPvarGetObj(vars[i])) )
1714 {
1715 topcostvars[ntopcostvars] = vars[i];
1716 topcosts[ntopcostvars] = SCIPvarGetObj(vars[i]);
1717 ++ntopcostvars;
1718 }
1719
1720 if( SCIPisIntegral(scip, opbinput->topcost) )
1721 topcostrhs = (SCIP_Longint) SCIPfloor(scip, opbinput->topcost - 1);
1722 else
1723 topcostrhs = (SCIP_Longint) SCIPfloor(scip, opbinput->topcost);
1724
1725 SCIP_CALL( SCIPcreateConsLinear(scip, &topcostcons, TOPCOSTCONSNAME, ntopcostvars, topcostvars, topcosts, -SCIPinfinity(scip),
1726 (SCIP_Real) topcostrhs, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
1727 SCIP_CALL( SCIPaddCons(scip, topcostcons) );
1728 SCIPdebugPrintCons(scip, topcostcons, NULL);
1729 SCIP_CALL( SCIPreleaseCons(scip, &topcostcons) );
1730
1731 SCIPfreeBufferArray(scip, &topcosts);
1732 SCIPfreeBufferArray(scip, &topcostvars);
1733 }
1734
1735 /* close file */
1736 SCIPfclose(opbinput->file);
1737
1738 return SCIP_OKAY;
1739 }
1740
1741
1742 /*
1743 * Local methods (for writing)
1744 */
1745
1746 /** transforms given and constraint variables to the corresponding active or negated variables */
1747 static
1748 SCIP_RETCODE getBinVarsRepresentatives(
1749 SCIP*const scip, /**< SCIP data structure */
1750 SCIP_VAR**const vars, /**< vars array to get active variables for */
1751 int const nvars, /**< pointer to number of variables and values in vars and vals array */
1752 SCIP_Bool const transformed /**< transformed constraint? */
1753 )
1754 {
1755 SCIP_Bool negated;
1756 int v;
1757
1758 assert( scip != NULL );
1759 assert( vars != NULL );
1760 assert( nvars > 0 );
1761
1762 if( transformed )
1763 {
1764 for( v = nvars - 1; v >= 0; --v )
1765 {
1766 /* gets a binary variable that is equal to the given binary variable, and that is either active, fixed, or
1767 * multi-aggregated, or the negated variable of an active, fixed, or multi-aggregated variable
1768 */
1769 SCIP_CALL( SCIPgetBinvarRepresentative( scip, vars[v], &vars[v], &negated) );
1770 }
1771 }
1772 else
1773 {
1774 SCIP_Real scalar;
1775 SCIP_Real constant;
1776
1777 for( v = nvars - 1; v >= 0; --v )
1778 {
1779 scalar = 1.0;
1780 constant = 0.0;
1781
1782 /* retransforms given variable, scalar and constant to the corresponding original variable, scalar and constant,
1783 * if possible; if the retransformation is impossible, NULL is returned as variable
1784 */
1785 SCIP_CALL( SCIPvarGetOrigvarSum(&vars[v], &scalar, &constant) );
1786
1787 if( vars[v] == NULL )
1788 {
1789 SCIPdebugMsg(scip, "A variable couldn't retransformed to an original variable.\n");
1790 return SCIP_INVALIDDATA;
1791 }
1792 if( SCIPisEQ(scip, scalar, -1.0) && SCIPisEQ(scip, constant, 1.0) )
1793 {
1794 SCIP_CALL( SCIPgetNegatedVar(scip, vars[v], &vars[v]) );
1795 }
1796 else
1797 {
1798 if( !SCIPisEQ(scip, scalar, 1.0) || !SCIPisZero(scip, constant) )
1799 {
1800 SCIPdebugMsg(scip, "A variable couldn't retransformed to an original variable or a negated variable of an original variable (scalar = %g, constant = %g).\n", scalar, constant);
1801 return SCIP_INVALIDDATA;
1802 }
1803 }
1804 }
1805 }
1806
1807 return SCIP_OKAY;
1808 }
1809
1810 /** transforms given variables, scalars, and constant to the corresponding active variables, scalars, and constant */
1811 static
1812 SCIP_RETCODE getActiveVariables(
1813 SCIP* scip, /**< SCIP data structure */
1814 SCIP_VAR** vars, /**< vars array to get active variables for */
1815 SCIP_Real* scalars, /**< scalars a_1, ..., a_n in linear sum a_1*x_1 + ... + a_n*x_n + c */
1816 int* nvars, /**< pointer to number of variables and values in vars and vals array */
1817 SCIP_Real* constant, /**< pointer to constant c in linear sum a_1*x_1 + ... + a_n*x_n + c */
1818 SCIP_Bool transformed /**< transformed constraint? */
1819 )
1820 {
1821 int requiredsize;
1822 int v;
1823
1824 assert(scip != NULL);
1825 assert(vars != NULL);
1826 assert(scalars != NULL);
1827 assert(nvars != NULL);
1828 assert(constant != NULL);
1829
1830 if( transformed )
1831 {
1832 SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, scalars, nvars, *nvars, constant, &requiredsize, TRUE) );
1833
1834 if( requiredsize > *nvars )
1835 {
1836 SCIP_CALL( SCIPreallocBufferArray(scip, &vars, requiredsize) );
1837 SCIP_CALL( SCIPreallocBufferArray(scip, &scalars, requiredsize) );
1838
1839 SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, scalars, nvars, requiredsize, constant, &requiredsize, TRUE) );
1840 assert( requiredsize <= *nvars );
1841 }
1842 }
1843 else
1844 for( v = 0; v < *nvars; ++v )
1845 {
1846 SCIP_CALL( SCIPvarGetOrigvarSum(&vars[v], &scalars[v], constant) );
1847
1848 if( vars[v] == NULL )
1849 return SCIP_INVALIDDATA;
1850 }
1851
1852 return SCIP_OKAY;
1853 }
1854
1855 /* computes all and-resultants and their corresponding constraint variables */
1856 static
1857 SCIP_RETCODE computeAndConstraintInfos(
1858 SCIP*const scip, /**< SCIP data structure */
1859 SCIP_Bool const transformed, /**< transformed problem? */
1860 SCIP_VAR*** resvars, /**< pointer to store all resultant variables */
1861 int* nresvars, /**< pointer to store the number of all resultant variables */
1862 SCIP_VAR**** andvars, /**< pointer to store to all resultant variables their corresponding active( or negated) and-constraint variables */
1863 int** nandvars, /**< pointer to store the number of all corresponding and-variables to their corresponding resultant variable */
1864 SCIP_Bool*const existandconshdlr, /**< pointer to store whether the and-constrainthandler exists*/
1865 SCIP_Bool*const existands /**< pointer to store if their exists some and-constraints */
1866 )
1867 {
1868 SCIP_CONSHDLR* conshdlr;
1869
1870 assert(scip != NULL);
1871 assert(resvars != NULL);
1872 assert(nresvars != NULL);
1873 assert(andvars != NULL);
1874 assert(nandvars != NULL);
1875 assert(existandconshdlr != NULL);
1876 assert(existands != NULL);
1877
1878 *resvars = NULL;
1879 *nandvars = NULL;
1880 *andvars = NULL;
1881 *nresvars = 0;
1882
1883 /* detect all and-resultants */
1884 conshdlr = SCIPfindConshdlr(scip, "and");
1885 if( conshdlr != NULL )
1886 {
1887 SCIP_CONS** andconss;
1888 int nandconss;
1889 int* shouldnotbeinand;
1890 int a;
1891 int c;
1892 int r;
1893 int v;
1894 int pos;
1895 int ncontainedands;
1896
1897 andconss = NULL;
1898 nandconss = 0;
1899 *existandconshdlr = TRUE;
1900
1901 /* if we write the original problem we need to get the original and constraints */
1902 if( !transformed )
1903 {
1904 SCIP_CONS** origconss;
1905 int norigconss;
1906
1907 origconss = SCIPgetOrigConss(scip);
1908 norigconss = SCIPgetNOrigConss(scip);
1909
1910 /* allocate memory for all possible and-constraints */
1911 SCIP_CALL( SCIPallocBufferArray(scip, &andconss, norigconss) );
1912
1913 /* collect all original and-constraints */
1914 for( c = norigconss - 1; c >= 0; --c )
1915 {
1916 conshdlr = SCIPconsGetHdlr(origconss[c]);
1917 assert( conshdlr != NULL );
1918
1919 if( strcmp(SCIPconshdlrGetName(conshdlr), "and") == 0 )
1920 {
1921 andconss[nandconss] = origconss[c];
1922 ++nandconss;
1923 }
1924 }
1925 }
1926 else
1927 {
1928 nandconss = SCIPconshdlrGetNConss(conshdlr);
1929 andconss = SCIPconshdlrGetConss(conshdlr);
1930 }
1931
1932 assert(andconss != NULL || nandconss == 0);
1933
1934 *nresvars = nandconss;
1935
1936 if( nandconss > 0 )
1937 {
1938 *existands = TRUE;
1939
1940 assert(andconss != NULL);
1941
1942 SCIP_CALL( SCIPallocMemoryArray(scip, resvars, *nresvars) );
1943 SCIP_CALL( SCIPallocMemoryArray(scip, andvars, *nresvars) );
1944 SCIP_CALL( SCIPallocMemoryArray(scip, nandvars, *nresvars) );
1945
1946 /* collect all and-constraint variables */
1947 for( c = nandconss - 1; c >= 0; --c )
1948 {
1949 SCIP_VAR** scipandvars;
1950
1951 assert(andconss[c] != NULL);
1952
1953 scipandvars = SCIPgetVarsAnd(scip, andconss[c]);
1954 (*nandvars)[c] = SCIPgetNVarsAnd(scip, andconss[c]);
1955 SCIP_CALL( SCIPduplicateMemoryArray(scip, &((*andvars)[c]), scipandvars, (*nandvars)[c]) ); /*lint !e866 */
1956 SCIP_CALL( getBinVarsRepresentatives(scip, (*andvars)[c], (*nandvars)[c], transformed) );
1957
1958 (*resvars)[c] = SCIPgetResultantAnd(scip, andconss[c]);
1959
1960 assert((*andvars)[c] != NULL && (*nandvars)[c] > 0);
1961 assert((*resvars)[c] != NULL);
1962 }
1963
1964 /* sorted the array */
1965 SCIPsortPtrPtrInt((void**)(*resvars), (void**)(*andvars), (*nandvars), SCIPvarComp, (*nresvars));
1966 }
1967 else
1968 *existands = FALSE;
1969
1970 SCIP_CALL( SCIPallocBufferArray(scip, &shouldnotbeinand, *nresvars) );
1971
1972 /* check that all and-constraints doesn't contain any and-resultants, if they do try to resolve this */
1973 /* attention: if resolving leads to x = x*y*... , we can't do anything here ( this only means (... >=x and) y >= x, so normally the and-constraint needs to be
1974 deleted and the inequality from before needs to be added ) */
1975 assert(*nandvars != NULL || *nresvars == 0);
1976 for( r = *nresvars - 1; r >= 0; --r )
1977 {
1978 ncontainedands = 0;
1979 shouldnotbeinand[ncontainedands] = r;
1980 ++ncontainedands;
1981 v = 0;
1982
1983 assert(*nandvars != NULL);
1984 while( v < (*nandvars)[r] )
1985 {
1986 assert(*andvars != NULL);
1987 assert(*resvars != NULL);
1988 if( SCIPsortedvecFindPtr((void**)(*resvars), SCIPvarComp, (*andvars)[r][v], *nresvars, &pos) )
1989 {
1990 /* check if the found position "pos" is equal to an already visited and resultant in this constraint,
1991 * than here could exist a directed cycle
1992 */
1993 /* better use tarjan's algorithm
1994 * <http://algowiki.net/wiki/index.php?title=Tarjan%27s_algorithm>,
1995 * <http://en.wikipedia.org/wiki/Tarjan%E2%80%99s_strongly_connected_components_algorithm>
1996 * because it could be that the same resultant is part of this and-constraint and than it would fail
1997 * without no cycle
1998 * Note1: tarjans standard algorithm doesn't find cycle from one node to the same;
1999 * Note2: when tarjan's algorithm find a cycle, it's still possible that this cycle is not "real" e.g.
2000 * y = y ~y z (z can also be a product) where y = 0 follows and therefor only "0 = z" is necessary
2001 */
2002 for( a = ncontainedands - 1; a >= 0; --a )
2003 if( shouldnotbeinand[a] == pos )
2004 {
2005 SCIPwarningMessage(scip, "This should not happen here. The and-constraint with resultant variable: ");
2006 SCIP_CALL( SCIPprintVar(scip, (*resvars)[r], NULL) );
2007 SCIPwarningMessage(scip, "possible contains a loop with and-resultant:");
2008 SCIP_CALL( SCIPprintVar(scip, (*resvars)[pos], NULL) );
2009
2010 /* free memory iff necessary */
2011 SCIPfreeBufferArray(scip, &shouldnotbeinand);
2012 if( !transformed )
2013 {
2014 SCIPfreeBufferArray(scip, &andconss);
2015 }
2016 return SCIP_INVALIDDATA;
2017 }
2018 SCIPdebugMsg(scip, "Another and-constraint contains and-resultant:");
2019 SCIPdebug( SCIP_CALL( SCIPprintVar(scip, (*resvars)[pos], NULL) ) );
2020 SCIPdebugMsg(scip, "Trying to resolve.\n");
2021
2022 shouldnotbeinand[ncontainedands] = pos;
2023 ++ncontainedands;
2024
2025 /* try to resolve containing ands */
2026
2027 /* resize array and number of variables */
2028 (*nandvars)[r] = (*nandvars)[r] + (*nandvars)[pos] - 1;
2029 SCIP_CALL( SCIPreallocMemoryArray(scip, &((*andvars)[r]), (*nandvars)[r]) ); /*lint !e866 */
2030
2031 /* copy all variables */
2032 for( a = (*nandvars)[pos] - 1; a >= 0; --a )
2033 (*andvars)[r][(*nandvars)[r] - a - 1] = (*andvars)[pos][a];
2034
2035 /* check same position with new variable, so we do not increase v */
2036 }
2037 else
2038 ++v;
2039 }
2040 }
2041 SCIPfreeBufferArray(scip, &shouldnotbeinand);
2042
2043 /* free memory iff necessary */
2044 if( !transformed )
2045 {
2046 SCIPfreeBufferArray(scip, &andconss);
2047 }
2048 }
2049 else
2050 {
2051 SCIPdebugMsg(scip, "found no and-constraint-handler\n");
2052 *existands = FALSE;
2053 *existandconshdlr = FALSE;
2054 }
2055
2056 return SCIP_OKAY;
2057 }
2058
2059 /** clears the given line buffer */
2060 static
2061 void clearBuffer(
2062 char* linebuffer, /**< line */
2063 int* linecnt /**< number of characters in line */
2064 )
2065 {
2066 assert( linebuffer != NULL );
2067 assert( linecnt != NULL );
2068
2069 (*linecnt) = 0;
2070 linebuffer[0] = '\0';
2071 }
2072
2073
2074 /** ends the given line with '\\0' and prints it to the given file stream */
2075 static
2076 void writeBuffer(
2077 SCIP* scip, /**< SCIP data structure */
2078 FILE* file, /**< output file (or NULL for standard output) */
2079 char* linebuffer, /**< line */
2080 int* linecnt /**< number of characters in line */
2081 )
2082 {
2083 assert( scip != NULL );
2084 assert( linebuffer != NULL );
2085 assert( linecnt != NULL );
2086 assert( 0 <= *linecnt && *linecnt < OPB_MAX_LINELEN );
2087
2088 if( (*linecnt) > 0 )
2089 {
2090 linebuffer[(*linecnt)] = '\0';
2091 SCIPinfoMessage(scip, file, "%s", linebuffer);
2092 clearBuffer(linebuffer, linecnt);
2093 }
2094 }
2095
2096
2097 /** appends extension to line and prints it to the give file stream if the line buffer get full */
2098 static
2099 void appendBuffer(
2100 SCIP* scip, /**< SCIP data structure */
2101 FILE* file, /**< output file (or NULL for standard output) */
2102 char* linebuffer, /**< line buffer */
2103 int* linecnt, /**< number of characters in line */
2104 const char* extension /**< string to extent the line */
2105 )
2106 {
2107 assert(scip != NULL);
2108 assert(linebuffer != NULL);
2109 assert(linecnt != NULL);
2110 assert(extension != NULL);
2111
2112 if( (*linecnt) + (int) strlen(extension) >= OPB_MAX_LINELEN - 1 )
2113 writeBuffer(scip, file, linebuffer, linecnt);
2114
2115 /* append extension to linebuffer */
2116 (void) strncat(linebuffer, extension, OPB_MAX_LINELEN - (unsigned int)(*linecnt));
2117 (*linecnt) += (int) strlen(extension);
2118 }
2119
2120 /** write objective function */
2121 static
2122 SCIP_RETCODE writeOpbObjective(
2123 SCIP*const scip, /**< SCIP data structure */
2124 FILE*const file, /**< output file, or NULL if standard output should be used */
2125 SCIP_VAR**const vars, /**< array with active (binary) variables */
2126 int const nvars, /**< number of active variables in the problem */
2127 SCIP_VAR** const resvars, /**< array of resultant variables */
2128 int const nresvars, /**< number of resultant variables */
2129 SCIP_VAR**const*const andvars, /**< corresponding array of and-variables */
2130 int const*const nandvars, /**< array of numbers of corresponding and-variables */
2131 SCIP_OBJSENSE const objsense, /**< objective sense */
2132 SCIP_Real const objscale, /**< scalar applied to objective function; external objective value is
2133 * extobj = objsense * objscale * (intobj + objoffset) */
2134 SCIP_Real const objoffset, /**< objective offset from bound shifting and fixing */
2135 char const*const multisymbol, /**< the multiplication symbol to use between coefficient and variable */
2136 SCIP_Bool const existands, /**< does some and-constraints exist? */
2137 SCIP_Bool const transformed /**< TRUE iff problem is the transformed problem */
2138 )
2139 {
2140 SCIP_VAR* var;
2141 char linebuffer[OPB_MAX_LINELEN+1];
2142 char buffer[OPB_MAX_LINELEN];
2143 SCIP_Longint mult;
2144 SCIP_Bool objective;
2145 int v;
2146 int linecnt;
2147 int pos;
2148
2149 assert(scip != NULL);
2150 assert(file != NULL);
2151 assert(vars != NULL || nvars == 0);
2152 assert(resvars != NULL || nresvars == 0);
2153 assert(andvars != NULL || nandvars == NULL);
2154 assert(multisymbol != NULL);
2155
2156 mult = 1;
2157 objective = FALSE;
2158
2159 clearBuffer(linebuffer, &linecnt);
2160
2161 /* check if a objective function exits and compute the multiplier to
2162 * shift the coefficients to integers */
2163 for( v = 0; v < nvars; ++v )
2164 {
2165 var = vars[v]; /*lint !e613 */
2166
2167 #ifndef NDEBUG
2168 {
2169 /* in case the original problem has to be posted the variables have to be either "original" or "negated" */
2170 if( !transformed )
2171 assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_ORIGINAL ||
2172 SCIPvarGetStatus(var) == SCIP_VARSTATUS_NEGATED );
2173 }
2174 #endif
2175
2176 /* we found a indicator variable so we assume this is a wbo file */
2177 if( strstr(SCIPvarGetName(var), INDICATORVARNAME) != NULL )
2178 {
2179 /* find the topcost linear inequality which gives us the maximal cost which could be violated by our
2180 * solution, which is an artificial constraint and print this at first
2181 *
2182 * @note: only linear constraint handler is enough in problem stage, otherwise it could be any upgraded linear
2183 * constraint which handles pure binary variables
2184 */
2185 SCIP_CONSHDLR* conshdlr;
2186 SCIP_CONS* topcostcons;
2187 SCIP_Bool printed;
2188
2189 printed = FALSE;
2190 topcostcons = SCIPfindCons(scip, TOPCOSTCONSNAME);
2191
2192 if( topcostcons != NULL )
2193 {
2194 conshdlr = SCIPconsGetHdlr(topcostcons);
2195 assert(conshdlr != NULL);
2196
2197 if( strcmp(SCIPconshdlrGetName(conshdlr), "linear") == 0 )
2198 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "soft: %g;\n", SCIPgetRhsLinear(scip, topcostcons));
2199 else if( strcmp(SCIPconshdlrGetName(conshdlr), "knapsack") == 0 )
2200 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "soft: %SCIP_LONGINT_FORMAT;\n",
(1) Event invalid_type: |
Argument "SCIPgetCapacityKnapsack(scip, topcostcons)" to format specifier "%S" was expected to have type "wchar_t *" but has type "long long". [details] |
2201 SCIPgetCapacityKnapsack(scip, topcostcons));
2202 else if( strcmp(SCIPconshdlrGetName(conshdlr), "setppc") == 0 )
2203 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "soft: 1;\n");
2204 else
2205 {
2206 SCIPABORT();
2207 return SCIP_INVALIDDATA; /*lint !e527 */
2208 }
2209 appendBuffer(scip, file, linebuffer, &linecnt, buffer);
2210 writeBuffer(scip, file, linebuffer, &linecnt);
2211 printed = TRUE;
2212 }
2213 /* following works only in transformed stage */
2214 else
2215 {
2216 /* first try linear constraints */
2217 conshdlr = SCIPfindConshdlr(scip, "linear");
2218
2219 if( conshdlr != NULL )
2220 {
2221 SCIP_CONS** conss;
2222 int nconss;
2223 int c;
2224
2225 conss = SCIPconshdlrGetConss(conshdlr);
2226 nconss = SCIPconshdlrGetNConss(conshdlr);
2227
2228 assert(conss != NULL || nconss == 0);
2229
2230 for( c = 0; c < nconss; ++c )
2231 {
2232 SCIP_VAR** linvars;
2233 int nlinvars;
2234 int w;
2235 SCIP_Bool topcostfound;
2236 SCIP_CONS* cons;
2237
2238 cons = conss[c]; /*lint !e613 */
2239 assert(cons != NULL);
2240
2241 linvars = SCIPgetVarsLinear(scip, cons);
2242 nlinvars = SCIPgetNVarsLinear(scip, cons);
2243
2244 assert(linvars != NULL || nlinvars == 0);
2245 topcostfound = FALSE;
2246
2247 for( w = 0; w < nlinvars; ++w )
2248 {
2249 if( strstr(SCIPvarGetName(linvars[w]), INDICATORVARNAME) != NULL ) /*lint !e613 */
2250 topcostfound = TRUE;
2251 else
2252 {
2253 assert(!topcostfound);
2254 topcostfound = FALSE;
2255 }
2256 }
2257
2258 if( topcostfound )
2259 {
2260 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "soft: %g;\n", SCIPgetRhsLinear(scip, cons));
2261 appendBuffer(scip, file, linebuffer, &linecnt, buffer);
2262 writeBuffer(scip, file, linebuffer, &linecnt);
2263 printed = TRUE;
2264 break;
2265 }
2266 }
2267 }
2268
2269 if( !printed )
2270 {
2271 /* second try knapsack constraints */
2272 conshdlr = SCIPfindConshdlr(scip, "knapsack");
2273
2274 if( conshdlr != NULL )
2275 {
2276 SCIP_CONS** conss;
2277 int nconss;
2278 int c;
2279
2280 conss = SCIPconshdlrGetConss(conshdlr);
2281 nconss = SCIPconshdlrGetNConss(conshdlr);
2282
2283 assert(conss != NULL || nconss == 0);
2284
2285 for( c = 0; c < nconss; ++c )
2286 {
2287 SCIP_VAR** topvars;
2288 int ntopvars;
2289 int w;
2290 SCIP_Bool topcostfound;
2291 SCIP_CONS* cons;
2292
2293 cons = conss[c]; /*lint !e613 */
2294 assert(cons != NULL);
2295
2296 topvars = SCIPgetVarsKnapsack(scip, cons);
2297 ntopvars = SCIPgetNVarsKnapsack(scip, cons);
2298
2299 assert(topvars != NULL || ntopvars == 0);
2300 topcostfound = FALSE;
2301
2302 for( w = 0; w < ntopvars; ++w )
2303 {
2304 if( strstr(SCIPvarGetName(topvars[w]), INDICATORVARNAME) != NULL ) /*lint !e613 */
2305 topcostfound = TRUE;
2306 else
2307 {
2308 assert(!topcostfound);
2309 topcostfound = FALSE;
2310 }
2311 }
2312
2313 if( topcostfound )
2314 {
2315 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "soft: %SCIP_LONGINT_FORMAT;\n",
2316 SCIPgetCapacityKnapsack(scip, cons));
2317 appendBuffer(scip, file, linebuffer, &linecnt, buffer);
2318 writeBuffer(scip, file, linebuffer, &linecnt);
2319 printed = TRUE;
2320 break;
2321 }
2322 }
2323 }
2324 }
2325
2326 if( !printed )
2327 {
2328 /* third try setppc constraints */
2329 conshdlr = SCIPfindConshdlr(scip, "setppc");
2330
2331 if( conshdlr != NULL )
2332 {
2333 SCIP_CONS** conss;
2334 int nconss;
2335 int c;
2336
2337 conss = SCIPconshdlrGetConss(conshdlr);
2338 nconss = SCIPconshdlrGetNConss(conshdlr);
2339
2340 assert(conss != NULL || nconss == 0);
2341
2342 for( c = 0; c < nconss; ++c )
2343 {
2344 SCIP_VAR** topvars;
2345 int ntopvars;
2346 int w;
2347 SCIP_Bool topcostfound;
2348 SCIP_CONS* cons;
2349
2350 cons = conss[c]; /*lint !e613 */
2351 assert(cons != NULL);
2352
2353 topvars = SCIPgetVarsSetppc(scip, cons);
2354 ntopvars = SCIPgetNVarsSetppc(scip, cons);
2355
2356 assert(topvars != NULL || ntopvars == 0);
2357 topcostfound = FALSE;
2358
2359 for( w = 0; w < ntopvars; ++w )
2360 {
2361 if( strstr(SCIPvarGetName(topvars[w]), INDICATORVARNAME) != NULL ) /*lint !e613 */
2362 topcostfound = TRUE;
2363 else
2364 {
2365 assert(!topcostfound);
2366 topcostfound = FALSE;
2367 }
2368 }
2369
2370 if( topcostfound )
2371 {
2372 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "soft: 1;\n");
2373 appendBuffer(scip, file, linebuffer, &linecnt, buffer);
2374 writeBuffer(scip, file, linebuffer, &linecnt);
2375 printed = TRUE;
2376 break;
2377 }
2378 }
2379 }
2380 }
2381 }
2382
2383 /* no topcost constraint found, so print empty topcost line, which means there is no upper bound on violated soft constraints */
2384 if( !printed )
2385 {
2386 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "soft: ;\n");
2387 appendBuffer(scip, file, linebuffer, &linecnt, buffer);
2388 writeBuffer(scip, file, linebuffer, &linecnt);
2389 }
2390
2391 return SCIP_OKAY;
2392 }
2393
2394 if( !SCIPisZero(scip, SCIPvarGetObj(var)) )
2395 {
2396 objective = TRUE;
2397 while( !SCIPisIntegral(scip, SCIPvarGetObj(var) * mult) )
2398 {
2399 assert(mult * 10 > mult);
2400 mult *= 10;
2401 }
2402 }
2403 }
2404
2405 if( objective )
2406 {
2407 /* there exist a objective function*/
2408 SCIPinfoMessage(scip, file, "* Obj. scale : %.15g\n", objscale * mult);
2409 SCIPinfoMessage(scip, file, "* Obj. offset : %.15g\n", objoffset);
2410
2411 clearBuffer(linebuffer, &linecnt);
2412
2413 /* opb format supports only minimization; therefore, a maximization problem has to be converted */
2414 if( objsense == SCIP_OBJSENSE_MAXIMIZE )
2415 mult *= -1;
2416
2417 SCIPdebugMsg(scip, "print objective function multiplied with %" SCIP_LONGINT_FORMAT "\n", mult);
2418
2419 appendBuffer(scip, file, linebuffer, &linecnt, "min:");
2420
2421 #ifndef NDEBUG
2422 if( existands )
2423 {
2424 int c;
2425 /* check that these variables are sorted */
2426 for( c = nresvars - 1; c > 0; --c )
2427 assert(SCIPvarGetIndex(resvars[c]) >= SCIPvarGetIndex(resvars[c - 1])); /*lint !e613 */
2428 }
2429 #endif
2430
2431 for( v = nvars - 1; v >= 0; --v )
2432 {
2433 SCIP_Bool negated;
2434 var = vars[v]; /*lint !e613 */
2435
2436 assert(var != NULL);
2437
2438 if( SCIPisZero(scip, SCIPvarGetObj(var)) )
2439 continue;
2440
2441 negated = SCIPvarIsNegated(var);
2442
2443 assert( linecnt != 0 );
2444
2445 if( SCIPvarGetObj(var) * mult > (SCIP_Real)SCIP_LONGINT_MAX )
2446 {
2447 SCIPerrorMessage("Integral objective value to big (mult = %" SCIP_LONGINT_FORMAT ", value = %g, mult*value = %g, printingvalue = %" SCIP_LONGINT_FORMAT ")for printing in opb format.\n", mult, SCIPvarGetObj(var), SCIPvarGetObj(var) * mult, (SCIP_Longint) SCIPround(scip, SCIPvarGetObj(var) * mult));
2448 }
2449
2450 /* replace and-resultant with corresponding variables */
2451 if( existands && SCIPsortedvecFindPtr((void**)resvars, SCIPvarComp, var, nresvars, &pos) )
2452 {
2453 int a;
2454
2455 assert(andvars != NULL);
2456 assert(nandvars != NULL);
2457 assert(pos >= 0 && nandvars[pos] > 0 && andvars[pos] != NULL);
2458 assert(andvars[pos][nandvars[pos] - 1] != NULL);
2459
2460 negated = SCIPvarIsNegated(andvars[pos][nandvars[pos] - 1]);
2461
2462 /* print and-vars */
2463 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, " %+" SCIP_LONGINT_FORMAT "%s%s%s",
2464 (SCIP_Longint) (SCIPvarGetObj(var) * mult), multisymbol, negated ? "~" : "",
2465 strstr(SCIPvarGetName(negated ? SCIPvarGetNegationVar(andvars[pos][nandvars[pos] - 1]) : andvars[pos][nandvars[pos] - 1]), "x"));
2466 appendBuffer(scip, file, linebuffer, &linecnt, buffer);
2467
2468 for(a = nandvars[pos] - 2; a >= 0; --a )
2469 {
2470 negated = SCIPvarIsNegated(andvars[pos][a]);
2471
2472 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "%s%s%s", multisymbol, negated ? "~" : "", strstr(SCIPvarGetName(negated ? SCIPvarGetNegationVar(andvars[pos][a]) : andvars[pos][a]), "x"));
2473 appendBuffer(scip, file, linebuffer, &linecnt, buffer);
2474 }
2475 }
2476 else
2477 {
2478 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, " %+" SCIP_LONGINT_FORMAT "%s%s%s",
2479 (SCIP_Longint) (SCIPvarGetObj(var) * mult), multisymbol, negated ? "~" : "", strstr(SCIPvarGetName(negated ? SCIPvarGetNegationVar(var) : var), "x"));
2480 appendBuffer(scip, file, linebuffer, &linecnt, buffer);
2481 }
2482 }
2483
2484 /* and objective function line ends with a ';' */
2485 appendBuffer(scip, file, linebuffer, &linecnt, " ;\n");
2486 writeBuffer(scip, file, linebuffer, &linecnt);
2487 }
2488
2489 return SCIP_OKAY;
2490 }
2491
2492 /* print maybe non linear row in OPB format to file stream */
2493 static
2494 SCIP_RETCODE printNLRow(
2495 SCIP*const scip, /**< SCIP data structure */
2496 FILE*const file, /**< output file (or NULL for standard output) */
2497 char const*const type, /**< row type ("=" or ">=") */
2498 SCIP_VAR**const vars, /**< array of variables */
2499 SCIP_Real const*const vals, /**< array of values */
2500 int const nvars, /**< number of variables */
2501 SCIP_Real lhs, /**< left hand side */
2502 SCIP_VAR** const resvars, /**< array of resultant variables */
2503 int const nresvars, /**< number of resultant variables */
2504 SCIP_VAR**const*const andvars, /**< corresponding array of and-variables */
2505 int const*const nandvars, /**< array of numbers of corresponding and-variables */
2506 SCIP_Longint weight, /**< if we found a soft constraint this is the weight, otherwise 0 */
2507 SCIP_Longint*const mult, /**< multiplier for the coefficients */
2508 char const*const multisymbol /**< the multiplication symbol to use between coefficient and variable */
2509 )
2510 {
2511 SCIP_VAR* var;
2512 char buffer[OPB_MAX_LINELEN];
2513 char linebuffer[OPB_MAX_LINELEN + 1];
2514 int v;
2515 int pos;
2516 int linecnt;
2517
2518 assert(scip != NULL);
2519 assert(strcmp(type, "=") == 0 || strcmp(type, ">=") == 0);
2520 assert(mult != NULL);
2521 assert(resvars != NULL);
2522 assert(nresvars > 0);
2523 assert(andvars != NULL && nandvars != NULL);
2524
2525 clearBuffer(linebuffer, &linecnt);
2526
2527 /* check if all coefficients are internal; if not commentstart multiplier */
2528 for( v = 0; v < nvars; ++v )
2529 {
2530 while( !SCIPisIntegral(scip, vals[v] * (*mult)) )
2531 {
2532 if( ABS(*mult) > ABS(*mult * 10) )
2533 return SCIP_INVALIDDATA;
2534 (*mult) *= 10;
2535 }
2536 }
2537
2538 while( !SCIPisIntegral(scip, lhs * (*mult)) )
2539 {
2540 if( ABS(*mult) > ABS(*mult * 10) )
2541 return SCIP_INVALIDDATA;
2542 (*mult) *= 10;
2543 }
2544
2545 /* print comment line if we have to multiply the coefficients to get integrals */
2546 if( ABS(*mult) != 1 )
2547 SCIPinfoMessage(scip, file, "* the following constraint is multiplied by %" SCIP_LONGINT_FORMAT " to get integral coefficients\n", ABS(*mult) );
2548
2549 #ifndef NDEBUG
2550 /* check that these variables are sorted */
2551 for( v = nresvars - 1; v > 0; --v )
2552 assert(SCIPvarGetIndex(resvars[v]) >= SCIPvarGetIndex(resvars[v - 1]));
2553 #endif
2554
2555 /* if we have a soft constraint print the weight*/
2556 if( weight != 0 )
2557 {
2558 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "[%+" SCIP_LONGINT_FORMAT "] ", weight);
2559 appendBuffer(scip, file, linebuffer, &linecnt, buffer);
2560 }
2561
2562 /* print coefficients */
2563 for( v = 0; v < nvars; ++v )
2564 {
2565 SCIP_Bool negated;
2566
2567 var = vars[v];
2568 assert( var != NULL );
2569
2570 negated = SCIPvarIsNegated(var);
2571
2572 /* replace and-resultant with corresponding variables */
2573 if( SCIPsortedvecFindPtr((void**)resvars, SCIPvarComp, var, nresvars, &pos) )
2574 {
2575 int a;
2576
2577 assert(andvars != NULL);
2578 assert(nandvars != NULL);
2579 assert(pos >= 0 && nandvars[pos] > 0 && andvars[pos] != NULL);
2580 assert(andvars[pos][nandvars[pos] - 1] != NULL);
2581
2582 negated = SCIPvarIsNegated(andvars[pos][nandvars[pos] - 1]);
2583
2584 if( vals[v] * (*mult) > (SCIP_Real)SCIP_LONGINT_MAX )
2585 {
2586 SCIPerrorMessage("Integral coefficient to big (mult = %" SCIP_LONGINT_FORMAT ", value = %g, mult*value = %g, printingvalue = %" SCIP_LONGINT_FORMAT ")for printing in opb format.\n", *mult, vals[v], vals[v] * (*mult), (SCIP_Longint) SCIPround(scip, vals[v] * (*mult)));
2587 }
2588
2589 /* print and-vars */
2590 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "%+" SCIP_LONGINT_FORMAT "%s%s%s",
2591 (SCIP_Longint) SCIPround(scip, vals[v] * (*mult)), multisymbol, negated ? "~" : "",
2592 strstr(SCIPvarGetName(negated ? SCIPvarGetNegationVar(andvars[pos][nandvars[pos] - 1]) : andvars[pos][nandvars[pos] - 1]), "x") );
2593 appendBuffer(scip, file, linebuffer, &linecnt, buffer);
2594
2595 for(a = nandvars[pos] - 2; a >= 0; --a )
2596 {
2597 negated = SCIPvarIsNegated(andvars[pos][a]);
2598
2599 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "%s%s%s", multisymbol, negated ? "~" : "", strstr(SCIPvarGetName(negated ? SCIPvarGetNegationVar(andvars[pos][a]) : andvars[pos][a]), "x"));
2600 appendBuffer(scip, file, linebuffer, &linecnt, buffer);
2601 }
2602
2603 appendBuffer(scip, file, linebuffer, &linecnt, " ");
2604 }
2605 else
2606 {
2607 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "%+" SCIP_LONGINT_FORMAT "%s%s%s ",
2608 (SCIP_Longint) SCIPround(scip, vals[v] * (*mult)), multisymbol, negated ? "~" : "", strstr(SCIPvarGetName(negated ? SCIPvarGetNegationVar(var) : var), "x"));
2609 appendBuffer(scip, file, linebuffer, &linecnt, buffer);
2610 }
2611 }
2612
2613 /* print left hand side */
2614 if( SCIPisZero(scip, lhs) )
2615 lhs = 0.0;
2616
2617 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "%s %" SCIP_LONGINT_FORMAT " ;\n", type, (SCIP_Longint) (lhs * (*mult)) );
2618 appendBuffer(scip, file, linebuffer, &linecnt, buffer);
2619
2620 writeBuffer(scip, file, linebuffer, &linecnt);
2621
2622 return SCIP_OKAY;
2623 }
2624
2625
2626 /** prints given maybe non-linear constraint information in OPB format to file stream */
2627 static
2628 SCIP_RETCODE printNonLinearCons(
2629 SCIP*const scip, /**< SCIP data structure */
2630 FILE*const file, /**< output file (or NULL for standard output) */
2631 SCIP_VAR**const vars, /**< array of variables */
2632 SCIP_Real*const vals, /**< array of coefficients values (or NULL if all coefficient values are 1) */
2633 int const nvars, /**< number of variables */
2634 SCIP_Real const lhs, /**< left hand side */
2635 SCIP_Real const rhs, /**< right hand side */
2636 SCIP_VAR** const resvars, /**< array of resultant variables */
2637 int const nresvars, /**< number of resultant variables */
2638 SCIP_VAR**const*const andvars, /**< corresponding array of and-variables */
2639 int const*const nandvars, /**< array of numbers of corresponding and-variables */
2640 SCIP_Longint weight, /**< if we found a soft constraint this is the weight, otherwise 0 */
2641 SCIP_Bool const transformed, /**< transformed constraint? */
2642 char const*const multisymbol /**< the multiplication symbol to use between coefficient and variable */
2643 )
2644 {
2645 SCIP_VAR** activevars;
2646 SCIP_Real* activevals;
2647 SCIP_Real activeconstant;
2648 SCIP_Longint mult;
2649 SCIP_RETCODE retcode;
2650 int v;
2651 int nactivevars;
2652
2653 assert(scip != NULL);
2654 assert(vars != NULL);
2655 assert(nvars > 0);
2656 assert(lhs <= rhs);
2657 assert(resvars != NULL);
2658 assert(nresvars > 0);
2659 assert(andvars != NULL && nandvars != NULL);
2660
2661 if( SCIPisInfinity(scip, -lhs) && SCIPisInfinity(scip, rhs) )
2662 return SCIP_OKAY;
2663
2664 activeconstant = 0.0;
2665 nactivevars = nvars;
2666
2667 /* duplicate variable and value array */
2668 SCIP_CALL( SCIPduplicateBufferArray(scip, &activevars, vars, nactivevars ) );
2669 if( vals != NULL )
2670 {
2671 SCIP_CALL( SCIPduplicateBufferArray(scip, &activevals, vals, nactivevars ) );
2672 }
2673 else
2674 {
2675 SCIP_CALL( SCIPallocBufferArray(scip, &activevals, nactivevars) );
2676
2677 for( v = 0; v < nactivevars; ++v )
2678 activevals[v] = 1.0;
2679 }
2680
2681 /* retransform given variables to active variables */
2682 SCIP_CALL( getActiveVariables(scip, activevars, activevals, &nactivevars, &activeconstant, transformed) );
2683
2684 mult = 1;
2685 retcode = SCIP_OKAY;
2686
2687 /* print row(s) in OPB format */
2688 if( SCIPisEQ(scip, lhs, rhs) )
2689 {
2690 assert( !SCIPisInfinity(scip, rhs) );
2691
2692 /* equality constraint */
2693 retcode = printNLRow(scip, file, "=", activevars, activevals, nactivevars, rhs - activeconstant, resvars,
2694 nresvars, andvars, nandvars, weight, &mult, multisymbol);
2695 }
2696 else
2697 {
2698 if( !SCIPisInfinity(scip, -lhs) )
2699 {
2700 /* print inequality ">=" */
2701 retcode = printNLRow(scip, file, ">=", activevars, activevals, nactivevars, lhs - activeconstant, resvars,
2702 nresvars, andvars, nandvars, weight, &mult, multisymbol);
2703 }
2704
2705 if( !SCIPisInfinity(scip, rhs) )
2706 {
2707 mult *= -1;
2708
2709 /* print inequality ">=" and multiplying all coefficients by -1 */
2710 retcode = printNLRow(scip, file, ">=", activevars, activevals, nactivevars, rhs - activeconstant, resvars,
2711 nresvars, andvars, nandvars, weight, &mult, multisymbol);
2712 }
2713 }
2714
2715 /* free buffer arrays */
2716 SCIPfreeBufferArray(scip, &activevars);
2717 SCIPfreeBufferArray(scip, &activevals);
2718
2719 return retcode;
2720 }
2721
2722
2723 /* print row in OPB format to file stream */
2724 static
2725 SCIP_RETCODE printRow(
2726 SCIP* scip, /**< SCIP data structure */
2727 FILE* file, /**< output file (or NULL for standard output) */
2728 const char* type, /**< row type ("=" or ">=") */
2729 SCIP_VAR** vars, /**< array of variables */
2730 SCIP_Real* vals, /**< array of values */
2731 int nvars, /**< number of variables */
2732 SCIP_Real lhs, /**< left hand side */
2733 SCIP_Longint weight, /**< if we found a soft constraint this is the weight, otherwise 0 */
2734 SCIP_Longint* mult, /**< multiplier for the coefficients */
2735 const char* multisymbol /**< the multiplication symbol to use between coefficient and variable */
2736 )
2737 {
2738 SCIP_VAR* var;
2739 char buffer[OPB_MAX_LINELEN];
2740 char linebuffer[OPB_MAX_LINELEN + 1];
2741 int v;
2742 int linecnt;
2743
2744 assert(scip != NULL);
2745 assert(strcmp(type, "=") == 0 || strcmp(type, ">=") == 0);
2746 assert(mult != NULL);
2747
2748 clearBuffer(linebuffer, &linecnt);
2749
2750 /* if we found the topcost linear inequality which gives us the maximal cost which could be violated by our solution,
2751 * we can stop printing because it is an artificial constraint
2752 */
2753 if( nvars > 0 && strstr(SCIPvarGetName(vars[0]), INDICATORVARNAME) != NULL )
2754 return SCIP_OKAY;
2755
2756 /* check if all coefficients are integral; if not commentstart multiplier */
2757 for( v = 0; v < nvars; ++v )
2758 {
2759 while( !SCIPisIntegral(scip, vals[v] * (*mult)) )
2760 {
2761 if( ABS(*mult) > ABS(*mult * 10) )
2762 return SCIP_INVALIDDATA;
2763 (*mult) *= 10;
2764 }
2765 }
2766
2767 while( !SCIPisIntegral(scip, lhs * (*mult)) )
2768 {
2769 if( ABS(*mult) > ABS(*mult * 10) )
2770 return SCIP_INVALIDDATA;
2771 (*mult) *= 10;
2772 }
2773
2774 /* print comment line if we have to multiply the coefficients to get integrals */
2775 if( ABS(*mult) != 1 )
2776 SCIPinfoMessage(scip, file, "* the following constraint is multiplied by %" SCIP_LONGINT_FORMAT " to get integral coefficients\n", ABS(*mult) );
2777
2778 /* if we have a soft constraint print the weight*/
2779 if( weight != 0 )
2780 {
2781 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "[%+" SCIP_LONGINT_FORMAT "] ", weight);
2782 appendBuffer(scip, file, linebuffer, &linecnt, buffer);
2783 }
2784
2785 /* print coefficients */
2786 for( v = 0; v < nvars; ++v )
2787 {
2788 SCIP_Bool negated;
2789
2790 var = vars[v];
2791 assert( var != NULL );
2792
2793 negated = SCIPvarIsNegated(var);
2794
2795 if( vals[v] * (*mult) > (SCIP_Real)SCIP_LONGINT_MAX )
2796 {
2797 SCIPerrorMessage("Integral coefficient to big (mult = %" SCIP_LONGINT_FORMAT ", value = %g, mult*value = %g, printingvalue = %" SCIP_LONGINT_FORMAT ")for printing in opb format.\n", *mult, vals[v], vals[v] * (*mult), (SCIP_Longint) SCIPround(scip, vals[v] * (*mult)));
2798 }
2799
2800 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "%+" SCIP_LONGINT_FORMAT "%s%s%s ",
2801 (SCIP_Longint) SCIPround(scip, vals[v] * (*mult)), multisymbol, negated ? "~" : "", strstr(SCIPvarGetName(negated ? SCIPvarGetNegationVar(var) : var), "x"));
2802 appendBuffer(scip, file, linebuffer, &linecnt, buffer);
2803 }
2804
2805 /* print left hand side */
2806 if( SCIPisZero(scip, lhs) )
2807 lhs = 0.0;
2808
2809 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "%s %" SCIP_LONGINT_FORMAT " ;\n", type, (SCIP_Longint) (lhs * (*mult)) );
2810 appendBuffer(scip, file, linebuffer, &linecnt, buffer);
2811
2812 writeBuffer(scip, file, linebuffer, &linecnt);
2813
2814 return SCIP_OKAY;
2815 }
2816
2817
2818 /** prints given linear constraint information in OPB format to file stream */
2819 static
2820 SCIP_RETCODE printLinearCons(
2821 SCIP* scip, /**< SCIP data structure */
2822 FILE* file, /**< output file (or NULL for standard output) */
2823 SCIP_VAR** vars, /**< array of variables */
2824 SCIP_Real* vals, /**< array of coefficients values (or NULL if all coefficient values are 1) */
2825 int nvars, /**< number of variables */
2826 SCIP_Real lhs, /**< left hand side */
2827 SCIP_Real rhs, /**< right hand side */
2828 SCIP_Longint weight, /**< if we found a soft constraint this is the weight, otherwise 0 */
2829 SCIP_Bool transformed, /**< transformed constraint? */
2830 const char* multisymbol /**< the multiplication symbol to use between coefficient and variable */
2831 )
2832 {
2833 SCIP_VAR** activevars;
2834 SCIP_Real* activevals;
2835 int nactivevars;
2836 SCIP_Real activeconstant;
2837 SCIP_Longint mult;
2838 SCIP_RETCODE retcode;
2839 int v;
2840
2841 assert( scip != NULL );
2842 assert( vars != NULL );
2843 assert( nvars > 0 );
2844 assert( lhs <= rhs );
2845
2846 if( SCIPisInfinity(scip, -lhs) && SCIPisInfinity(scip, rhs) )
2847 return SCIP_OKAY;
2848
2849 activeconstant = 0.0;
2850
2851 /* duplicate variable and value array */
2852 nactivevars = nvars;
2853 SCIP_CALL( SCIPduplicateBufferArray(scip, &activevars, vars, nactivevars ) );
2854 if( vals != NULL )
2855 {
2856 SCIP_CALL( SCIPduplicateBufferArray(scip, &activevals, vals, nactivevars ) );
2857 }
2858 else
2859 {
2860 SCIP_CALL( SCIPallocBufferArray(scip, &activevals, nactivevars) );
2861
2862 for( v = 0; v < nactivevars; ++v )
2863 activevals[v] = 1.0;
2864 }
2865
2866 /* retransform given variables to active variables */
2867 SCIP_CALL( getActiveVariables(scip, activevars, activevals, &nactivevars, &activeconstant, transformed) );
2868
2869 mult = 1;
2870 retcode = SCIP_OKAY;
2871
2872 /* print row(s) in OPB format */
2873 if( SCIPisEQ(scip, lhs, rhs) )
2874 {
2875 assert( !SCIPisInfinity(scip, rhs) );
2876
2877 /* equality constraint */
2878 retcode = printRow(scip, file, "=", activevars, activevals, nactivevars, rhs - activeconstant, weight, &mult,
2879 multisymbol);
2880 }
2881 else
2882 {
2883 if( !SCIPisInfinity(scip, -lhs) )
2884 {
2885 /* print inequality ">=" */
2886 retcode = printRow(scip, file, ">=", activevars, activevals, nactivevars, lhs - activeconstant, weight, &mult,
2887 multisymbol);
2888 }
2889
2890 if( !SCIPisInfinity(scip, rhs) )
2891 {
2892 mult *= -1;
2893
2894 /* print inequality ">=" and multiplying all coefficients by -1 */
2895 retcode = printRow(scip, file, ">=", activevars, activevals, nactivevars, rhs - activeconstant, weight, &mult,
2896 multisymbol);
2897 }
2898 }
2899
2900 /* free buffer arrays */
2901 SCIPfreeBufferArray(scip, &activevars);
2902 SCIPfreeBufferArray(scip, &activevals);
2903
2904 return retcode;
2905 }
2906
2907 /* print row in OPB format to file stream */
2908 static
2909 SCIP_RETCODE printPBRow(
2910 SCIP*const scip, /**< SCIP data structure */
2911 FILE*const file, /**< output file (or NULL for standard output) */
2912 const char* type, /**< row type ("=" or ">=") */
2913 SCIP_VAR**const linvars, /**< array of variables */
2914 SCIP_Real*const linvals, /**< array of values */
2915 int const nlinvars, /**< number of variables */
2916 SCIP_VAR***const termvars, /**< term array with array of variables to print */
2917 int*const ntermvars, /**< array with number of variables in each term */
2918 SCIP_Real*const termvals, /**< array of coefficient values for non-linear variables */
2919 int const ntermvals, /**< number non-linear variables in the problem */
2920 SCIP_Bool**const negatedarrays, /**< array of arrays to know which variable in a non-linear part is negated */
2921 SCIP_VAR*const indvar, /**< indicator variable, or NULL */
2922 SCIP_Real lhs, /**< left hand side */
2923 SCIP_Longint* mult, /**< multiplier for the coefficients */
2924 const char* multisymbol /**< the multiplication symbol to use between coefficient and variable */
2925 )
2926 {
2927 SCIP_VAR* var;
2928 char buffer[OPB_MAX_LINELEN];
2929 char linebuffer[OPB_MAX_LINELEN + 1];
2930 int v;
2931 int t;
2932 int linecnt;
2933
2934 assert(scip != NULL);
2935 assert(strcmp(type, "=") == 0 || strcmp(type, ">=") == 0);
2936 assert(linvars != NULL || nlinvars == 0);
2937 assert(linvals != NULL || nlinvars == 0);
2938 assert(termvars != NULL || ntermvals == 0);
2939 assert(ntermvars != NULL || ntermvals == 0);
2940 assert(termvals != NULL || ntermvals == 0);
2941 assert(negatedarrays != NULL || ntermvals == 0);
2942 assert(mult != NULL);
2943
2944 clearBuffer(linebuffer, &linecnt);
2945
2946 /* if we found the topcost linear inequality which gives us the maximal cost which could be violated by our solution,
2947 * we can stop printing because it is an artificial constraint
2948 */
2949 if( ntermvals == 0 && nlinvars > 0 && strstr(SCIPvarGetName(linvars[0]), INDICATORVARNAME) != NULL ) /*lint !e613 */
2950 return SCIP_OKAY;
2951
2952 /* check if all linear coefficients are internal; if not commentstart multiplier */
2953 for( v = 0; v < nlinvars; ++v )
2954 {
2955 while( !SCIPisIntegral(scip, linvals[v] * (*mult)) ) /*lint !e613 */
2956 {
2957 if( ABS(*mult) > ABS(*mult * 10) )
2958 return SCIP_INVALIDDATA;
2959 (*mult) *= 10;
2960 }
2961 }
2962
2963 /* check if all non-linear coefficients are internal; if not commentstart multiplier */
2964 for( v = 0; v < ntermvals; ++v )
2965 {
2966 while( !SCIPisIntegral(scip, termvals[v] * (*mult)) ) /*lint !e613 */
2967 {
2968 if( ABS(*mult) > ABS(*mult * 10) )
2969 return SCIP_INVALIDDATA;
2970 (*mult) *= 10;
2971 }
2972 }
2973
2974 while( !SCIPisIntegral(scip, lhs * (*mult)) )
2975 {
2976 if( ABS(*mult) > ABS(*mult * 10) )
2977 return SCIP_INVALIDDATA;
2978 (*mult) *= 10;
2979 }
2980
2981 /* print comment line if we have to multiply the coefficients to get integrals */
2982 if( ABS(*mult) != 1 )
2983 SCIPinfoMessage(scip, file, "* the following constraint is multiplied by %" SCIP_LONGINT_FORMAT " to get integral coefficients\n", ABS(*mult) );
2984
2985 /* if indicator variable exist we have a soft constraint */
2986 if( indvar != NULL )
2987 {
2988 SCIP_Real weight;
2989
2990 weight = SCIPvarGetObj(indvar);
2991 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "[%+g] ", weight);
2992 appendBuffer(scip, file, linebuffer, &linecnt, buffer);
2993 }
2994
2995 /* print linear part */
2996 for( v = 0; v < nlinvars; ++v )
2997 {
2998 SCIP_Bool negated;
2999
3000 var = linvars[v]; /*lint !e613 */
3001 assert(var != NULL);
3002
3003 negated = SCIPvarIsNegated(var);
3004
3005 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "%+" SCIP_LONGINT_FORMAT "%s%s%s ",
3006 (SCIP_Longint) SCIPround(scip, linvals[v] * (*mult)), multisymbol, negated ? "~" : "", strstr(SCIPvarGetName(negated ? SCIPvarGetNegationVar(var) : var), "x")); /*lint !e613 */
3007 appendBuffer(scip, file, linebuffer, &linecnt, buffer);
3008 }
3009
3010 /* print non-linear part */
3011 for( t = 0; t < ntermvals; ++t )
3012 {
3013 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "%+" SCIP_LONGINT_FORMAT, (SCIP_Longint) SCIPround(scip, termvals[t] * (*mult))); /*lint !e613 */
3014 appendBuffer(scip, file, linebuffer, &linecnt, buffer);
3015
3016 for( v = 0; v < ntermvars[t]; ++v ) /*lint !e613 */
3017 {
3018 SCIP_Bool negated;
3019
3020 var = termvars[t][v]; /*lint !e613 */
3021 assert(var != NULL);
3022
3023 negated = negatedarrays[t][v]; /*lint !e613 */
3024
3025 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "%s%s%s", multisymbol, negated ? "~" : "", strstr(SCIPvarGetName(negated ? SCIPvarGetNegationVar(var) : var), "x"));
3026 appendBuffer(scip, file, linebuffer, &linecnt, buffer);
3027 }
3028 appendBuffer(scip, file, linebuffer, &linecnt, " ");
3029 }
3030
3031 /* print left hand side */
3032 if( SCIPisZero(scip, lhs) )
3033 lhs = 0.0;
3034
3035 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "%s %" SCIP_LONGINT_FORMAT " ;\n", type, (SCIP_Longint) (lhs * (*mult)) );
3036 appendBuffer(scip, file, linebuffer, &linecnt, buffer);
3037
3038 writeBuffer(scip, file, linebuffer, &linecnt);
3039
3040 return SCIP_OKAY;
3041 }
3042
3043
3044 /** prints given pseudo boolean constraint information in OPB format to file stream */
3045 static
3046 SCIP_RETCODE printPseudobooleanCons(
3047 SCIP*const scip, /**< SCIP data structure */
3048 FILE*const file, /**< output file, or NULL if standard output should be used */
3049 SCIP_VAR**const linvars, /**< array with variables of linear part */
3050 SCIP_Real*const linvals, /**< array of coefficients values of linear part */
3051 int const nlinvars, /**< number variables in linear part of the problem */
3052 SCIP_VAR***const termvars, /**< term array with array of variables to print */
3053 int*const ntermvars, /**< array with number of variables in each term */
3054 SCIP_Real*const termvals, /**< array of coefficient values for non-linear variables */
3055 int const ntermvals, /**< number non-linear variables in the problem */
3056 SCIP_VAR*const indvar, /**< indicator variable, or NULL */
3057 SCIP_Real const lhs, /**< left hand side of constraint */
3058 SCIP_Real const rhs, /**< right hand side of constraint */
3059 SCIP_Bool transformed, /**< should the transformed problem be printed ? */
3060 const char* multisymbol /**< the multiplication symbol to use between coefficient and variable */
3061 )
3062 {
3063 SCIP_VAR*** activetermvars;
3064 SCIP_Bool** negatedarrays;
3065 SCIP_VAR** activelinvars;
3066 SCIP_Real* activelinvals;
3067 int nactivelinvars;
3068 SCIP_Real activelinconstant;
3069 SCIP_Longint mult;
3070 SCIP_RETCODE retcode;
3071 int v;
3072
3073 assert(scip != NULL);
3074 assert(linvars != NULL || nlinvars == 0);
3075 assert(linvals != NULL || nlinvars == 0);
3076 assert(termvars != NULL || 0 == ntermvals);
3077 assert(ntermvars != NULL || 0 == ntermvals);
3078 assert(termvals != NULL || 0 == ntermvals);
3079 assert(lhs <= rhs);
3080
3081 if( SCIPisInfinity(scip, -lhs) && SCIPisInfinity(scip, rhs) )
3082 return SCIP_OKAY;
3083
3084 activelinconstant = 0.0;
3085
3086 /* duplicate variable and value array for linear part */
3087 nactivelinvars = nlinvars;
3088 if( nactivelinvars > 0 )
3089 {
3090 SCIP_CALL( SCIPduplicateBufferArray(scip, &activelinvars, linvars, nactivelinvars ) );
3091 SCIP_CALL( SCIPduplicateBufferArray(scip, &activelinvals, linvals, nactivelinvars ) );
3092
3093 /* retransform given variables to active variables */
3094 SCIP_CALL( getActiveVariables(scip, activelinvars, activelinvals, &nactivelinvars, &activelinconstant, transformed) );
3095 }
3096 else
3097 {
3098 activelinvars = NULL;
3099 activelinvals = NULL;
3100 }
3101
3102 /* create non-linear information for printing */
3103 if( ntermvals > 0 )
3104 {
3105 assert(termvars != NULL);
3106 assert(ntermvars != NULL);
3107 assert(termvals != NULL);
3108
3109 SCIP_CALL( SCIPallocBufferArray(scip, &activetermvars, ntermvals) );
3110 SCIP_CALL( SCIPallocBufferArray(scip, &negatedarrays, ntermvals) );
3111 for( v = ntermvals - 1; v >= 0; --v )
3112 {
3113 assert(ntermvars[v] > 0); /*lint !e613 */
3114
3115 if( transformed )
3116 {
3117 SCIP_CALL( SCIPallocBufferArray(scip, &(activetermvars[v]), ntermvars[v]) ); /*lint !e866 */
3118 SCIP_CALL( SCIPallocBufferArray(scip, &(negatedarrays[v]), ntermvars[v]) ); /*lint !e866 */
3119
3120 /* get binary representatives of binary variables in non-linear terms */
3121 SCIP_CALL( SCIPgetBinvarRepresentatives(scip, ntermvars[v], termvars[v], activetermvars[v], negatedarrays[v]) );
3122 }
3123 else
3124 {
3125 SCIP_CALL( SCIPduplicateBufferArray(scip, &(activetermvars[v]), termvars[v], ntermvars[v]) ); /*lint !e866 */
3126 SCIP_CALL( SCIPallocBufferArray(scip, &(negatedarrays[v]), ntermvars[v]) ); /*lint !e866 */
3127 BMSclearMemoryArray(negatedarrays[v], ntermvars[v]); /*lint !e866 */
3128 }
3129 }
3130 }
3131 else
3132 {
3133 activetermvars = NULL;
3134 negatedarrays = NULL;
3135 }
3136
3137 mult = 1;
3138 retcode = SCIP_OKAY;
3139
3140 /* print row(s) in OPB format */
3141 if( SCIPisEQ(scip, lhs, rhs) )
3142 {
3143 assert( !SCIPisInfinity(scip, rhs) );
3144
3145 /* equality constraint */
3146 retcode = printPBRow(scip, file, "=", activelinvars, activelinvals, nactivelinvars, activetermvars,
3147 ntermvars, termvals, ntermvals, negatedarrays, indvar, rhs - activelinconstant, &mult, multisymbol);
3148 }
3149 else
3150 {
3151 if( !SCIPisInfinity(scip, -lhs) )
3152 {
3153 /* print inequality ">=" */
3154 retcode = printPBRow(scip, file, ">=", activelinvars, activelinvals, nactivelinvars, activetermvars,
3155 ntermvars, termvals, ntermvals, negatedarrays, indvar, lhs - activelinconstant, &mult, multisymbol);
3156 }
3157
3158 if( !SCIPisInfinity(scip, rhs) )
3159 {
3160 mult *= -1;
3161
3162 /* print inequality ">=" and multiplying all coefficients by -1 */
3163 /* coverity[var_deref_model] */
3164 retcode = printPBRow(scip, file, ">=", activelinvars, activelinvals, nactivelinvars, activetermvars,
3165 ntermvars, termvals, ntermvals, negatedarrays, indvar, rhs - activelinconstant, &mult, multisymbol);
3166 }
3167 }
3168
3169 /* free buffers for non-linear arrays */
3170 if( ntermvals > 0 )
3171 {
3172 assert(negatedarrays != NULL);
3173 assert(activetermvars != NULL);
3174
3175 for( v = 0; v < ntermvals; ++v )
3176 {
3177 assert(negatedarrays[v] != NULL);
3178 assert(activetermvars[v] != NULL);
3179 SCIPfreeBufferArray(scip, &(negatedarrays[v]));
3180 SCIPfreeBufferArray(scip, &(activetermvars[v]));
3181 }
3182 SCIPfreeBufferArray(scip, &negatedarrays);
3183 SCIPfreeBufferArray(scip, &activetermvars);
3184 }
3185
3186 /* free buffer for linear arrays */
3187 if( nactivelinvars > 0 )
3188 {
3189 SCIPfreeBufferArray(scip, &activelinvars);
3190 SCIPfreeBufferArray(scip, &activelinvals);
3191 }
3192
3193 return retcode;
3194 }
3195
3196 /** determine total number of linear constraints split into lhs/rhs */
3197 static
3198 void determineTotalNumberLinearConss(
3199 SCIP*const scip, /**< SCIP data structure */
3200 SCIP_CONS**const conss, /**< array with constraints of the problem */
3201 int const nconss, /**< number of constraints in the problem */
3202 int* nlinearconss, /**< pointer to store the total number of linear constraints */
3203 int* nsplitlinearconss /**< pointer to store the total number of linear constraints split into lhs/rhs */
3204 )
3205 {
3206 SCIP_CONSHDLR* conshdlr;
3207 const char* conshdlrname;
3208 SCIP_CONS* cons;
3209 int c;
3210
3211 assert(scip != NULL);
3212 assert(conss != NULL || nconss == 0);
3213 assert(nlinearconss != NULL);
3214 assert(nsplitlinearconss != NULL);
3215
3216 *nlinearconss = 0;
3217 *nsplitlinearconss = 0;
3218
3219 /* loop over all constraints */
3220 for( c = 0; c < nconss; ++c )
3221 {
3222 cons = conss[c];
3223 assert(cons != NULL);
3224 conshdlr = SCIPconsGetHdlr(cons); /*lint !e613*/
3225 assert(conshdlr != NULL);
3226
3227 conshdlrname = SCIPconshdlrGetName(conshdlr);
3228
3229 if( strcmp(conshdlrname, "linear") == 0 )
3230 {
3231 if( ! SCIPisInfinity(scip, SCIPgetLhsLinear(scip, cons)) )
3232 ++(*nsplitlinearconss);
3233
3234 if( ! SCIPisInfinity(scip, SCIPgetRhsLinear(scip, cons)) )
3235 ++(*nsplitlinearconss);
3236
3237 ++(*nlinearconss);
3238 }
3239
3240 if( strcmp(conshdlrname, "varbound") == 0 )
3241 {
3242 if( ! SCIPisInfinity(scip, SCIPgetLhsVarbound(scip, cons)) )
3243 ++(*nsplitlinearconss);
3244
3245 if( ! SCIPisInfinity(scip, SCIPgetRhsVarbound(scip, cons)) )
3246 ++(*nsplitlinearconss);
3247
3248 ++(*nlinearconss);
3249 }
3250 }
3251 }
3252
3253 /** write constraints */
3254 static
3255 SCIP_RETCODE writeOpbConstraints(
3256 SCIP*const scip, /**< SCIP data structure */
3257 FILE*const file, /**< output file, or NULL if standard output should be used */
3258 SCIP_CONS**const conss, /**< array with constraints of the problem */
3259 int const nconss, /**< number of constraints in the problem */
3260 SCIP_VAR**const vars, /**< array with active (binary) variables */
3261 int const nvars, /**< number of active variables in the problem */
3262 SCIP_VAR** const resvars, /**< array of resultant variables */
3263 int const nresvars, /**< number of resultant variables */
3264 SCIP_VAR**const*const andvars, /**< corresponding array of and-variables */
3265 int const*const nandvars, /**< array of numbers of corresponding and-variables */
3266 char const*const multisymbol, /**< the multiplication symbol to use between coefficient and variable */
3267 SCIP_Bool const existandconshdlr, /**< does and-constrainthandler exist? */
3268 SCIP_Bool const existands, /**< does some and-constraints exist? */
3269 SCIP_Bool const transformed /**< TRUE iff problem is the transformed problem */
3270 )
3271 {
3272 SCIP_CONSHDLR* conshdlr;
3273 const char* conshdlrname;
3274 SCIP_CONS* cons;
3275 SCIP_VAR** consvars;
3276 SCIP_Real* consvals;
3277 SCIP_RETCODE retcode;
3278 int nconsvars;
3279 int v, c;
3280 SCIP_HASHMAP* linconssofindicatorsmap = NULL;
3281 SCIP_HASHMAP* linconssofpbsmap = NULL;
3282
3283 assert(scip != NULL);
3284 assert(file != NULL);
3285 assert(conss != NULL || nconss == 0);
3286 assert(vars != NULL || nvars == 0);
3287 assert(resvars != NULL || nresvars == 0);
3288 assert(andvars != NULL || nandvars == 0);
3289 assert(multisymbol != NULL);
3290
3291 if( transformed )
3292 {
3293 conshdlr = SCIPfindConshdlr(scip, "indicator");
3294
3295 /* find artificial linear constraints which correspond to indicator constraints to avoid double printing */
3296 if( conshdlr != NULL )
3297 {
3298 SCIP_CONS** indconss;
3299 int nindconss;
3300
3301 indconss = SCIPconshdlrGetConss(conshdlr);
3302 nindconss = SCIPconshdlrGetNConss(conshdlr);
3303 assert(indconss != NULL || nindconss == 0);
3304
3305 if( nindconss > 0 )
3306 {
3307 SCIP_CONS* lincons;
3308
3309 /* create the linear constraint of indicator constraints hash map */
3310 SCIP_CALL( SCIPhashmapCreate(&linconssofindicatorsmap, SCIPblkmem(scip), nindconss) );
3311 assert(indconss != NULL);
3312
3313 for( c = 0; c < nindconss; ++c )
3314 {
3315 assert(indconss[c] != NULL);
3316 lincons = SCIPgetLinearConsIndicator(indconss[c]);
3317 assert(lincons != NULL);
3318
3319 /* insert constraint into mapping between */
3320 SCIP_CALL( SCIPhashmapInsert(linconssofindicatorsmap, (void*)lincons, (void*)lincons) );
3321 }
3322 }
3323 }
3324
3325 conshdlr = SCIPfindConshdlr(scip, "pseudoboolean");
3326
3327 /* find artifical linear constraints which correspond to indicator constraints to avoid double printing */
3328 if( conshdlr != NULL )
3329 {
3330 SCIP_CONS** pbconss;
3331 int npbconss;
3332
3333 pbconss = SCIPconshdlrGetConss(conshdlr);
3334 npbconss = SCIPconshdlrGetNConss(conshdlr);
3335 assert(pbconss != NULL || npbconss == 0);
3336
3337 if( npbconss > 0 )
3338 {
3339 SCIP_CONS* lincons;
3340
3341 /* create the linear constraint of indicator constraints hash map */
3342 SCIP_CALL( SCIPhashmapCreate(&linconssofpbsmap, SCIPblkmem(scip), npbconss) );
3343
3344 for( c = 0; c < npbconss; ++c )
3345 {
3346 assert(pbconss[c] != NULL); /*lint !e613*/
3347 lincons = SCIPgetLinearConsPseudoboolean(scip, pbconss[c]); /*lint !e613*/
3348 assert(lincons != NULL);
3349
3350 /* insert constraint into mapping between */
3351 SCIP_CALL( SCIPhashmapInsert(linconssofpbsmap, (void*)lincons, (void*)lincons) );
3352 }
3353 }
3354 }
3355 }
3356 /* in original space we cannot ask the constraint handler for its constraints, therefore we have to loop over all
3357 * original to check for artificial linear once
3358 */
3359 else
3360 {
3361 SCIP_CONS* lincons;
3362 SCIP_Bool pbhashmapcreated = FALSE;
3363 SCIP_Bool indhashmapcreated = FALSE;
3364
3365 /* loop over all constraint for printing */
3366 for( c = 0; c < nconss; ++c )
3367 {
3368 conshdlr = SCIPconsGetHdlr(conss[c]); /*lint !e613*/
3369 assert(conshdlr != NULL);
3370
3371 conshdlrname = SCIPconshdlrGetName(conshdlr);
3372
3373 if( strcmp(conshdlrname, "pseudoboolean") == 0 )
3374 {
3375 if( !pbhashmapcreated )
3376 {
3377 /* create the linear constraint of indicator constraints hash map */
3378 SCIP_CALL( SCIPhashmapCreate(&linconssofpbsmap, SCIPblkmem(scip), nconss) );
3379 pbhashmapcreated = TRUE;
3380 }
3381
3382 lincons = SCIPgetLinearConsPseudoboolean(scip, conss[c]); /*lint !e613*/
3383 assert(lincons != NULL);
3384
3385 /* insert constraint into mapping between */
3386 SCIP_CALL( SCIPhashmapInsert(linconssofpbsmap, (void*)lincons, (void*)lincons) );
3387 }
3388 else if( strcmp(conshdlrname, "indicator") == 0 )
3389 {
3390 if( !indhashmapcreated )
3391 {
3392 /* create the linear constraint of indicator constraints hash map */
3393 SCIP_CALL( SCIPhashmapCreate(&linconssofindicatorsmap, SCIPblkmem(scip), nconss) );
3394 indhashmapcreated = TRUE;
3395 }
3396
3397 lincons = SCIPgetLinearConsIndicator(conss[c]); /*lint !e613*/
3398 assert(lincons != NULL);
3399
3400 /* insert constraint into mapping between */
3401 SCIP_CALL( SCIPhashmapInsert(linconssofindicatorsmap, (void*)lincons, (void*)lincons) );
3402 }
3403 }
3404 }
3405
3406 retcode = SCIP_OKAY;
3407 cons = NULL;
3408
3409 /* loop over all constraint for printing */
3410 for( c = 0; c < nconss && retcode == SCIP_OKAY; ++c )
3411 {
3412 SCIP_CONS* artcons;
3413
3414 artcons = NULL;
3415
3416 cons = conss[c]; /*lint !e613 */
3417 assert(cons != NULL);
3418
3419 conshdlr = SCIPconsGetHdlr(cons);
3420 assert(conshdlr != NULL);
3421
3422 conshdlrname = SCIPconshdlrGetName(conshdlr);
3423 assert(transformed == SCIPconsIsTransformed(cons));
3424
3425 /* in case the transformed is written only constraint are posted which are enabled in the current node */
3426 assert(!transformed || SCIPconsIsEnabled(cons));
3427
3428 if( linconssofpbsmap != NULL )
3429 artcons = (SCIP_CONS*) SCIPhashmapGetImage(linconssofpbsmap, (void*)cons);
3430 if( artcons == NULL && linconssofindicatorsmap != NULL )
3431 artcons = (SCIP_CONS*) SCIPhashmapGetImage(linconssofindicatorsmap, (void*)cons);
3432
3433 if( artcons == NULL )
3434 {
3435 if( strcmp(conshdlrname, "linear") == 0 )
3436 {
3437 if( SCIPgetNVarsLinear(scip, cons) == 0 )
3438 {
3439 if( SCIPisGT(scip, SCIPgetLhsLinear(scip, cons), SCIPgetRhsLinear(scip, cons)) )
3440 {
3441 SCIPerrorMessage("Cannot print empty violated constraint %s, %g <= %g is not fulfilled\n",
3442 SCIPconsGetName(cons), SCIPgetLhsLinear(scip, cons), SCIPgetRhsLinear(scip, cons));
3443 }
3444 continue;
3445 }
3446
3447 if( existands )
3448 {
3449 retcode = printNonLinearCons(scip, file,
3450 SCIPgetVarsLinear(scip, cons), SCIPgetValsLinear(scip, cons), SCIPgetNVarsLinear(scip, cons),
3451 SCIPgetLhsLinear(scip, cons), SCIPgetRhsLinear(scip, cons), resvars, nresvars, andvars, nandvars,
3452 0LL, transformed, multisymbol);
3453 }
3454 else
3455 {
3456 retcode = printLinearCons(scip, file,
3457 SCIPgetVarsLinear(scip, cons), SCIPgetValsLinear(scip, cons), SCIPgetNVarsLinear(scip, cons),
3458 SCIPgetLhsLinear(scip, cons), SCIPgetRhsLinear(scip, cons), 0LL, transformed, multisymbol);
3459 }
3460 }
3461 else if( strcmp(conshdlrname, "setppc") == 0 )
3462 {
3463 consvars = SCIPgetVarsSetppc(scip, cons);
3464 nconsvars = SCIPgetNVarsSetppc(scip, cons);
3465
3466 if( nconsvars == 0 )
3467 continue;
3468
3469 switch( SCIPgetTypeSetppc(scip, cons) )
3470 {
3471 case SCIP_SETPPCTYPE_PARTITIONING :
3472 if( existands )
3473 {
3474 retcode = printNonLinearCons(scip, file, consvars, NULL, nconsvars, 1.0, 1.0, resvars, nresvars,
3475 andvars, nandvars, 0LL, transformed, multisymbol);
3476 }
3477 else
3478 {
3479 retcode = printLinearCons(scip, file,
3480 consvars, NULL, nconsvars, 1.0, 1.0, 0LL, transformed, multisymbol);
3481 }
3482 break;
3483 case SCIP_SETPPCTYPE_PACKING :
3484 if( existands )
3485 {
3486 retcode = printNonLinearCons(scip, file,
3487 consvars, NULL, nconsvars, -SCIPinfinity(scip), 1.0, resvars, nresvars, andvars, nandvars,
3488 0LL, transformed, multisymbol);
3489 }
3490 else
3491 {
3492 retcode = printLinearCons(scip, file,
3493 consvars, NULL, nconsvars, -SCIPinfinity(scip), 1.0, 0LL, transformed, multisymbol);
3494 }
3495 break;
3496 case SCIP_SETPPCTYPE_COVERING :
3497 if( existands )
3498 {
3499 retcode = printNonLinearCons(scip, file,
3500 consvars, NULL, nconsvars, 1.0, SCIPinfinity(scip), resvars, nresvars, andvars, nandvars,
3501 0LL, transformed, multisymbol);
3502 }
3503 else
3504 {
3505 retcode = printLinearCons(scip, file,
3506 consvars, NULL, nconsvars, 1.0, SCIPinfinity(scip), 0LL, transformed, multisymbol);
3507 }
3508 break;
3509 }
3510 }
3511 else if( strcmp(conshdlrname, "logicor") == 0 )
3512 {
3513 if( SCIPgetNVarsLogicor(scip, cons) == 0 )
3514 continue;
3515
3516 if( existands )
3517 {
3518 retcode = printNonLinearCons(scip, file,
3519 SCIPgetVarsLogicor(scip, cons), NULL, SCIPgetNVarsLogicor(scip, cons), 1.0, SCIPinfinity(scip),
3520 resvars, nresvars, andvars, nandvars, 0LL, transformed, multisymbol);
3521 }
3522 else
3523 {
3524 retcode = printLinearCons(scip, file,
3525 SCIPgetVarsLogicor(scip, cons), NULL, SCIPgetNVarsLogicor(scip, cons),
3526 1.0, SCIPinfinity(scip), 0LL, transformed, multisymbol);
3527 }
3528 }
3529 else if( strcmp(conshdlrname, "knapsack") == 0 )
3530 {
3531 SCIP_Longint* weights;
3532
3533 consvars = SCIPgetVarsKnapsack(scip, cons);
3534 nconsvars = SCIPgetNVarsKnapsack(scip, cons);
3535
3536 if( nconsvars == 0 )
3537 continue;
3538
3539 /* copy Longint array to SCIP_Real array */
3540 weights = SCIPgetWeightsKnapsack(scip, cons);
3541 SCIP_CALL( SCIPallocBufferArray(scip, &consvals, nconsvars) );
3542 for( v = 0; v < nconsvars; ++v )
3543 consvals[v] = (SCIP_Real)weights[v];
3544
3545 if( existands )
3546 {
3547 retcode = printNonLinearCons(scip, file, consvars, consvals, nconsvars, -SCIPinfinity(scip),
3548 (SCIP_Real) SCIPgetCapacityKnapsack(scip, cons), resvars, nresvars, andvars, nandvars,
3549 0LL, transformed, multisymbol);
3550 }
3551 else
3552 {
3553 retcode = printLinearCons(scip, file, consvars, consvals, nconsvars, -SCIPinfinity(scip),
3554 (SCIP_Real) SCIPgetCapacityKnapsack(scip, cons), 0LL, transformed, multisymbol);
3555 }
3556
3557 SCIPfreeBufferArray(scip, &consvals);
3558 }
3559 else if( strcmp(conshdlrname, "varbound") == 0 )
3560 {
3561 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, 2) );
3562 SCIP_CALL( SCIPallocBufferArray(scip, &consvals, 2) );
3563
3564 consvars[0] = SCIPgetVarVarbound(scip, cons);
3565 consvars[1] = SCIPgetVbdvarVarbound(scip, cons);
3566
3567 consvals[0] = 1.0;
3568 consvals[1] = SCIPgetVbdcoefVarbound(scip, cons);
3569
3570 if( existands )
3571 {
3572 retcode = printNonLinearCons(scip, file, consvars, consvals, 2, SCIPgetLhsVarbound(scip, cons),
3573 SCIPgetRhsVarbound(scip, cons), resvars, nresvars, andvars, nandvars, 0LL, transformed, multisymbol);
3574 }
3575 else
3576 {
3577 retcode = printLinearCons(scip, file, consvars, consvals, 2, SCIPgetLhsVarbound(scip, cons),
3578 SCIPgetRhsVarbound(scip, cons), 0LL, transformed, multisymbol);
3579 }
3580
3581 SCIPfreeBufferArray(scip, &consvars);
3582 SCIPfreeBufferArray(scip, &consvals);
3583 }
3584 else if( strcmp(conshdlrname, "pseudoboolean") == 0 )
3585 {
3586 SCIP_VAR*** termvars;
3587 int* ntermvars;
3588 int termvarssize;
3589 SCIP_CONS** andconss;
3590 SCIP_Real* andcoefs ;
3591 SCIP_VAR** linvars;
3592 SCIP_Real* lincoefs ;
3593 int nlinvars;
3594 int t;
3595
3596 /* get the required array size for the variables array and for the number of variables in each variable array */
3597 termvarssize = SCIPgetNAndsPseudoboolean(scip, cons);
3598 assert(termvarssize >= 0);
3599
3600 /* allocate temporary memory */
3601 SCIP_CALL( SCIPallocBufferArray(scip, &andconss, termvarssize) );
3602 SCIP_CALL( SCIPallocBufferArray(scip, &termvars, termvarssize) );
3603 SCIP_CALL( SCIPallocBufferArray(scip, &andcoefs, termvarssize) );
3604 SCIP_CALL( SCIPallocBufferArray(scip, &ntermvars, termvarssize) );
3605
3606 /* get all corresponding and-constraints and therefor all variables */
3607 SCIP_CALL( SCIPgetAndDatasPseudoboolean(scip, cons, andconss, andcoefs, &termvarssize) );
3608 for( t = termvarssize - 1; t >= 0; --t )
3609 {
3610 termvars[t] = SCIPgetVarsAnd(scip, andconss[t]);
3611 ntermvars[t] = SCIPgetNVarsAnd(scip, andconss[t]);
3612 }
3613
3614 /* gets number of linear variables without artificial terms variables of pseudoboolean constraint */
3615 nlinvars = SCIPgetNLinVarsWithoutAndPseudoboolean(scip, cons);
3616
3617 /* allocate temporary memory */
3618 SCIP_CALL( SCIPallocBufferArray(scip, &linvars, nlinvars) );
3619 SCIP_CALL( SCIPallocBufferArray(scip, &lincoefs, nlinvars) );
3620
3621 /* gets linear constraint of pseudoboolean constraint */
3622 SCIP_CALL( SCIPgetLinDatasWithoutAndPseudoboolean(scip, cons, linvars, lincoefs, &nlinvars) );
3623
3624 retcode = printPseudobooleanCons(scip, file, linvars, lincoefs, nlinvars,
3625 termvars, ntermvars, andcoefs, termvarssize, SCIPgetIndVarPseudoboolean(scip, cons),
3626 SCIPgetLhsPseudoboolean(scip, cons), SCIPgetRhsPseudoboolean(scip, cons), transformed, multisymbol);
3627
3628 /* free temporary memory */
3629 SCIPfreeBufferArray(scip, &lincoefs);
3630 SCIPfreeBufferArray(scip, &linvars);
3631 SCIPfreeBufferArray(scip, &ntermvars);
3632 SCIPfreeBufferArray(scip, &andcoefs);
3633 SCIPfreeBufferArray(scip, &termvars);
3634 SCIPfreeBufferArray(scip, &andconss);
3635 }
3636 else if( strcmp(conshdlrname, "indicator") == 0 )
3637 {
3638 SCIP_CONS* lincons;
3639 SCIP_VAR* indvar;
3640 SCIP_VAR* slackvar;
3641 SCIP_Longint weight;
3642
3643 /* get artificial binary indicator variables */
3644 indvar = SCIPgetBinaryVarIndicator(cons);
3645 assert(indvar != NULL);
3646
3647 if( SCIPvarGetStatus(indvar) == SCIP_VARSTATUS_NEGATED )
3648 {
3649 indvar = SCIPvarGetNegationVar(indvar);
3650 assert(indvar != NULL);
3651 assert(SCIPvarGetStatus(indvar) != SCIP_VARSTATUS_AGGREGATED && SCIPvarGetStatus(indvar) != SCIP_VARSTATUS_MULTAGGR);
3652
3653 /* get the soft cost of this constraint */
3654 weight = (SCIP_Longint) SCIPvarGetObj(indvar);
3655 }
3656 else
3657 {
3658 assert(SCIPvarGetStatus(indvar) != SCIP_VARSTATUS_AGGREGATED && SCIPvarGetStatus(indvar) != SCIP_VARSTATUS_MULTAGGR);
3659
3660 /* get the soft cost of this constraint */
3661 weight = -(SCIP_Longint) SCIPvarGetObj(indvar);
3662 }
3663
3664 /* get artificial slack variable */
3665 slackvar = SCIPgetSlackVarIndicator(cons);
3666 assert(slackvar != NULL);
3667
3668 /* only need to print indicator constraints with weights on their indicator variable */
3669 if( weight != 0 )
3670 {
3671 SCIP_VAR** scipvarslinear;
3672 SCIP_Real* scipvalslinear;
3673 SCIP_Bool cont;
3674 int nonbinarypos;
3675
3676 lincons = SCIPgetLinearConsIndicator(cons);
3677 assert(lincons != NULL);
3678
3679 nconsvars = SCIPgetNVarsLinear(scip, lincons);
3680 scipvarslinear = SCIPgetVarsLinear(scip, lincons);
3681 scipvalslinear = SCIPgetValsLinear(scip, lincons);
3682
3683 /* allocate temporary memory */
3684 SCIP_CALL( SCIPduplicateBufferArray(scip, &consvars, scipvarslinear, nconsvars) );
3685 SCIP_CALL( SCIPduplicateBufferArray(scip, &consvals, scipvalslinear, nconsvars) );
3686
3687 nonbinarypos = -1;
3688 cont = FALSE;
3689
3690 /* find non-binary variable */
3691 for( v = 0; v < nconsvars; ++v )
3692 {
3693 if( SCIPvarGetType(consvars[v]) != SCIP_VARTYPE_BINARY )
3694 {
3695 if( consvars[v] == slackvar )
3696 {
3697 assert(nonbinarypos == -1);
3698 nonbinarypos = v;
3699 }
3700 else
3701 {
3702 SCIPwarningMessage(scip, "cannot print linear constraint <%s> of indicator constraint <%s> because it has more than one non-binary variable\n", SCIPconsGetName(lincons), SCIPconsGetName(cons) );
3703 SCIPinfoMessage(scip, file, "* ");
3704 SCIP_CALL( SCIPprintCons(scip, cons, file) );
3705 SCIPinfoMessage(scip, file, ";\n");
3706 cont = TRUE;
3707 break;
3708 }
3709 }
3710 }
3711
3712 /* if we have not found any non-binary variable we do not print the constraint, maybe we should ??? */
3713 if( nonbinarypos == -1 )
3714 {
3715 SCIPwarningMessage(scip, "cannot print linear constraint <%s> of indicator constraint <%s> because it has no slack variable\n", SCIPconsGetName(lincons), SCIPconsGetName(cons) );
3716 SCIPinfoMessage(scip, file, "* ");
3717 SCIP_CALL( SCIPprintCons(scip, cons, file) );
3718 SCIPinfoMessage(scip, file, ";\n");
3719
3720 /* free temporary memory */
3721 SCIPfreeBufferArray(scip, &consvals);
3722 SCIPfreeBufferArray(scip, &consvars);
3723 continue;
3724 }
3725
3726 /* if the constraint has more than two non-binary variables is not printable and we go to the next */
3727 if( cont )
3728 {
3729 /* free temporary memory */
3730 SCIPfreeBufferArray(scip, &consvals);
3731 SCIPfreeBufferArray(scip, &consvars);
3732 continue;
3733 }
3734
3735 assert(0 <= nonbinarypos && nonbinarypos < nconsvars);
3736
3737 /* remove slackvariable in linear constraint for printing */
3738 --nconsvars;
3739 consvars[nonbinarypos] = consvars[nconsvars];
3740 consvals[nonbinarypos] = consvals[nconsvars];
3741
3742 if( existands )
3743 {
3744 retcode = printNonLinearCons(scip, file,
3745 consvars, consvals, nconsvars, SCIPgetLhsLinear(scip, lincons), SCIPgetRhsLinear(scip, lincons),
3746 resvars, nresvars, andvars, nandvars,
3747 weight, transformed, multisymbol);
3748 }
3749 else
3750 {
3751 retcode = printLinearCons(scip, file,
3752 consvars, consvals, nconsvars, SCIPgetLhsLinear(scip, lincons), SCIPgetRhsLinear(scip, lincons),
3753 weight, transformed, multisymbol);
3754 }
3755
3756 /* free temporary memory */
3757 SCIPfreeBufferArray(scip, &consvals);
3758 SCIPfreeBufferArray(scip, &consvars);
3759 }
3760 else
3761 {
3762 SCIPwarningMessage(scip, "indicator constraint <%s> will not be printed because the indicator variable has no objective value(= weight of this soft constraint)\n", SCIPconsGetName(cons) );
3763 SCIPinfoMessage(scip, file, "* ");
3764 SCIP_CALL( SCIPprintCons(scip, cons, file) );
3765 SCIPinfoMessage(scip, file, ";\n");
3766 }
3767 }
3768 else if( strcmp(conshdlrname, "and") == 0 )
3769 {
3770 /* all resultants of the and constraint will be replaced by all corresponding variables of this constraint,
3771 * so no and-constraint will be printed directly */
3772 assert(existandconshdlr);
3773 }
3774 else
3775 {
3776 SCIPwarningMessage(scip, "constraint handler <%s> cannot print requested format\n", conshdlrname );
3777 SCIPinfoMessage(scip, file, "* ");
3778 SCIP_CALL( SCIPprintCons(scip, cons, file) );
3779 SCIPinfoMessage(scip, file, ";\n");
3780 }
3781 }
3782 }
3783
3784 if( retcode == SCIP_INVALIDDATA )
3785 {
3786 assert(cons != NULL);
3787
3788 SCIPerrorMessage("Cannot print constraint %s with non-integral coefficient or sides in opb-format\n",
3789 SCIPconsGetName(cons));
3790 SCIP_CALL( SCIPprintCons(scip, cons, stderr) );
3791 SCIPinfoMessage(scip, file, ";\n");
3792 }
3793
3794 if( linconssofpbsmap != NULL )
3795 {
3796 /* free hash map */
3797 SCIPhashmapFree(&linconssofpbsmap);
3798 }
3799 if( linconssofindicatorsmap != NULL )
3800 {
3801 /* free hash map */
3802 SCIPhashmapFree(&linconssofindicatorsmap);
3803 }
3804
3805 return retcode;
3806 }
3807
3808 /* write fixed variables (unless already done because they are an and resultant or and variable) */
3809 static
3810 SCIP_RETCODE writeOpbFixedVars(
3811 SCIP*const scip, /**< SCIP data structure */
3812 FILE*const file, /**< output file, or NULL if standard output should be used */
3813 SCIP_VAR** vars, /**< array with active (binary) variables */
3814 int nvars, /**< number of active variables in the problem */
3815 SCIP_HASHTABLE*const printedfixing, /**< hashmap to store if a fixed variable was already printed */
3816 char const*const multisymbol, /**< the multiplication symbol to use between coefficient and variable */
3817 SCIP_Bool const transformed /**< TRUE iff problem is the transformed problem */
3818 )
3819 {
3820 char linebuffer[OPB_MAX_LINELEN+1];
3821 char buffer[OPB_MAX_LINELEN];
3822 int linecnt;
3823 int v;
3824
3825 assert(scip != NULL);
3826 assert(file != NULL);
3827 assert(vars != NULL || nvars == 0);
3828 assert(printedfixing != NULL);
3829 assert(multisymbol != NULL);
3830
3831 clearBuffer(linebuffer, &linecnt);
3832
3833 /* print variables which are fixed */
3834 for( v = 0; v < nvars; ++v )
3835 {
3836 SCIP_VAR* var;
3837 SCIP_Real lb;
3838 SCIP_Real ub;
3839 SCIP_Bool neg = FALSE;
3840
3841 assert( vars != NULL );
3842 var = vars[v];
3843
3844 if( transformed )
3845 {
3846 /* in case the transformed is written only local bounds are posted which are valid in the current node */
3847 lb = SCIPvarGetLbLocal(var);
3848 ub = SCIPvarGetUbLocal(var);
3849 }
3850 else
3851 {
3852 lb = SCIPvarGetLbOriginal(var);
3853 ub = SCIPvarGetUbOriginal(var);
3854 }
3855 assert(lb > -0.5 && ub < 1.5);
3856 assert(SCIPisFeasIntegral(scip, lb));
3857 assert(SCIPisFeasIntegral(scip, ub));
3858
3859 /* print fixed and-resultants */
3860 if( lb > 0.5 || ub < 0.5 )
3861 {
3862 if( transformed ) {
3863 SCIP_CALL( SCIPgetBinvarRepresentative(scip, var, &var, &neg) );
3864 }
3865
3866 if( SCIPhashtableExists(printedfixing, (void*)var) )
3867 continue;
3868
3869 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "+1%s%s%s = %g ;\n", multisymbol, neg ? "~" : "", strstr(SCIPvarGetName(neg ? SCIPvarGetNegationVar(var) : var), "x"), lb);
3870 appendBuffer(scip, file, linebuffer, &linecnt, buffer);
3871
3872 /* add variable to the hashmap */
3873 SCIP_CALL( SCIPhashtableInsert(printedfixing, (void*)var) );
3874 }
3875 }
3876
3877 writeBuffer(scip, file, linebuffer, &linecnt);
3878
3879 return SCIP_OKAY;
3880 }
3881
3882 /* write and constraints of inactive but relevant and-resultants and and variables which are fixed to one */
3883 static
3884 SCIP_RETCODE writeOpbRelevantAnds(
3885 SCIP*const scip, /**< SCIP data structure */
3886 FILE*const file, /**< output file, or NULL if standard output should be used */
3887 SCIP_VAR**const resvars, /**< array of resultant variables */
3888 int const nresvars, /**< number of resultant variables */
3889 SCIP_VAR**const*const andvars, /**< corresponding array of and-variables */
3890 int const*const nandvars, /**< array of numbers of corresponding and-variables */
3891 SCIP_HASHTABLE*const printedfixing, /**< hashmap to store if a fixed variable was already printed */
3892 char const*const multisymbol, /**< the multiplication symbol to use between coefficient and variable */
3893 SCIP_Bool const transformed /**< TRUE iff problem is the transformed problem */
3894 )
3895 {
3896 SCIP_VAR* resvar;
3897 SCIP_Longint rhslhs;
3898 char linebuffer[OPB_MAX_LINELEN+1];
3899 char buffer[OPB_MAX_LINELEN];
3900 int linecnt;
3901 int r, v;
3902
3903 assert(scip != NULL);
3904 assert(file != NULL);
3905 assert(resvars != NULL || nresvars == 0);
3906 assert(nandvars != NULL || nresvars == 0);
3907 assert(andvars != NULL || nandvars == NULL);
3908 assert(multisymbol != NULL);
3909
3910 clearBuffer(linebuffer, &linecnt);
3911
3912 /* print and-variables which are fixed */
3913 /* @todo remove this block here and the hashtable and let writeOpbFixedVars() do the job? */
3914 for( r = nresvars - 1; r >= 0; --r )
3915 {
3916 SCIP_VAR* var;
3917 SCIP_Bool neg;
3918 SCIP_Real lb;
3919 SCIP_Real ub;
3920
3921 assert( resvars != NULL );
3922 resvar = resvars[r];
3923
3924 if( transformed )
3925 {
3926 /* in case the transformed is written only local bounds are posted which are valid in the current node */
3927 lb = SCIPvarGetLbLocal(resvar);
3928 ub = SCIPvarGetUbLocal(resvar);
3929 }
3930 else
3931 {
3932 lb = SCIPvarGetLbOriginal(resvar);
3933 ub = SCIPvarGetUbOriginal(resvar);
3934 }
3935
3936 /* print fixed and-resultants */
3937 if( lb > 0.5 || ub < 0.5 )
3938 {
3939 /* coverity[copy_paste_error] */
3940 SCIP_CALL( SCIPgetBinvarRepresentative(scip, resvar, &var, &neg) );
3941
3942 assert(SCIPisFeasIntegral(scip, lb));
3943 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "+1%s%s%s = %g ;\n", multisymbol, neg ? "~" : "", strstr(SCIPvarGetName(neg ? SCIPvarGetNegationVar(var) : var), "x"), lb);
3944 appendBuffer(scip, file, linebuffer, &linecnt, buffer);
3945
3946 /* add variable to the hashmap */
3947 SCIP_CALL( SCIPhashtableInsert(printedfixing, (void*)var) );
3948 }
3949
3950 assert( andvars != NULL && nandvars != NULL );
3951 assert( andvars[r] != NULL || nandvars[r] == 0 );
3952
3953 /* print fixed and-variables */
3954 for( v = nandvars[r] - 1; v >= 0; --v ) /*lint !e613 */
3955 {
3956 assert( andvars[r] != NULL );
3957 assert( andvars[r][v] != NULL );
3958
3959 if( transformed )
3960 {
3961 /* in case the transformed is written only local bounds are posted which are valid in the current node */
3962 lb = SCIPvarGetLbLocal(andvars[r][v]);
3963 ub = SCIPvarGetUbLocal(andvars[r][v]);
3964 }
3965 else
3966 {
3967 lb = SCIPvarGetLbOriginal(andvars[r][v]);
3968 ub = SCIPvarGetUbOriginal(andvars[r][v]);
3969 }
3970
3971 if( lb > 0.5 || ub < 0.5 )
3972 {
3973 SCIP_CALL( SCIPgetBinvarRepresentative(scip, andvars[r][v], &var, &neg) ); /*lint !e613 */
3974
3975 assert(SCIPisFeasIntegral(scip, lb));
3976 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "+1%s%s%s = %g ;\n", multisymbol, neg ? "~" : "", strstr(SCIPvarGetName(neg ? SCIPvarGetNegationVar(var) : var), "x"), lb);
3977 appendBuffer(scip, file, linebuffer, &linecnt, buffer);
3978
3979 /* add variable to the hashmap */
3980 SCIP_CALL( SCIPhashtableInsert(printedfixing, (void*)var) );
3981 }
3982 }
3983 }
3984
3985 /* print and-constraints with fixed and-resultant to zero and all and-constraints with
3986 * aggregated resultant, otherwise we would loose this information
3987 */
3988 for( r = nresvars - 1; r >= 0; --r )
3989 {
3990 assert( resvars != NULL );
3991 resvar = resvars[r];
3992 rhslhs = (SCIPvarGetUbLocal(resvar) < 0.5) ? 0 : ((SCIPvarGetLbLocal(resvar) > 0.5) ? 1 : -1);
3993
3994 /* if and resultant is fixed to 0 and at least one and-variable is fixed to zero, we don't print this redundant constraint */
3995 if( rhslhs == 0 )
3996 {
3997 SCIP_Bool cont;
3998
3999 cont = FALSE;
4000
4001 assert( andvars != NULL && nandvars != NULL );
4002 assert( andvars[r] != NULL || nandvars[r] == 0 );
4003
4004 /* if resultant variable and one other and variable is already zero, so we did not need to print this and
4005 * constraint because all other variables are free
4006 */
4007 for( v = nandvars[r] - 1; v >= 0; --v ) /*lint !e613 */
4008 {
4009 assert( andvars[r] != NULL );
4010 assert( andvars[r][v] != NULL );
4011
4012 if( SCIPvarGetUbLocal(andvars[r][v]) < 0.5 ) /*lint !e613 */
4013 {
4014 cont = TRUE;
4015 break;
4016 }
4017 }
4018
4019 if( cont )
4020 continue;
4021 }
4022 /* if and resultant is fixed to 1 and all and-variable are fixed to 1 too, we don't print this redundant constraint */
4023 else if( rhslhs == 1 )
4024 {
4025 SCIP_Bool cont;
4026
4027 cont = TRUE;
4028
4029 assert( andvars != NULL && nandvars != NULL );
4030 assert( andvars[r] != NULL || nandvars[r] == 0 );
4031
4032 /* if all variables are already fixed to one, we do not need to print this and constraint */
4033 for( v = nandvars[r] - 1; v >= 0; --v )
4034 {
4035 assert( andvars[r] != NULL );
4036 assert( andvars[r][v] != NULL );
4037
4038 if( SCIPvarGetLbLocal(andvars[r][v]) < 0.5 ) /*lint !e613 */
4039 {
4040 cont = FALSE;
4041 break;
4042 }
4043 }
4044
4045 if( cont )
4046 continue;
4047 }
4048
4049 /* print and with fixed or aggregated and-resultant */
4050 /* rhslhs equals to 0 means the and constraint is relevant due to it's not clear on which values the and variables are
4051 * rhslhs equals to 1 means the and constraint is irrelevant cause all and variables have to be 1 too
4052 * rhslhs equals to -1 means the and constraint is relevant cause the variable is only aggregated */
4053 if( !SCIPvarIsActive(resvar) )
4054 {
4055 SCIP_VAR* var;
4056 SCIP_Bool neg;
4057 SCIP_Bool firstprinted;
4058
4059 firstprinted = FALSE;
4060
4061 assert( andvars != NULL && nandvars != NULL );
4062 assert( andvars[r] != NULL || nandvars[r] == 0 );
4063
4064 for( v = nandvars[r] - 1; v >= 0; --v )
4065 {
4066 assert( andvars[r] != NULL );
4067 assert( andvars[r][v] != NULL );
4068
4069 SCIP_CALL( SCIPgetBinvarRepresentative(scip, andvars[r][v], &var, &neg) ); /*lint !e613 */
4070
4071 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "%s%s%s", (firstprinted) ? multisymbol : "", neg ? "~" : "", strstr(SCIPvarGetName(neg ? SCIPvarGetNegationVar(var) : var), "x"));
4072 appendBuffer(scip, file, linebuffer, &linecnt, buffer);
4073
4074 firstprinted = TRUE;
4075 }
4076
4077 /* if the resultant is aggregated we need to print his binary representation */
4078 if( rhslhs == -1 )
4079 {
4080 int pos;
4081
4082 assert(transformed);
4083
4084 SCIP_CALL( SCIPgetBinvarRepresentative(scip, resvar, &resvar, &neg) );
4085
4086 #ifndef NDEBUG
4087 if( neg )
4088 assert(SCIPvarIsActive(SCIPvarGetNegationVar(resvar)));
4089 else
4090 assert(SCIPvarIsActive(resvar));
4091 #endif
4092
4093 /* replace and-resultant with corresponding variables */
4094 if( SCIPsortedvecFindPtr((void**)resvars, SCIPvarComp, neg ? SCIPvarGetNegationVar(resvar) : resvar, nresvars, &pos) )
4095 {
4096 SCIP_Bool negated;
4097 int a;
4098
4099 assert(andvars != NULL);
4100 assert(nandvars != NULL);
4101 assert(pos >= 0 && nandvars[pos] > 0 && andvars[pos] != NULL);
4102 assert(andvars[pos][nandvars[pos] - 1] != NULL);
4103
4104 negated = SCIPvarIsNegated(andvars[pos][nandvars[pos] - 1]);
4105
4106 /* print and-vars */
4107 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, neg ? " +1%s%s%s" : " -1%s%s%s", multisymbol, negated ? "~" : "",
4108 strstr(SCIPvarGetName(negated ? SCIPvarGetNegationVar(andvars[pos][nandvars[pos] - 1]) : andvars[pos][nandvars[pos] - 1]), "x"));
4109 appendBuffer(scip, file, linebuffer, &linecnt, buffer);
4110
4111 for(a = nandvars[pos] - 2; a >= 0; --a )
4112 {
4113 negated = SCIPvarIsNegated(andvars[pos][a]);
4114
4115 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "%s%s%s", multisymbol, negated ? "~" : "", strstr(SCIPvarGetName(negated ? SCIPvarGetNegationVar(andvars[pos][a]) : andvars[pos][a]), "x"));
4116 appendBuffer(scip, file, linebuffer, &linecnt, buffer);
4117 }
4118
4119 appendBuffer(scip, file, linebuffer, &linecnt, " ");
4120
4121 if( neg )
4122 rhslhs = 1;
4123 else
4124 rhslhs = 0;
4125 }
4126 else
4127 {
4128 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, " -1%s%s%s", multisymbol, neg ? "~" : "",
4129 strstr(SCIPvarGetName(neg ? SCIPvarGetNegationVar(resvar) : resvar), "x"));
4130 appendBuffer(scip, file, linebuffer, &linecnt, buffer);
4131
4132 rhslhs = 0;
4133 }
4134 }
4135
4136 /* print rhslhs */
4137 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, " = %" SCIP_LONGINT_FORMAT " ;\n", rhslhs);
4138 appendBuffer(scip, file, linebuffer, &linecnt, buffer);
4139
4140 writeBuffer(scip, file, linebuffer, &linecnt);
4141 }
4142 }
4143
4144 return SCIP_OKAY;
4145 }
4146
4147 /* writes problem to file */
4148 static
4149 SCIP_RETCODE writeOpb(
4150 SCIP* scip, /**< SCIP data structure */
4151 FILE* file, /**< output file, or NULL if standard output should be used */
4152 const char* name, /**< problem name */
4153 SCIP_Bool transformed, /**< TRUE iff problem is the transformed problem */
4154 SCIP_OBJSENSE objsense, /**< objective sense */
4155 SCIP_Real objscale, /**< scalar applied to objective function; external objective value is
4156 * extobj = objsense * objscale * (intobj + objoffset) */
4157 SCIP_Real objoffset, /**< objective offset from bound shifting and fixing */
4158 SCIP_VAR** vars, /**< array with active (binary) variables */
4159 int nvars, /**< number of active variables in the problem */
4160 SCIP_CONS** conss, /**< array with constraints of the problem */
4161 int nconss, /**< number of constraints in the problem */
4162 SCIP_VAR** const resvars, /**< array of resultant variables */
4163 int const nresvars, /**< number of resultant variables */
4164 SCIP_VAR**const*const andvars, /**< corresponding array of and-variables */
4165 int const*const nandvars, /**< array of numbers of corresponding and-variables */
4166 SCIP_Bool const existandconshdlr, /**< does and-constrainthandler exist? */
4167 SCIP_Bool const existands, /**< does some and-constraints exist? */
4168 SCIP_RESULT* result /**< pointer to store the result of the file writing call */
4169 )
4170 {
4171 char multisymbol[OPB_MAX_LINELEN];
4172 SCIP_HASHTABLE* printedfixing;
4173 SCIP_Bool usesymbol;
4174 SCIP_RETCODE retcode;
4175 int nlinearconss;
4176 int nsplitlinearconss;
4177
4178 assert( scip != NULL );
4179 assert( vars != NULL || nvars == 0 );
4180 assert( conss != NULL || nconss == 0 );
4181 assert( result != NULL );
4182
4183 /* check if should use a multipliers symbol star '*' between coefficients and variables */
4184 SCIP_CALL( SCIPgetBoolParam(scip, "reading/" READER_NAME "/multisymbol", &usesymbol) );
4185 (void) SCIPsnprintf(multisymbol, OPB_MAX_LINELEN, "%s", usesymbol ? " * " : " ");
4186
4187 /* determine how many linear constraints are split */
4188 determineTotalNumberLinearConss(scip, conss, nconss, &nlinearconss, &nsplitlinearconss);
4189
4190 /* print statistics as comment to file */
4191 SCIPinfoMessage(scip, file, "* SCIP STATISTICS\n");
4192 SCIPinfoMessage(scip, file, "* Problem name : %s\n", name);
4193 SCIPinfoMessage(scip, file, "* Variables : %d (all binary)\n", nvars);
4194 SCIPinfoMessage(scip, file, "* Constraints : %d\n", nconss - nlinearconss + nsplitlinearconss);
4195
4196 /* create a hash table */
4197 SCIP_CALL( SCIPhashtableCreate(&printedfixing, SCIPblkmem(scip), nvars,
4198 SCIPvarGetHashkey, SCIPvarIsHashkeyEq, SCIPvarGetHashkeyVal, NULL) );
4199
4200 /* write objective function */
4201 SCIP_CALL( writeOpbObjective(scip, file, vars, nvars, resvars, nresvars, andvars, nandvars,
4202 objsense, objscale, objoffset, multisymbol, existands, transformed) );
4203
4204 /* write constraints */
4205 retcode = writeOpbConstraints(scip, file, conss, nconss, vars, nvars, resvars, nresvars, andvars, nandvars,
4206 multisymbol, existandconshdlr, existands, transformed);
4207
4208 if( existands && (retcode == SCIP_OKAY) )
4209 {
4210 /* write and constraints of inactive but relevant and-resultants and and-variables which are fixed to one
4211 with no fixed and resultant */
4212 SCIP_CALL( writeOpbRelevantAnds(scip, file, resvars, nresvars, andvars, nandvars, printedfixing, multisymbol, transformed) );
4213 }
4214
4215 /* write fixed variables */
4216 SCIP_CALL( writeOpbFixedVars(scip, file, vars, nvars, printedfixing, multisymbol, transformed) );
4217
4218 SCIPhashtableFree(&printedfixing);
4219
4220 *result = SCIP_SUCCESS;
4221
4222 return retcode;
4223 }
4224
4225
4226 /*
4227 * extern methods
4228 */
4229
4230 /** reads problem from file */
4231 SCIP_RETCODE SCIPreadOpb(
4232 SCIP* scip, /**< SCIP data structure */
4233 SCIP_READER* reader, /**< the file reader itself */
4234 const char* filename, /**< full path and name of file to read, or NULL if stdin should be used */
4235 SCIP_RESULT* result /**< pointer to store the result of the file reading call */
4236 )
4237 { /*lint --e{715}*/
4238 OPBINPUT opbinput;
4239 SCIP_RETCODE retcode;
4240 int i;
4241
4242 assert(scip != NULL); /* for lint */
4243 assert(reader != NULL);
4244
4245 /* initialize OPB input data */
4246 opbinput.file = NULL;
4247 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &opbinput.linebuf, OPB_MAX_LINELEN) );
4248 opbinput.linebuf[0] = '\0';
4249 opbinput.linebufsize = OPB_MAX_LINELEN;
4250 SCIP_CALL( SCIPallocBufferArray(scip, &opbinput.token, OPB_MAX_LINELEN) );
4251 opbinput.token[0] = '\0';
4252 SCIP_CALL( SCIPallocBufferArray(scip, &opbinput.tokenbuf, OPB_MAX_LINELEN) );
4253 opbinput.tokenbuf[0] = '\0';
4254 for( i = 0; i < OPB_MAX_PUSHEDTOKENS; ++i )
4255 {
4256 SCIP_CALL( SCIPallocBufferArray(scip, &(opbinput.pushedtokens[i]), OPB_MAX_LINELEN) ); /*lint !e866 */
4257 }
4258
4259 opbinput.npushedtokens = 0;
4260 opbinput.linenumber = 1;
4261 opbinput.linepos = 0;
4262 opbinput.objsense = SCIP_OBJSENSE_MINIMIZE;
4263 opbinput.eof = FALSE;
4264 opbinput.haserror = FALSE;
4265 opbinput.nproblemcoeffs = 0;
4266 opbinput.wbo = FALSE;
4267 opbinput.topcost = -SCIPinfinity(scip);
4268 opbinput.nindvars = 0;
4269 #if GENCONSNAMES == TRUE
4270 opbinput.consnumber = 0;
4271 #endif
4272
4273 /* read the file */
4274 retcode = readOPBFile(scip, &opbinput, filename);
4275
4276 /* free dynamically allocated memory */
4277 for( i = OPB_MAX_PUSHEDTOKENS - 1; i >= 0; --i )
4278 {
4279 SCIPfreeBufferArrayNull(scip, &(opbinput.pushedtokens[i]));
4280 }
4281 SCIPfreeBufferArrayNull(scip, &opbinput.tokenbuf);
4282 SCIPfreeBufferArrayNull(scip, &opbinput.token);
4283 SCIPfreeBlockMemoryArray(scip, &opbinput.linebuf, opbinput.linebufsize);
4284
4285 if( retcode == SCIP_PLUGINNOTFOUND )
4286 retcode = SCIP_READERROR;
4287
4288 SCIP_CALL( retcode );
4289
4290 if( opbinput.nproblemcoeffs > 0 )
4291 {
4292 SCIPwarningMessage(scip, "there might be <%d> coefficients or weight out of range!\n", opbinput.nproblemcoeffs);
4293 }
4294
4295 /* evaluate the result */
4296 if( opbinput.haserror )
4297 return SCIP_READERROR;
4298 else
4299 {
4300 /* set objective sense */
4301 SCIP_CALL( SCIPsetObjsense(scip, opbinput.objsense) );
4302 *result = SCIP_SUCCESS;
4303 }
4304
4305 return SCIP_OKAY;
4306 }
4307
4308 /** writes problem to file */
4309 SCIP_RETCODE SCIPwriteOpb(
4310 SCIP* scip, /**< SCIP data structure */
4311 FILE* file, /**< output file, or NULL if standard output should be used */
4312 const char* name, /**< problem name */
4313 SCIP_Bool transformed, /**< TRUE iff problem is the transformed problem */
4314 SCIP_OBJSENSE objsense, /**< objective sense */
4315 SCIP_Real objscale, /**< scalar applied to objective function; external objective value is
4316 * extobj = objsense * objscale * (intobj + objoffset) */
4317 SCIP_Real objoffset, /**< objective offset from bound shifting and fixing */
4318 SCIP_VAR** vars, /**< array with active variables ordered binary, integer, implicit, continuous */
4319 int nvars, /**< number of active variables in the problem */
4320 int nbinvars, /**< number of binary variables */
4321 int nintvars, /**< number of general integer variables */
4322 int nimplvars, /**< number of implicit integer variables */
4323 int ncontvars, /**< number of continuous variables */
4324 SCIP_VAR** fixedvars, /**< array with fixed variables */
4325 int nfixedvars, /**< number of fixed and aggregated variables in the problem */
4326 SCIP_CONS** conss, /**< array with constraints of the problem */
4327 int nconss, /**< number of constraints in the problem */
4328 SCIP_Bool genericnames, /**< should generic variable and constraint names be used */
4329 SCIP_RESULT* result /**< pointer to store the result of the file writing call */
4330 )
4331 { /*lint --e{715}*/
4332 SCIP_RETCODE retcode = SCIP_OKAY;
4333
4334 if( nvars != nbinvars && (nintvars > 0 || SCIPfindConshdlr(scip, "indicator") != NULL
4335 || ncontvars + nimplvars != SCIPconshdlrGetNConss(SCIPfindConshdlr(scip, "indicator"))) )
4336 {
4337 SCIPwarningMessage(scip, "only binary problems can be written in OPB format.\n");
4338 *result = SCIP_DIDNOTRUN;
4339 }
4340 else
4341 {
4342 SCIP_VAR*** andvars;
4343 SCIP_VAR** resvars;
4344 int* nandvars;
4345 SCIP_Bool existands;
4346 SCIP_Bool existandconshdlr;
4347 int nresvars;
4348 int v;
4349
4350 /* computes all and-resultants and their corresponding constraint variables */
4351 /* coverity[leaked_storage] */
4352 SCIP_CALL( computeAndConstraintInfos(scip, transformed, &resvars, &nresvars, &andvars, &nandvars, &existandconshdlr, &existands) );
4353
4354 if( genericnames )
4355 {
4356 #ifndef NDEBUG
4357 /* check for correct names for opb-format */
4358 int idx;
4359 int pos;
4360
4361 for( v = nvars - 1; v >= 0; --v )
4362 {
4363 if( existands )
4364 {
4365 /* and variables are artificial */
4366 if( SCIPsortedvecFindPtr((void**)resvars, SCIPvarComp, vars[v], nresvars, &pos) )
4367 continue;
4368 }
4369
4370 assert(sscanf(SCIPvarGetName(vars[v]), "x%d", &idx) == 1);
4371 }
4372 #endif
4373 retcode = writeOpb(scip, file, name, transformed, objsense, objscale, objoffset, vars,
4374 nvars, conss, nconss, resvars, nresvars, andvars, nandvars, existandconshdlr, existands, result);
4375 }
4376 else
4377 {
4378 SCIP_Bool printed;
4379 int idx;
4380 int pos;
4381
4382 printed = FALSE;
4383
4384 /* check if there are already generic names for all (not fixed variables)*/
4385 for( v = nvars - 1; v >= 0; --v )
4386 if( !existands || !SCIPsortedvecFindPtr((void**)resvars, SCIPvarComp, vars[v], nresvars, &pos) )
4387 {
4388 if( sscanf(SCIPvarGetName(vars[v]), transformed ? "t_x%d" : "x%d", &idx) != 1 && strstr(SCIPvarGetName(vars[v]), INDICATORVARNAME) == NULL && strstr(SCIPvarGetName(vars[v]), INDICATORSLACKVARNAME) == NULL )
4389 {
4390 SCIPwarningMessage(scip, "At least following variable name isn't allowed in opb format.\n");
4391 SCIP_CALL( SCIPprintVar(scip, vars[v], NULL) );
4392 SCIPwarningMessage(scip, "OPB format needs generic variable names!\n");
4393
4394 if( transformed )
4395 {
4396 SCIPwarningMessage(scip, "write transformed problem with generic variable names.\n");
4397 SCIP_CALL( SCIPprintTransProblem(scip, file, "opb", TRUE) );
4398 }
4399 else
4400 {
4401 SCIPwarningMessage(scip, "write original problem with generic variable names.\n");
4402 SCIP_CALL( SCIPprintOrigProblem(scip, file, "opb", TRUE) );
4403 }
4404 printed = TRUE;
4405 break;
4406 }
4407 }
4408
4409 if( !printed )
4410 {
4411 /* check if there are already generic names for all (fixed variables)*/
4412 for( v = nfixedvars - 1; v >= 0; --v )
4413 if( !existands || !SCIPsortedvecFindPtr((void**)resvars, SCIPvarComp, vars[v], nresvars, &pos) )
4414 {
4415 /* coverity[secure_coding] */
4416 if( sscanf(SCIPvarGetName(fixedvars[v]), transformed ? "t_x%d" : "x%d", &idx) != 1 && strstr(SCIPvarGetName(fixedvars[v]), INDICATORVARNAME) == NULL && strstr(SCIPvarGetName(fixedvars[v]), INDICATORSLACKVARNAME) == NULL )
4417 {
4418 SCIPwarningMessage(scip, "At least following variable name isn't allowed in opb format.\n");
4419 SCIP_CALL( SCIPprintVar(scip, fixedvars[v], NULL) );
4420 SCIPwarningMessage(scip, "OPB format needs generic variable names!\n");
4421
4422 if( transformed )
4423 {
4424 SCIPwarningMessage(scip, "write transformed problem with generic variable names.\n");
4425 SCIP_CALL( SCIPprintTransProblem(scip, file, "opb", TRUE) );
4426 }
4427 else
4428 {
4429 SCIPwarningMessage(scip, "write original problem with generic variable names.\n");
4430 SCIP_CALL( SCIPprintOrigProblem(scip, file, "opb", TRUE) );
4431 }
4432 printed = TRUE;
4433 break;
4434 }
4435 }
4436 }
4437
4438 if( !printed )
4439 {
4440 #ifndef NDEBUG
4441 for( v = nvars - 1; v >= 0; --v )
4442 {
4443 if( existands )
4444 {
4445 if( SCIPsortedvecFindPtr((void**)resvars, SCIPvarComp, vars[v], nresvars, &pos) )
4446 continue;
4447 }
4448
4449 assert(sscanf(SCIPvarGetName(vars[v]), transformed ? "t_x%d" : "x%d", &idx) == 1 || strstr(SCIPvarGetName(vars[v]), INDICATORVARNAME) != NULL || strstr(SCIPvarGetName(vars[v]), INDICATORSLACKVARNAME) != NULL );
4450 }
4451 #endif
4452 retcode = writeOpb(scip, file, name, transformed, objsense, objscale, objoffset, vars,
4453 nvars, conss, nconss, resvars, nresvars, andvars, nandvars, existandconshdlr, existands, result);
4454 }
4455 }
4456
4457 if( existands )
4458 {
4459 /* free temporary buffers */
4460 assert(resvars != NULL);
4461 assert(andvars != NULL);
4462 assert(nandvars != NULL);
4463
4464 for( v = nresvars - 1; v >= 0; --v )
4465 {
4466 assert(andvars[v] != NULL);
4467 SCIPfreeMemoryArray(scip, &andvars[v]);
4468 }
4469 SCIPfreeMemoryArray(scip, &nandvars);
4470 SCIPfreeMemoryArray(scip, &andvars);
4471 SCIPfreeMemoryArray(scip, &resvars);
4472 }
4473
4474 *result = SCIP_SUCCESS;
4475 }
4476
4477 if( retcode == SCIP_INVALIDDATA )
4478 return SCIP_WRITEERROR;
4479
4480 return retcode;
4481 }
4482
4483 /*
4484 * Callback methods of reader
4485 */
4486
4487 /** copy method for reader plugins (called when SCIP copies plugins) */
4488 static
4489 SCIP_DECL_READERCOPY(readerCopyOpb)
4490 { /*lint --e{715}*/
4491 assert(scip != NULL);
4492 assert(reader != NULL);
4493 assert(strcmp(SCIPreaderGetName(reader), READER_NAME) == 0);
4494
4495 /* call inclusion method of reader */
4496 SCIP_CALL( SCIPincludeReaderOpb(scip) );
4497
4498 return SCIP_OKAY;
4499 }
4500
4501
4502 /** problem reading method of reader */
4503 static
4504 SCIP_DECL_READERREAD(readerReadOpb)
4505 { /*lint --e{715}*/
4506
4507 SCIP_CALL( SCIPreadOpb(scip, reader, filename, result) );
4508
4509 return SCIP_OKAY;
4510 }
4511
4512
4513 /** problem writing method of reader */
4514 static
4515 SCIP_DECL_READERWRITE(readerWriteOpb)
4516 { /*lint --e{715}*/
4517
4518 SCIP_CALL( SCIPwriteOpb(scip, file, name, transformed, objsense, objscale, objoffset, vars,
4519 nvars, nbinvars, nintvars, nimplvars, ncontvars, fixedvars, nfixedvars, conss, nconss, genericnames, result) );
4520
4521 return SCIP_OKAY;
4522 }
4523
4524 /*
4525 * reader specific interface methods
4526 */
4527
4528 /** includes the opb file reader in SCIP */
4529 SCIP_RETCODE SCIPincludeReaderOpb(
4530 SCIP* scip /**< SCIP data structure */
4531 )
4532 {
4533 SCIP_READER* reader;
4534
4535 /* include reader */
4536 SCIP_CALL( SCIPincludeReaderBasic(scip, &reader, READER_NAME, READER_DESC, READER_EXTENSION, NULL) );
4537
4538 /* set non fundamental callbacks via setter functions */
4539 SCIP_CALL( SCIPsetReaderCopy(scip, reader, readerCopyOpb) );
4540 SCIP_CALL( SCIPsetReaderRead(scip, reader, readerReadOpb) );
4541 SCIP_CALL( SCIPsetReaderWrite(scip, reader, readerWriteOpb) );
4542
4543 /* add opb reader parameters */
4544 SCIP_CALL( SCIPaddBoolParam(scip,
4545 "reading/" READER_NAME "/dynamicconss", "should model constraints be subject to aging?",
4546 NULL, FALSE, FALSE/*TRUE*/, NULL, NULL) ); /* have to be FALSE, otherwise an error might inccur in restart during branch and bound */
4547 SCIP_CALL( SCIPaddBoolParam(scip,
4548 "reading/" READER_NAME "/multisymbol", "use '*' between coefficients and variables by writing to problem?",
4549 NULL, TRUE, FALSE, NULL, NULL) );
4550
4551 return SCIP_OKAY;
4552 }
4553