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