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