All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
xternal.c
Go to the documentation of this file. 31 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
45 * - incorporates a full-scale mixed integer quadratically constrained programming (MIQCP) solver.
47 * See the web site of <a href="http://scip.zib.de">SCIP</a> for more information about licensing and to download SCIP.
49 * SCIP is developed together with <a href="http://www3.mathematik.tu-darmstadt.de/ags/optimierung/research/discrete-optimization.html">TU Darmstadt</a> and
50 * <a href="http://www.am.uni-erlangen.de/wima/">University of Erlangen-Nürnberg (Chair of EDOM)</a>
126 * SCIP contains several examples that demonstrate its usage. They are contained in the "examples" directory
137 * An implementation of the column generation approach for the binpacking problem. It includes a customized reader,
154 * A solver for a simple capacity-constrained vehicle routing problem, which is based on pricing tours via a dynamic
176 * A short implementations of a constraint handler, two easy combinatorial heuristics, a file reader, etc. which
177 * demonstrate the usage of SCIP as a branch-and-cut-framework for solving traveling salesman problem instances.
190 * An example showing how to setup constraints (esp. nonlinear ones) when using SCIP as callable library.
243 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
252 * - No spaces between control structure keywords like "if", "for", "while", "switch" and the corresponding brackets.
253 * - No spaces between a function name and the parenthesis in both the definition and function calls.
255 * - All global functions start with "SCIP". In the usual naming scheme this is followed by the object and a method name
257 * - Make all functions that are not used outside the module 'static'. Naming should start with a lower case letter.
309 * If you are using (x)emacs, you can use the following customization for the c++-mode. These settings satisfy the
334 * Eclipse user can use the profile below. This profile does not match the \SCIP coding guideline completely.
341 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_opening_paren_in_method_declaration" value="do not insert"/>
342 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_opening_paren_in_for" value="insert"/>
345 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_comma_in_base_types" value="do not insert"/>
347 * <setting id="org.eclipse.cdt.core.formatter.indent_switchstatements_compare_to_switch" value="false"/>
348 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_opening_brace_in_array_initializer" value="insert"/>
349 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_comma_in_method_declaration_parameters" value="do not insert"/>
350 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_opening_paren_in_if" value="insert"/>
351 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_opening_paren_in_exception_specification" value="do not insert"/>
352 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_closing_paren_in_parenthesized_expression" value="do not insert"/>
353 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_comma_in_base_types" value="insert"/>
354 * <setting id="org.eclipse.cdt.core.formatter.indent_body_declarations_compare_to_access_specifier" value="true"/>
355 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_closing_paren_in_exception_specification" value="do not insert"/>
356 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_comma_in_template_arguments" value="insert"/>
357 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_opening_brace_in_block" value="insert"/>
358 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_closing_paren_in_method_declaration" value="do not insert"/>
359 * <setting id="org.eclipse.cdt.core.formatter.use_tabs_only_for_leading_indentations" value="false"/>
360 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_colon_in_labeled_statement" value="do not insert"/>
361 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_colon_in_case" value="insert"/>
362 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_comma_in_array_initializer" value="insert"/>
363 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_comma_in_enum_declarations" value="insert"/>
364 * <setting id="org.eclipse.cdt.core.formatter.alignment_for_expressions_in_array_initializer" value="16"/>
365 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_comma_in_declarator_list" value="insert"/>
366 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_opening_bracket" value="do not insert"/>
367 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_closing_paren_in_for" value="insert"/>
368 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_prefix_operator" value="do not insert"/>
370 * <setting id="org.eclipse.cdt.core.formatter.insert_new_line_before_else_in_if_statement" value="insert"/>
372 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_opening_paren_in_parenthesized_expression" value="do not insert"/>
373 * <setting id="org.eclipse.cdt.core.formatter.insert_space_between_empty_parens_in_method_declaration" value="do not insert"/>
375 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_closing_paren_in_switch" value="insert"/>
376 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_opening_paren_in_parenthesized_expression" value="do not insert"/>
378 * <setting id="org.eclipse.cdt.core.formatter.indent_switchstatements_compare_to_cases" value="true"/>
379 * <setting id="org.eclipse.cdt.core.formatter.keep_empty_array_initializer_on_one_line" value="false"/>
380 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_opening_brace_in_method_declaration" value="insert"/>
382 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_opening_brace_in_switch" value="do not insert"/>
383 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_closing_paren_in_cast" value="do not insert"/>
384 * <setting id="org.eclipse.cdt.core.formatter.insert_space_between_empty_braces_in_array_initializer" value="do not insert"/>
385 * <setting id="org.eclipse.cdt.core.formatter.brace_position_for_method_declaration" value="next_line"/>
386 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_closing_paren_in_while" value="insert"/>
387 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_question_in_conditional" value="insert"/>
388 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_semicolon" value="do not insert"/>
389 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_closing_angle_bracket_in_template_arguments" value="insert"/>
390 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_colon_in_base_clause" value="do not insert"/>
392 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_unary_operator" value="do not insert"/>
393 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_comma_in_declarator_list" value="do not insert"/>
394 * <setting id="org.eclipse.cdt.core.formatter.alignment_for_arguments_in_method_invocation" value="16"/>
395 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_opening_paren_in_while" value="do not insert"/>
396 * <setting id="org.eclipse.cdt.core.formatter.insert_space_between_empty_brackets" value="do not insert"/>
397 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_opening_bracket" value="do not insert"/>
398 * <setting id="org.eclipse.cdt.core.formatter.alignment_for_parameters_in_method_declaration" value="48"/>
399 * <setting id="org.eclipse.cdt.core.formatter.insert_new_line_before_closing_brace_in_array_initializer" value="do not insert"/>
401 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_opening_paren_in_method_invocation" value="do not insert"/>
402 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_closing_brace_in_array_initializer" value="insert"/>
403 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_semicolon_in_for" value="do not insert"/>
405 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_colon_in_conditional" value="insert"/>
406 * <setting id="org.eclipse.cdt.core.formatter.brace_position_for_type_declaration" value="next_line"/>
407 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_assignment_operator" value="insert"/>
408 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_opening_angle_bracket_in_template_arguments" value="do not insert"/>
409 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_comma_in_expression_list" value="do not insert"/>
410 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_opening_angle_bracket_in_template_parameters" value="do not insert"/>
413 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_opening_paren_in_method_declaration" value="do not insert"/>
414 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_comma_in_template_parameters" value="do not insert"/>
415 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_colon_in_default" value="do not insert"/>
416 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_binary_operator" value="insert"/>
417 * <setting id="org.eclipse.cdt.core.formatter.alignment_for_conditional_expression" value="16"/>
418 * <setting id="org.eclipse.cdt.core.formatter.insert_space_between_empty_parens_in_method_invocation" value="do not insert"/>
419 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_comma_in_array_initializer" value="do not insert"/>
420 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_closing_paren_in_if" value="insert"/>
421 * <setting id="org.eclipse.cdt.core.formatter.format_guardian_clause_on_one_line" value="false"/>
422 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_opening_paren_in_cast" value="do not insert"/>
423 * <setting id="org.eclipse.cdt.core.formatter.indent_access_specifier_compare_to_type_header" value="false"/>
424 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_opening_brace_in_type_declaration" value="insert"/>
425 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_colon_in_labeled_statement" value="insert"/>
426 * <setting id="org.eclipse.cdt.core.formatter.continuation_indentation_for_array_initializer" value="1"/>
427 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_comma_in_method_declaration_parameters" value="insert"/>
428 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_semicolon_in_for" value="insert"/>
429 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_closing_paren_in_method_invocation" value="do not insert"/>
430 * <setting id="org.eclipse.cdt.core.formatter.indent_body_declarations_compare_to_namespace_header" value="false"/>
431 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_closing_brace_in_block" value="insert"/>
432 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_assignment_operator" value="insert"/>
434 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_opening_brace_in_array_initializer" value="insert"/>
435 * <setting id="org.eclipse.cdt.core.formatter.insert_new_line_at_end_of_file_if_missing" value="do not insert"/>
436 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_comma_in_template_parameters" value="insert"/>
437 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_comma_in_expression_list" value="insert"/>
438 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_question_in_conditional" value="insert"/>
439 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_opening_paren_in_exception_specification" value="insert"/>
440 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_binary_operator" value="insert"/>
441 * <setting id="org.eclipse.cdt.core.formatter.insert_new_line_before_identifier_in_function_declaration" value="do not insert"/>
442 * <setting id="org.eclipse.cdt.core.formatter.alignment_for_base_clause_in_type_declaration" value="80"/>
443 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_comma_in_method_declaration_throws" value="do not insert"/>
444 * <setting id="org.eclipse.cdt.core.formatter.insert_space_between_empty_parens_in_exception_specification" value="do not insert"/>
445 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_comma_in_method_invocation_arguments" value="do not insert"/>
446 * <setting id="org.eclipse.cdt.core.formatter.indent_declaration_compare_to_template_header" value="false"/>
447 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_unary_operator" value="do not insert"/>
448 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_opening_paren_in_switch" value="do not insert"/>
450 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_comma_in_method_declaration_throws" value="insert"/>
451 * <setting id="org.eclipse.cdt.core.formatter.indent_statements_compare_to_block" value="true"/>
452 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_comma_in_template_arguments" value="do not insert"/>
453 * <setting id="org.eclipse.cdt.core.formatter.insert_new_line_before_catch_in_try_statement" value="insert"/>
454 * <setting id="org.eclipse.cdt.core.formatter.alignment_for_throws_clause_in_method_declaration" value="48"/>
455 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_opening_paren_in_method_invocation" value="do not insert"/>
456 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_closing_paren_in_cast" value="do not insert"/>
457 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_closing_paren_in_catch" value="insert"/>
458 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_opening_angle_bracket_in_template_parameters" value="do not insert"/>
460 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_closing_angle_bracket_in_template_parameters" value="do not insert"/>
461 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_opening_paren_in_while" value="insert"/>
462 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_comma_in_method_invocation_arguments" value="insert"/>
463 * <setting id="org.eclipse.cdt.core.formatter.brace_position_for_block_in_case" value="next_line"/>
465 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_postfix_operator" value="do not insert"/>
466 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_colon_in_base_clause" value="insert"/>
467 * <setting id="org.eclipse.cdt.core.formatter.insert_new_line_after_template_declaration" value="do not insert"/>
468 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_opening_paren_in_catch" value="insert"/>
471 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_opening_paren_in_if" value="do not insert"/>
472 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_opening_paren_in_switch" value="insert"/>
474 * <setting id="org.eclipse.cdt.core.formatter.insert_new_line_after_opening_brace_in_array_initializer" value="do not insert"/>
476 * <setting id="org.eclipse.cdt.core.formatter.brace_position_for_namespace_declaration" value="end_of_line"/>
477 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_colon_in_conditional" value="insert"/>
478 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_comma_in_enum_declarations" value="do not insert"/>
479 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_prefix_operator" value="do not insert"/>
480 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_closing_angle_bracket_in_template_arguments" value="do not insert"/>
481 * <setting id="org.eclipse.cdt.core.formatter.brace_position_for_array_initializer" value="end_of_line"/>
482 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_colon_in_case" value="do not insert"/>
483 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_opening_paren_in_catch" value="do not insert"/>
484 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_opening_brace_in_namespace_declaration" value="insert"/>
485 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_postfix_operator" value="do not insert"/>
486 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_closing_bracket" value="do not insert"/>
487 * <setting id="org.eclipse.cdt.core.formatter.insert_new_line_before_while_in_do_statement" value="insert"/>
488 * <setting id="org.eclipse.cdt.core.formatter.insert_space_before_opening_paren_in_for" value="do not insert"/>
489 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_closing_angle_bracket_in_template_parameters" value="insert"/>
490 * <setting id="org.eclipse.cdt.core.formatter.insert_space_after_opening_angle_bracket_in_template_arguments" value="do not insert"/>
496 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
500 * In most cases (LINUX and MAC) it is quite easy to compile and install SCIP. Therefore, reading the section
501 * \ref BRIEFINSTALL "Brief installation description" should usually be enough. If this is not the case you find
502 * \ref DETAILEDINSTALL "Detailed installation description" below as well as \ref EXAMPLE1 "Examples".
506 * The easiest way to install SCIP is to use the SCIP Optimization Suite which contains SCIP, SoPlex, and ZIMPL. For
507 * that we refer to the INSTALL file of the SCIP Optimization Suite (main advantage: there is no need
515 * -# (optional) install the header, libraries, and binary <code>make install INSTALLDIR="/usr/local/</code>
540 * In this section we describe the use, and a few features, of the SCIP Makefile. We also give two examples for how to install
541 * SCIP. The \ref EXAMPLE1 "first example" illustrates the default installation. This means, with SoPleX and ZIMPL. The
542 * \ref EXAMPLE2 "second example" shows how to get CPLEX linked to SCIP without ZIMPL. This is followed by a section which
543 * gives some hints on what to do if the \ref COMPILERPROBLEMS "compilation throws an error". We give some comments on
546 * If you experience any problems during the installation, you will find help in the \ref INSTALL "INSTALL" file.
548 * SCIP contains a makefile system, which allows the individual setting of several parameters. For
551 * - <code>OPT=<dbg|opt|opt-gccold></code> Here <code>dbg</code> turns on the debug mode of SCIP. This enables asserts
552 * and avoids macros for several function in order to ease debugging. The default is <code>opt</code>, which enables
553 * the optimized mode. The third option <code>opt-gccold</code> will work with older GCC compilers before version
556 * - <code>LPS=<clp|cpx|grb|msk|qso|spx|xprs|none></code> This determines the LP-solver, which should have been
565 * - <code>none</code>: no LP-solver (you should set the parameter <lp/solvefreq> to <-1> to avoid solving LPs)
567 * - <code>LPSOPT=<dbg|opt|opt-gccold></code> Chooses the debug or optimized version (or old GCC optimized) version of
570 * - <code>ZIMPL=<true|false></code> Turns direct support of ZIMPL in SCIP on (default) or off, respectively.
571 * - <code>ZIMPLOPT=<dbg|opt|opt-gccold></code> Chooses the debug or optimized (default) (or old GCC optimized)
573 * If the ZIMPL-support is disabled, the GMP-library is no longer needed for SCIP and therefore not linked to SCIP.
575 * - <code>READLINE=<true|false></code> Turns support via the readline library on (default) or off, respectively.
577 * - <code>IPOPT=<true|false></code> to enable or disable (default) IPOPT interface (needs IPOPT)
579 * - <code>EXPRINT=<cppad|none></code> to use CppAD as expressions interpreter (default) or no expressions interpreter
581 * - <code>GAMS=<true|false></code> to enable or disable (default) reading functionality in GAMS reader (needs GAMS)
585 * - <code>NOBLKBUFMEM=<true></code> turns off the internal SCIP block and buffer memory. This way the code can be checked by valgrind or
586 * similar tools. (The individual options <code>NOBLKMEM=<true></code> and <code>NOBUFMEM=<true></code> to turn off the SCIP block and
589 * - <code>SHARED=<true></code> generates a shared object of the SCIP libraries. (The binary uses these shared
591 * - <code>OPT=prf</code> generates a profiling version of SCIP providing a detailed statistic of the time usage of
596 * - <code>COMP=intel</code> Uses of the Intel compiler which is only available with the main optimization flags
608 * - <code>depend</code> Creates dependencies files. This is only needed if you add files to SCIP.
617 * - <code>make.<sys>.<machine>.<compiler>.<dbg|opt|prf|opt-gccold></code> These file contain system/compiler specific
621 * If your platform or compiler is not supported by SCIP you might try and copy one of the existing
628 * Typing <code>make</code> uses SoPlex as LP solver and includes support for the modeling language ZIMPL. You will be asked the
635 - Current settings: LPS=spx OSTYPE=linux ARCH=x86_64 COMP=gnu SUFFIX= ZIMPL=true ZIMPLOPT=opt IPOPT=false IPOPTOPT=opt
643 -> "libsoplex.*" is the path to the SoPlex library, e.g., "../../soplex/lib/libsoplex.linux.x86.gnu.opt.a"
644 -> "zimplinc" is a directory containing the path to the ZIMPL "src" directory, e.g., "../../zimpl/src".
645 -> "libzimpl.*" is the path to the ZIMPL library, e.g., "../../zimpl/lib/libzimpl.linux.x86.gnu.opt.a"
654 > Enter soft-link target file or directory for "lib/libsoplex.linux.x86_64.gnu.opt.a" (return if not needed):
656 -> creating softlink "lib/libsoplex.linux.x86_64.gnu.opt.a" -> "../../soplex/lib/libsoplex.linux.x86_64.gnu.opt.a"
660 * this soft-link is not necessarily needed since "lib/libsoplex.linux.x86_64.gnu.opt.a" already exists - press return to skip
661 > Enter soft-link target file or directory for "lib/libsoplex.linux.x86_64.gnu.opt.so" (return if not needed):
663 * skipped creation of softlink "lib/libsoplex.linux.x86_64.gnu.opt.so". Call "make links" if needed later.
673 > Enter soft-link target file or directory for "lib/libzimpl.linux.x86_64.gnu.opt.a" (return if not needed):
675 -> creating softlink "lib/libzimpl.linux.x86_64.gnu.opt.a" -> "../../zimpl/lib/libzimpl.linux.x86_64.gnu.opt.a"
679 * this soft-link is not necessarily needed since "lib/libzimpl.linux.x86_64.gnu.opt.a" already exists - press return to skip
680 > Enter soft-link target file or directory for "lib/libzimpl.linux.x86_64.gnu.opt.so" (return if not needed):
682 * skipped creation of softlink "lib/libzimpl.linux.x86_64.gnu.opt.so". Call "make links" if needed later.
695 * Typing <code>make LPS=cpx ZIMPL=false</code> uses CPLEX as LP solver. You will be asked the following questions on
702 - Current settings: LPS=cpx OSTYPE=linux ARCH=x86_64 COMP=gnu SUFFIX= ZIMPL=false ZIMPLOPT=opt IPOPT=false IPOPTOPT=opt
710 -> "libcplex.*" is the path to the CPLEX library, e.g., "<CPLEX-path>/lib/x86_rhel4.0_3.4/static_pic/libcplex.a"
719 > Enter soft-link target file or directory for "lib/libcplex.linux.x86_64.gnu.a" (return if not needed):
721 -> creating softlink "lib/libcplex.linux.x86_64.gnu.a" -> "../../../../adm_cple/cplex121/lib/x86-64_sles9.0_3.3/static_pic/libcplex.a"
725 > Enter soft-link target file or directory for "lib/libcplex.linux.x86_64.gnu.so" (return if not needed):
727 * skipped creation of softlink "lib/libcplex.linux.x86_64.gnu.so". Call "make links" if needed later.
740 * - If the soft-link query script does not work on your machine, read step 2 in the \ref INSTALL "INSTALL" file for
744 * <code>make: *** No rule to make target `lib/???', needed by `obj/O.linux.x86.gnu.opt/lib/scip/???.o'. Stop.</code>\n
745 * the corresponding soft-link was not created or points to a wrong location. Check the soft-link targets in the "lib/"
746 * subdirectory. Try to delete all soft-links from the "lib/" directory\n and call "make links" to generate them
747 * again. If this still fails, read step 2 for instructions on manually\n creating the soft-links.
751 * the corresponding machine dependent makefile for your architecture and compiler is missing.\n Create one of the given
752 * name in the "make/" subdirectory. You may take\n "make/make.linux.x86.gnu.opt" or any other file in the make
755 * - The readline library seems to differ slightly on different OS distributions. Some versions do
762 * - On some systems, the <code>sigaction()</code> method is not available. In this case, you have
763 * to either add <code>-DNO_SIGACTION</code> to the FLAGS in the appropriate "make/make.*" file, or
767 * - On some systems, the <code>rand_r()</code> method is not available. In this case, you have to either add
768 * <code>-DNO_RAND_R</code> to the FLAGS in the appropriate "make/make.*" file, or to compile with
771 * - On some systems, the <code>strtok_r()</code> method is not available. In this case, you have
772 * to either add <code>-DNO_STRTOK_R</code> to the FLAGS in the appropriate make/make.* file, or to
773 * compile with <code>make USRFLAGS=-DNO_STRTOK_R</code>. Make sure, the file "src/scip/misc.c" is
776 * - On some systems, the <code>strerror_r()</code> method is not available. In this case, you have
777 * to either add <code>-DNO_STRERROR_R</code> to the FLAGS in the appropriate "make/make.*" file, or
781 * - On some systems, the option [-e] is not available for the read command. You have to compile with READ=read.
784 * VERBOSE=true ...</code> in order to get the full compiler invocation. This might help to fix the
789 * To build your own windows binaries under windows we recommend using the MinGW-Compiler with MSYS
795 * - pcre (here suffices the pcre7.0-lib.zip (or equivalent) to be extracted into the mingw-folder)
797 * After calling <code>make clean</code> in the ZIMPL folder you will also need flex and bison to
798 * remake ZIMPL. We recommend NOT to use <code>"make clean"</code> inside the ZIMPL-folder if you do
801 * You can download these additional packages from <a href="http://gnuwin32.sourceforge.net/packages.html">here</a>
804 * Second you need to copy the file <code>sh.exe</code> to <code>bash.exe</code> otherwise various
806 * getopt-options, but for mingw you need to add the entry <code>\#include <getopt.h></code> into
809 * Finally, there is one package you need to compile if you want to use ZIMPL and ZIMPL-support in
812 * <code>./configure --prefix=/mingw ; make ; make install</code> should succeed without problems
821 * To run the program, enter <code>bin/scip</code> for the last compiled version. If you have more than one compiled
828 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
835 * Instructions on how to write a new plugin and include it in SCIP can be found in the corresponding
838 * SCIP can also be used for writing your own branch-and-cut or branch-and-cut-and-price code. SCIP already
839 * provides a number of existing code examples which we suggest as both reference and starting point
848 * - The <a href="http://scip.zib.de/doc/examples/VRP"><b>VRP</b></a>-example is a <b>branch-and-cut-and-price</b> (column generation)-code
851 * and the <a href="http://scip.zib.de/doc/examples/Binpacking"><b>Binpacking</b></a>-example are
863 * from the SCIP root directory for copying the content of the <code>Coloring</code>-example into a fresh
878 * Note that you need to update the dependency files before compiling your project via <code>make depend</code>.
888 * If are using SCIP as a black box solver, here you will find some tips and tricks what you can do.
890 * First of all, we need a SCIP binary and an example problem file to work with. Therefore, you can either download the
891 * SCIP standard distribution (which includes problem files) and compile it on your own or you can download a
892 * precompiled binary and an example problem separately. SCIP can read files in LP, MPS, ZPL, WBO, FZN, PIP, OSiL, and other formats (see \ref FILEREADERS).
894 * If you want to download the source code of the SCIP standard distribution, we recommend to go to the <a
895 * href="http://scip.zib.de/#download">SCIP download section</a>, download the latest release (version 3.0 as
896 * of this writing), inflate the tarball (e.g., with "tar xzf scipoptsuite-[version].tgz"), and follow the instructions
897 * in the INSTALL file. The instance stein27, which will serve as an example in this tutorial, can be found under
900 * If you want to download a precompiled binary, go to the <a href="http://scip.zib.de/#download">SCIP download
901 * section</a> and download an appropriate binary for your operating system. To follow this tutorial, we recommend downloading the instance
905 * Now start your binary, without any arguments. This opens the interactive shell, which should look somehow like this:
908 * SCIP version 2.0.1 [precision: 8 byte] [memory: block] [mode: optimized] [LP solver: SoPlex 1.5.0]
913 * ZIMPL 3.1.0 Zuse Institute Mathematical Programming Language developed by T. Koch (zimpl.zib.de)
920 * First of all "help" shows you a list of all available shell commands. Brackets indicate a submenu with further options.
930 * Okay, let's solve some MIPs... use "read <path/to/file>" to parse a problem file, "optimize" to solve it and "display
940 * (round 1) 0 del vars, 0 del conss, 0 chg bounds, 0 chg sides, 0 chg coeffs, 118 upgd conss, 0 impls, 0 clqs
942 * 0 deleted vars, 0 deleted constraints, 0 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients
950 * time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
951 * t 0.0s| 1 | 0 | 34 | - | 337k| 0 | 21 | 27 | 118 | 27 | 118 | 0 | 0 | 0 | 1.300000e+01 | 2.700000e+01 | 107.69%
952 * R 0.0s| 1 | 0 | 34 | - | 338k| 0 | 21 | 27 | 118 | 27 | 118 | 0 | 0 | 0 | 1.300000e+01 | 2.600000e+01 | 100.00%
953 * s 0.0s| 1 | 0 | 34 | - | 339k| 0 | 21 | 27 | 118 | 27 | 118 | 0 | 0 | 0 | 1.300000e+01 | 2.500000e+01 | 92.31%
954 * 0.0s| 1 | 0 | 44 | - | 392k| 0 | 21 | 27 | 118 | 27 | 120 | 2 | 0 | 0 | 1.300000e+01 | 2.500000e+01 | 92.31%
955 * b 0.0s| 1 | 0 | 44 | - | 393k| 0 | 21 | 27 | 118 | 27 | 120 | 2 | 0 | 0 | 1.300000e+01 | 1.900000e+01 | 46.15%
957 * 0.1s| 1 | 2 | 107 | - | 920k| 0 | 24 | 27 | 118 | 27 | 131 | 13 | 0 | 24 | 1.300000e+01 | 1.900000e+01 | 46.15%
958 * R 0.1s| 14 | 10 | 203 | 7.4 | 935k| 13 | - | 27 | 118 | 27 | 124 | 13 | 0 | 164 | 1.300000e+01 | 1.800000e+01 | 38.46%
959 * 0.1s| 100 | 54 | 688 | 5.9 | 994k| 13 | 20 | 27 | 118 | 27 | 124 | 13 | 0 | 206 | 1.300000e+01 | 1.800000e+01 | 38.46%
960 * 0.1s| 200 | 86 | 1195 | 5.5 |1012k| 13 | - | 27 | 119 | 27 | 124 | 13 | 1 | 207 | 1.300000e+01 | 1.800000e+01 | 38.46%
961 * time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
962 * 0.2s| 300 | 106 | 1686 | 5.3 |1024k| 13 | - | 27 | 119 | 27 | 124 | 13 | 1 | 207 | 1.350000e+01 | 1.800000e+01 | 33.33%
964 * 0.7s| 4100 | 50 | 18328 | 4.4 |1033k| 16 | 8 | 27 | 119 | 27 | 124 | 13 | 15 | 207 | 1.650000e+01 | 1.800000e+01 | 9.09%
984 * What do we see here? After "optimize", SCIP first goes into presolving. Not much is happening for this instance, just
985 * the linear constraints get upgraded to more specific types. Each round of presolving will be displayed in a single
986 * line, with a short summary at the end. Here, there has only been one round with actual changes, the second round did
987 * not bring any further reductions. Thus, it is not displayed and presolving is stopped. Then, we see the actual
988 * solving process. The first three output lines indicate that new incumbent solutions were found by the primal
989 * heuristics with display characters "t", "R", and "s"; see, how the "primalbound" column goes down from 27 to 25. In
990 * the fourth line, two "cuts" are added. Up to here, we needed 44 "LP iter"ations (34 for the first LP and 10 more to
991 * resolve after adding cuts). Little later, the root node processing is finished. We see that there are now two open
992 * nodes in the "left" column. From now on, we will see an output line every hundredth node or whenever a new incumbent
993 * is found (e.g. at node 14 in the above output). After some more nodes, the "dualbound" starts moving, too. At one
994 * point, both will be the same, and the solving process terminates, showing us some wrap-up information.
996 * The exact performance varies amongst different architectures, operating systems, and so on. Do not be worried if
997 * your installation needs more or less time or nodes to solve. Also, this instance has more than 2000 different optimal
998 * solutions. The optimal objective value always has to be 18, but the solution vector may differ. If you are interested
999 * in this behavior, which is called "performance variability", you may have a look at the MIPLIB2010 paper.
1001 * We might want to have some more information now. Which were the heuristics that found the solutions? What plugins
1002 * were called during the solutions process and how much time did they spend? How did the instance that we were solving
1003 * look? Information on certain plugin types (e.g., heuristics, branching rules, separators) we get by
1004 * "display <plugin-type>", information on the solution process, we get by "display statistics", and "display problem"
1014 * shifting s -5000 10 0 LP rounding heuristic with infeasibility recovering also using continuous variables
1030 * We see that rounding and shifting were the heuristics producing the solutions in the beginning. Rounding is called at
1031 * every node, shifting only at every tenth level of the tree. The statistics are quite comprehensive, thus, we just
1032 * explain a few lines here. We get information for all types of plugins and for the overall solving process. Besides
1033 * others, we see that in six calls, the gomory cut separator and the strong Chvátal-Gomory separator each produced
1034 * several hundred cuts (of which only a few entered the LP). The oneopt heuristic found one solution in 4 calls,
1035 * whereas coefdiving failed all 57 times it was called. All the LPs have been solved with the dual simplex algorithm, which
1038 * Now, we can start playing around with parameters. Rounding and shifting seem to be quite successful on this instance,
1039 * wondering what happens if we disable them? Or what happens, if we are even more rigorous and disable all heuristics?
1053 * <shifting> LP rounding heuristic with infeasibility recovering also using continuous variables
1059 * freq frequency for calling primal heuristic <shifting> (-1: never, 0: only at depth freqofs) [10]
1075 * z 0.1s| 3 | 4 | 140 | 10.5 |1060k| 2 | 22 | 27 | 118 | 27 | 123 | 14 | 0 | 66 | 1.300000e+01 | 1.900000e+01 | 46.15%
1076 * z 0.1s| 6 | 7 | 176 | 11.4 |1063k| 5 | 18 | 27 | 118 | 27 | 123 | 14 | 0 | 118 | 1.300000e+01 | 1.900000e+01 | 46.15%
1077 * * 0.1s| 39 | 28 | 386 | 7.0 |1092k| 14 | - | 27 | 118 | 27 | 123 | 14 | 0 | 199 | 1.300000e+01 | 1.800000e+01 | 38.46%
1089 * We can navigate through the menus step-by-step and get a list of available options and submenus. Thus, we select
1090 * "set" to change settings, "heuristics" to change settings of primal heuristics, "shifting" for that particular
1091 * heuristic. Then we see a list of parameters (and yet another submenu for advanced parameters), and disable this
1092 * heuristic by setting its calling frequency to -1. If we already know the path to a certain setting, we can directly
1093 * type it (as for the rounding heuristic in the above example). Note that we do not have to use the full names, but we
1096 * To solve a problem a second time, we have to read it and start the optimization process again.
1116 * D 0.1s| 1 | 0 | 107 | - | 971k| 0 | 24 | 27 | 122 | 27 | 131 | 13 | 4 | 0 | 1.300000e+01 | 1.800000e+01 | 38.46%
1117 * 0.1s| 1 | 0 | 107 | - | 971k| 0 | 24 | 27 | 122 | 27 | 131 | 13 | 4 | 0 | 1.300000e+01 | 1.800000e+01 | 38.46%
1118 * 0.1s| 1 | 0 | 119 | - |1111k| 0 | 24 | 27 | 122 | 27 | 132 | 14 | 4 | 0 | 1.300000e+01 | 1.800000e+01 | 38.46%
1119 * 0.1s| 1 | 2 | 119 | - |1112k| 0 | 24 | 27 | 122 | 27 | 132 | 14 | 4 | 24 | 1.300000e+01 | 1.800000e+01 | 38.46%
1120 * time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
1121 * 0.2s| 100 | 59 | 698 | 5.8 |1138k| 14 | 11 | 27 | 122 | 27 | 123 | 14 | 4 | 204 | 1.300000e+01 | 1.800000e+01 | 38.46%
1122 * 0.2s| 200 | 91 | 1226 | 5.6 |1155k| 14 | - | 27 | 122 | 27 | 123 | 14 | 4 | 207 | 1.300000e+01 | 1.800000e+01 | 38.46%
1135 * Okay, what happened here? First, we reset all parameters to their default values, using "set default". Next, we
1136 * loaded some meta-parameter settings (also see <a href="http://scip.zib.de/#faq">the FAQ</a>), to apply primal heuristics
1137 * more aggressively. SCIP shows us, which single parameters it changed therefor. Now, the optimal solution is already
1138 * found at the root node, by a heuristic which is deactivated by default. Then, after node 200, the user pressed
1139 * CTRL-C which interrupts the solving process, We see that now in the short status report, primal and dual bound are
1140 * different, thus, the problem is not solved yet. Nevertheless, we could access statistics, see the current incumbent
1141 * solution, change parameters and so on. Entering "optimize" we continue the solving process from the point on at which
1144 * SCIP can also write information to files. E.g., we could store the incumbent solution to a file, or output the
1145 * problem instance in another file format (the LP format is much more human readable than the MPS format, for example).
1159 * We hope this tutorial gave you an overview of what is possible using the SCIP interactive shell. Please also read our
1160 * \ref FAQ, in particular the section <a href="http://scip.zib.de/#faq">Using SCIP as a standalone MIP/MINLP-Solver</a>.
1163 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
1166 * If you are looking for a method in order to perform a specific task, there are usually two places to look at:
1168 * In this main header file, you find all methods that perform "complex" operations that affect or need data from
1170 * For these methods, you always have to provide the SCIP pointer that is created by SCIPcreate().
1171 * The documentation of "scip.h" is grouped into several blocks, each dealing with methods for a specific kind of
1175 * - The files \ref PUBLICMETHODS "pub_<...>.h" contain methods that perform "easy" operations that only
1180 * The file "pub_misc.h" contains methods for data structures like priority queues, hash tables, and hash maps,
1181 * as well as methods for sorting, numerics, random numbers, string operations, and file operations.
1183 * If you are looking for a description of a callback method of a plugin that you want to implement, you have to
1187 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
1190 * A constraint handler defines the semantics and the algorithms to process constraints of a certain class. A single
1191 * constraint handler is responsible for all constraints belonging to its constraint class. For example, there is
1192 * one \ref cons_knapsack.h "knapsack constraint handler" that ensures solutions are only accepted if they satisfy all
1193 * knapsack constraints in the model. \n A complete list of all constraint handlers contained in this release can be
1197 * For an example, look into the subtour constraint handler (examples/TSP/src/ConshdlrSubtour.cpp) of the
1201 * It is very easy to transfer the C explanation to C++; whenever a method should be implemented using the
1202 * SCIP_DECL_CONS... notion, reimplement the corresponding virtual member function of the abstract scip::ObjConshdlr
1205 * Additional documentation for the callback methods of a constraint handler can be found in the file
1209 * -# Copy the template files src/scip/cons_xyz.c and src/scip/cons_xyz.h into files "cons_subtour.c"
1212 * Make sure to <b>adjust your Makefile</b> such that these files are compiled and linked to your project.
1213 * -# Use SCIPincludeConsSubtour() in order to include the constraint handler into your SCIP instance,
1217 * -# Define the \ref CONS_DATA "constraint data and the constraint handler data". This is optional.
1220 * -# Implement the \ref CONS_ADDITIONALCALLBACKS "additional callback methods". This is optional.
1226 * These are given as compiler defines. Some of them are optional, as, e.g., separation-related properties,
1228 * In the C++ wrapper class, you have to provide the constraint handler properties by calling the constructor
1229 * of the abstract base class scip::ObjConshdlr from within your constructor (see the TSP example).
1236 * Additionally, if you are searching for a constraint handler with SCIPfindConshdlr(), this name is looked up.
1240 * This string is printed as a description of the constraint handler in the interactive shell of SCIP.
1243 * Like the separation priority, the enforcement priorities define the order in which the different constraint handlers
1245 * The constraint enforcement is called after the price-and-cut loop is executed (in the case that the LP is solved
1249 * That means, if a constraint handler has negative enforcement priority, it only has to deal with integral solutions
1250 * in its enforcement methods, because for fractional solutions, the integrality constraint handler would have
1252 * If you want to implement a constraint-depending branching rule (for example, SOS branching on special ordered
1253 * set constraints), you have to assign a positive enforcement priority to your constraint handler.
1258 * \par CONSHDLR_CHECKPRIORITY: the priority of the constraint handler for checking feasibility.
1259 * Like the separation priority, the checking priorities define the order in which the different constraint handlers
1262 * That means, constraint handlers with negative checking priorities only have to deal with integral solutions.
1264 * \par CONSHDLR_EAGERFREQ: the default frequency for using all instead of only the useful constraints in separation, propagation and enforcement.
1265 * If \em constraint \em aging is activated, some constraints that were not useful in the past for propagation or
1267 * Usually, the obsolete constraints are not presented to the separation and propagation methods of the constraint
1269 * However, every n'th call, with n being the EAGERFREQ of the constraint handler, all constraints are presented to the
1273 * If the eager evaluation frequency is set to -1, obsolete constraints are never presented to the separation and
1275 * A frequency of 0 means, that obsolete constraints are only used in the first call of each method.
1277 * \par CONSHDLR_NEEDSCONS: indicates whether the constraint handler should be skipped, if no constraints are available.
1278 * Usually, a constraint handler is only executed if there are constraints of its corresponding class in the model.
1280 * However, some constraint handlers must be called without having a constraint of the class in the model, because
1282 * For example, the integrality constraint handler has the NEEDSCONS flag set to FALSE, because there is no explicit
1284 * The integrality conditions are attached to the variables, and the integrality constraint handler has to check
1289 * The following properties are optional and only need to be defined if the constraint handlers support
1292 * \par LINCONSUPGD_PRIORITY: priority of the constraint handler for upgrading of linear constraints
1293 * This property is only needed if a certain linear constraint can be upgraded to a more specific one. In one of
1294 * the first presolving rounds SCIP tries to upgrade linear constraints to more specialized constraints, such as
1297 * \par NONLINCONSUPGD_PRIORITY: priority of the constraint handler for upgrading of nonlinear constraints
1298 * This property has the same effect as the LINCONSUPGD_PRIORITY parameter, see above, and should be set whenever
1299 * an upgrade functionality from a general nonlinear constraint to the more specific one is defined.
1302 * The separation frequency defines the depth levels at which the constraint handler's separation methods \ref CONSSEPALP
1304 * For example, a separation frequency of 7 means, that the separation callback is executed for subproblems that are
1306 * A separation frequency of 0 means, that the separation method is only called at the root node.
1311 * If you want to have a more flexible control of when to execute the separation algorithm, you have to assign
1312 * a separation frequency of 1 and implement a check at the beginning of your separation algorithm whether you really
1316 * \par CONSHDLR_SEPAPRIORITY: the priority of the constraint handler for separation. (optional: to be set only if the constraint handler supports separation)
1317 * In each separation round during the price-and-cut loop of the subproblem processing or during the separation loop
1318 * of the primal solution separation, the separators and separation methods of the constraint handlers are called in
1319 * a predefined order, which is given by the priorities of the separators and the separation priorities of the
1321 * First, the separators with non-negative priority are called in the order of decreasing priority.
1322 * Next, the separation methods of the different constraint handlers are called in the order of decreasing separation
1324 * Finally, the separators with negative priority are called in the order of decreasing priority.
1326 * The separation priority of the constraint handler should be set according to the complexity of the cut separation
1328 * Constraint handlers that provide fast algorithms that usually have a high impact (i.e., cut off a large portion of
1332 * \par CONSHDLR_DELAYSEPA: the default for whether the separation method should be delayed, if other separators found cuts.
1333 * If the constraint handler's separation method is marked to be delayed, it is only executed after no other separator
1335 * If the separation method of the constraint handler is very expensive, you may want to mark it to be delayed until all
1339 * This default frequency has the same meaning as the CONSHDLR_SEPAFREQ with respect to the domain propagation
1341 * A propagation frequency of 0 means that propagation is only applied in preprocessing and at the root node.
1344 * \par CONSHDLR_DELAYPROP: the default for whether the propagation method should be delayed, if other propagators found reductions.
1345 * This property is analogous to the DELAYSEPA flag, but deals with the propagation method of the constraint handler.
1349 * This property indicates at which places the propagation routine of the constraint handler is called.
1350 * Possible values are defined in type_timing.h and can be concatenated, e.g., as in SCIP_PROPTIMING_ALWAYS.
1352 * \par CONSHDLR_MAXPREROUNDS: the default maximal number of presolving rounds the constraint handler participates in.
1354 * If enough changes have been applied to the model, an additional preprocessing round is performed.
1355 * The MAXPREROUNDS parameter of a constraint handler denotes the maximal number of preprocessing rounds the constraint
1360 * \par CONSHDLR_DELAYPRESOL: the default for whether the presolving method should be delayed, if other presolvers found reductions.
1361 * This property is analogous to the DELAYSEPA flag, but deals with the preprocessing method of the constraint handler.
1367 * Below the header "Data structures" you can find two structs called "struct SCIP_ConsData" and
1370 * The constraint handler data must be implemented as member variables of your constraint handler class.
1372 * The constraint data are the information that is needed to define a single constraint of the constraint handler's
1374 * For example, the data of a knapsack constraint would consist of a list of variables, a list of weights, and
1379 * The constraint handler data are additional variables, that belong to the constraint handler itself and which are
1381 * For example, you can use these data to store parameters of the constraint handler or statistical information.
1388 * At the bottom of "cons_subtour.c" you can find three interface methods, that also appear in "cons_subtour.h".
1389 * These are SCIPincludeConshdlrSubtour(), SCIPcreateConsSubtour(), and SCIPcreateConsSubtourBasic().
1392 * It is responsible for notifying SCIP of the presence of the constraint handler by calling the method
1394 * It is called by the user, if (s)he wants to include the constraint handler, i.e., if (s)he wants to make
1396 * -# If you are using constraint handler data, you have to <b>allocate the memory for the data</b> at this point.
1410 * -# Now, <b>SCIP gets notified</b> of the presence of the constraint handler together with its \ref CONS_FUNDAMENTALCALLBACKS "basic callbacks".
1418 * -# All \ref CONS_ADDITIONALCALLBACKS "additional callbacks" are added via their setter functions.
1423 * -# If the constraint handler is a specialization of a general linear or nonlinear constraint, we want to include an <b>automatic
1428 * SCIP_CALL( SCIPincludeLinconsUpgrade(scip, linconsUpgdKnapsack, LINCONSUPGD_PRIORITY, CONSHDLR_NAME) );
1433 * SCIP_CALL( SCIPincludeNonlinconsUpgrade(scip, nonlinconsUpgdSubtour, NULL, NONLINCONSUPGD_PRIORITY, TRUE, CONSHDLR_NAME) );
1436 * See also cons_nonlinear.h for further information about the general upgrade procedure in the nonlinear case.
1438 * Some parameters which are important to play with are added to every constraint automatically, as, e.g.,
1443 * "multiplier on separation frequency, how often knapsack cuts are separated (-1: never, 0: only at root)",
1453 * The methods SCIPcreateConsSubtour() and SCIPcreateConsSubtourBasic() are called to create a single constraint of the constraint
1456 * Take a look at the following example from the \ref cons_knapsack.h "knapsack constraint handler":
1494 * SCIP_CALL( consdataCreate(scip, &consdata, conshdlrdata->eventhdlr, nvars, vars, weights, capacity) );
1496 * SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
1503 * In this example, consdataCreate() is a local method that allocates memory for the given consdata
1504 * and fills the data with the given <code>vars</code> array. For allocating memory for the constraint data, you
1513 * Besides the various functions which you will implement inside your constraint handler there exists a number
1514 * of <b> callback methods </b> associated with your constraint handler. Callback methods can be regarded as
1515 * tasks which your constraint handler is able to provide to the solver. They are grouped into two
1525 * \ref CONS_ADDITIONALCALLBACKS "additional callbacks". Such callbacks can be used to allocate and free memory
1526 * at different stages of the solving process. Although not mandatory, it might be useful to implement
1531 * (e.g., SCIPincludeConshdlrKnapsack() for the \ref cons_knapsack.h "knapsack constraint handler").
1532 * Since SCIP version 3.0, two ways of setting callbacks can be used, either via SCIPincludeConshdlr()
1533 * (all at once, as it always was), or via SCIPincludeConshdlrBasic() and setter functions for additional callbacks.
1540 * By implementing the fundamental callbacks, you define the semantics of the constraint class the constraint handler
1542 * If these methods are implemented, the resulting code is already correct and finds the optimal solution to the
1544 * However, it might be very slow because the additional features, like cut separation and domain propagation, are
1546 * In the C++ wrapper class scip::ObjConshdlr, the fundamental callback methods are virtual abstract member functions.
1547 * You have to implement them in order to be able to construct an object of your constraint handler class.
1549 * There are three fundamental callback methods that are all dealing with the feasibility of a given solution.
1551 * However, it is usually reasonable to implement a single local method that is called by all of the three callback
1561 * It has to return a result SCIP_FEASIBLE, if the solution satisfies all the constraints of the constraint handler,
1564 * That means, the constraint handler has to deal with arbitrary solutions that do not necessarily satisfy the bounds
1572 * For example, the \ref cons_knapsack.h "knapsack constraint handler" loops over its constraints and
1573 * calculates the scalar product \f$w^T x\f$ of weights \f$w\f$ with the solution vector \f$x\f$.
1575 * If it exceeds the capacity, the CONSCHECK method is immediately aborted with the result SCIP_INFEASIBLE.
1580 * The CONSENFOLP method is called after the price-and-cut loop was finished and an LP solution is available.
1581 * Like the CHECK call, the ENFOLP method should return a result SCIP_FEASIBLE, if the solution satisfies all the
1583 * However, the behavior should be different, if the solution violates some of the associated constraints.
1584 * The constraint handler may return a result SCIP_INFEASIBLE in this situation, but this is not the best what
1603 * By using the latter method, you can have a single local method to check a solution for feasibility by passing
1604 * the given <code>sol</code> to the CONSCHECK call and by passing a NULL pointer as <code>sol</code> to
1610 * The CONSENFOPS callback is similar to the CONSENFOLP callback, but deals with \em pseudo \em solutions instead
1613 * If the LP was not solved at the current subproblem (either because the user did not want to solve it, or because
1616 * In this solution, the variables are set to the local bound which is best with respect to the objective function.
1617 * You can think of the pseudo solution as solution to the LP relaxation with all constraints except the bounds
1620 * Like the ENFOLP callback, the ENFOPS callback has to check whether the pseudo solution satisfies all the constraints
1622 * The pseudo solution can be accessed by the same methods as the LP solution (SCIP knows, if the LP was solved at the
1625 * Unlike the ENFOLP callback, the ENFOPS callback must not add cuts and cannot return the result SCIP_SEPARATED.
1626 * It is, however, possible to force the solving of the LP by returning the result SCIP_SOLVELP.
1627 * For example, the infeasibility of a linear constraint that contains continuous variables cannot be resolved,
1629 * In this case, the LP has to be solved in order to get a solution that satisfies the linear constraint.
1634 * It has to tell SCIP, which variables are existing in the given constraint, and in which way modifications of these
1637 * For each variable that is affected by the constraint, the callback should call SCIPaddVarLocks():
1638 * - If the constraint may become violated by decreasing the value of a variable, it should call
1639 * SCIPaddVarLocks(scip, var, nlockspos, nlocksneg), saying that rounding down is potentially rendering the
1640 * (positive) constraint infeasible and rounding up is potentially rendering the negation of the constraint
1642 * - If the constraint may become violated by increasing the value of a variable, it should call
1643 * SCIPaddVarLocks(scip, var, nlocksneg, nlockspos), saying that rounding up is potentially rendering the
1644 * constraint's negation infeasible and rounding down is potentially rendering the constraint itself
1646 * - If the constraint may become violated by changing the variable in any direction, it should call
1649 * <b>Note:</b> You do not have to worry about nlockspos and nlocksneg. These integer values are given as
1650 * parameter of the CONSLOCK callback (see type_cons.h). Just use these variables in the above described
1651 * fashion <b>without</b> adding or subtracting anything to them. In case of the knapsack constraints this
1673 * To give same more intuition, consider the linear constraint \f$3x -5y +2z \leq 7\f$ as an example.
1675 * SCIPaddVarLocks(scip, x, nlocksneg, nlockspos), SCIPaddVarLocks(scip, y, nlockspos, nlocksneg),
1677 * and \f$z\f$ and rounding down of \f$y\f$ can destroy the feasibility of the constraint, while rounding
1689 * The additional callback methods do not need to be implemented in every case, but provide useful functionality
1690 * for many applications. They can be added to your constraint handler via setter functions, see
1695 * If you are using constraint handler data, you have to implement this method in order to free the
1696 * constraint handler data. This can be done by the following procedure (which is taken from the
1716 * If you have allocated memory for fields in your constraint handler data, remember to free this memory
1723 * The CONSHDLRCOPY callback is executed when the SCIP instance is copied, e.g. to solve a sub-SCIP. By defining this
1724 * callback as <code>NULL</code> the user disables the inclusion of the specified constraint handler into all copied SCIP
1725 * instances. This may deteriorate the performance of primal heuristics solving sub-SCIPs, since these constitute only
1729 * calls the interface method which includes the constraint handler to the model. For example, this callback is
1748 * <b>Note:</b> If you implement this callback, take care when setting the valid pointer. The valid pointer should be
1749 * set to TRUE if (and only if!) you can make sure that all necessary data of the constraint handler are copied
1750 * correctly. If the complete problem is validly copied, i.e. if the copy methods of all problem defining plugins
1751 * (constraint handlers and pricers) return <code>*valid = TRUE</code>, then dual reductions found for the copied problem can be
1752 * transferred to the original SCIP instance. Thus, if the valid pointer is wrongly set to TRUE, it might happen that
1755 * <b>Note:</b> If you implement this callback and the constraint handler needs constraints (see CONSHDLR_NEEDSCONS),
1761 * The constraint handler may, e.g., use this call to replace the original variables in its constraints by transformed
1767 * In this method, the constraint handler should free all resources that were allocated for the solving process.
1771 * The CONSINITPRE callback is executed before the preprocessing is started, even if presolving is turned off.
1772 * The constraint handler may use this call to initialize its presolving data, or to modify its constraints
1774 * Necessary constraint modifications that have to be performed even if presolving is turned off should be done here
1779 * The CONSEXITPRE callback is executed after the preprocessing has been finished, even if presolving is turned off.
1780 * The constraint handler may use this call e.g. to clean up its presolving data, or to finally modify its constraints
1782 * Necessary constraint modifications that have to be performed even if presolving is turned off should be done here
1788 * The CONSINITSOL callback is executed when the presolving is finished and the branch-and-bound process is about to
1795 * The constraint handler should use this call to clean up its branch-and-bound data, in particular to release
1803 * The CONSDELETE callback is therefore the counterpart of the SCIPcreateCons...() interface method and the CONSTRANS
1808 * The CONSTRANS method is called for each constraint of the constraint handler, when the user starts the solving
1810 * It has to copy the original constraint data of the constraint to the memory for the transformed problem.
1813 * The original model is copied in order to protect it from transformations that are applied during the solving process,
1816 * If the solving process data are freed, the original data still exist and the user can, e.g., modify the problem and
1819 * If you do not implement the CONSTRANS method, a transformed constraint is created with the same flags and the
1823 * If you want to implement preprocessing methods or other methods that modify the constraint data, you have to
1826 * Here is an example, which is taken from the \ref cons_knapsack.h "knapsack constraint handler":
1852 * SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
1853 * SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
1856 * SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
1865 * It should add the LP relaxations of all "initial" constraints to the LP. The method should scan the constraints
1866 * array for constraints that are marked initial via calls to SCIPconsIsInitial() and put the LP relaxation
1871 * The CONSSEPALP callback is executed during the price-and-cut loop of the subproblem processing.
1872 * It should try to generate cutting planes for the constraints of the constraint handler in order to separate
1876 * Usually, a separation callback searches and produces cuts, that are added with a call to SCIPaddCut().
1881 * - detecting that the node is infeasible in the variables' bounds and can be cut off (result SCIP_CUTOFF)
1885 * - stating that the separator searched, but did not find domain reductions, cutting planes, or cut constraints
1889 * - stating that a new separation round should be started without calling the remaining separator methods (result SCIP_NEWROUND)
1892 * CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, and CONSHDLR_DELAYSEPA, which influence the behaviour of SCIP
1898 * It should try to generate cutting planes for the constraints of the constraint handler in order to separate
1900 * The method is not called in the LP solution loop, which means that there is no valid LP solution.
1902 * Usually, a separation callback searches and produces cuts, that are added with a call to SCIPaddCut().
1907 * - detecting that the node is infeasible in the variables' bounds and can be cut off (result SCIP_CUTOFF)
1911 * - stating that the separator searched, but did not find domain reductions, cutting planes, or cut constraints
1915 * - stating that a new separation round should be started without calling the remaining separator methods (result SCIP_NEWROUND)
1918 * CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, and CONSHDLR_DELAYSEPA, which influence the behaviour of SCIP
1924 * It should propagate the constraints, which means that it should infer reductions in the variables' local bounds
1926 * This technique, which is the main workhorse of constraint programming, is called "node preprocessing" in the
1930 * - detecting that the node is infeasible in the variables' bounds and can be cut off (result SCIP_CUTOFF)
1932 * - stating that the propagator searched, but did not find domain reductions, cutting planes, or cut constraints
1938 * CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP, and CONSHDLR_PROP_TIMING, which influence the behaviour of SCIP
1943 * If the constraint handler should support \ref CONF "conflict analysis", it has to supply a CONSRESPROP method.
1944 * It also should call SCIPinferVarLbCons() or SCIPinferVarUbCons() in domain propagation instead of SCIPchgVarLb() or
1946 * In the SCIPinferVarLbCons() and SCIPinferVarUbCons() calls, the handler provides the constraint that deduced the
1947 * variable's bound change, and an integer value <code>inferinfo</code> that can be arbitrarily chosen.
1949 * The propagation conflict resolving method CONSRESPROP must then be implemented to provide the "reasons" for the bound
1950 * changes, i.e., the bounds of variables at the time of the propagation, which forced the constraint to set the
1951 * conflict variable's bound to its current value. It can use the <code>inferinfo</code> tag to identify its own propagation rule
1952 * and thus identify the "reason" bounds. The bounds that form the reason of the assignment must then be provided by
1953 * calls to SCIPaddConflictLb() and SCIPaddConflictUb() in the propagation conflict resolving method.
1955 * <b>Note:</b> The fact that <code>inferinfo</code> is an integer, as opposed to an arbitrary data object, is a compromise between space and speed. Sometimes a propagator would
1956 * need more information to efficiently infer the original propagation steps that lead to the conflict. This would,
1957 * however, require too much space. In the extreme, the original propagation steps have to be repeated.
1959 * For example, the \ref cons_logicor.h "logicor constraint" \f$c = x \vee y \vee z\f$ fixes variable \f$z\f$ to TRUE (i.e., changes the lower
1960 * bound of \f$z\f$ to 1.0), if both, \f$x\f$ and \f$y\f$, are assigned to FALSE (i.e., if the upper bounds of these
1961 * variables are 0.0). It uses <code>SCIPinferVarLbCons(scip, z, 1.0, c, 0)</code> to apply this assignment (an
1962 * inference information tag is not needed by the constraint handler and is set to 0). In the conflict analysis, the
1963 * constraint handler may be asked to resolve the lower bound change on \f$z\f$ with constraint \f$c\f$, that was
1964 * applied at a time given by a bound change index "bdchgidx". With a call to <code>SCIPvarGetLbAtIndex(z,
1965 * bdchgidx)</code>, the handler can find out, that the lower bound of variable \f$z\f$ was set to 1.0 at the given
1966 * point of time, and should call <code>SCIPaddConflictUb(scip, x, bdchgidx)</code> and <code>SCIPaddConflictUb(scip, y,
1967 * bdchgidx)</code> to tell SCIP, that the upper bounds of \f$x\f$ and \f$y\f$ at this point of time were the reason for
1970 * If conflict analysis should not be supported, the method has to set the result code to SCIP_DIDNOTFIND. Although
1971 * this is a viable approach to circumvent the implementation of the usually rather complex conflict resolving method, it
1972 * will make the conflict analysis less effective. We suggest to first omit the conflict resolving method and check how
1973 * effective the \ref CONSPROP "propagation method" is. If it produces a lot of propagations for your application, you definitely should
1979 * It should try to tighten the domains of the variables, tighten the coefficients of the constraints of the constraint
1980 * handler, delete redundant constraints, aggregate and fix variables if possible, and upgrade constraints to more
1983 * If the CONSPRESOL callback applies changes to the constraint data, you also have to implement the \ref CONSTRANS callback
1984 * in order to copy the constraint data to the transformed problem space and protect the original problem from the
1987 * To inform SCIP that the presolving method found a reduction the result pointer has to be set in a proper way.
1990 * - SCIP_UNBOUNDED : at least one variable is not bounded by any constraint in objective direction
2003 * The CONSACTIVE callback method is called each time a constraint of the constraint handler is activated.
2004 * For example, if a constraint is added locally to a subproblem, the CONSACTIVE callback is called whenever the
2009 * The CONSDEACTIVE callback method is called each time a constraint of the constraint handler is deactivated.
2010 * For example, if a constraint is added locally to a subproblem, the CONSDEACTIVE callback is called whenever the
2015 * The CONSENABLE callback method is called each time a constraint of the constraint handler is enabled.
2016 * Constraints might be active without being enabled. In this case, only the feasibility checks are executed,
2021 * The CONSDISABLE callback method is called each time a constraint of the constraint handler is disabled.
2025 * The CONSPRINT callback method is called, when the user asks SCIP to display the problem to the screen
2026 * or save the problem into a file. This is, however, only the case if the user requested the CIP format.
2027 * For more details about reading and writing with SCIP we refer to the \ref READER "file readers". In this
2028 * callback method the constraint handler should display the data of the constraint in an appropriate form.
2030 * In later versions of SCIP, the constraint handlers should also be able to parse (i.e., read) constraints
2035 * The CONSCOPY callback method is used whenever constraints should be copied from one SCIP instance into another SCIP
2036 * instance. This method comes with the necessary parameters to do so, most importantly with a mapping of the variables of the
2037 * source SCIP instance to the corresponding variables of the target SCIP instance, and a mapping for the constraints
2038 * in the same way. For a complete list of all arguments of this callback method see type_cons.h.
2040 * To get the corresponding target variable of a given source variable, you can use the variable map directly:
2046 * We recommend, however, to use the method SCIPgetVarCopy() which gets besides others the variable map and the constraint map as input
2047 * and returns the requested target variable. The advantage of using SCIPgetVarCopy() is that in the case
2051 * SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevar, &targetvar, varmap, consmap, global) );
2054 * Finally, the result pointer <code>valid</code> has to be set to TRUE if (and only if!) the copy process was successful.
2056 * <b>Note:</b> Be careful when setting the valid pointer. If you set the valid pointer to TRUE, but the constraint was
2057 * not copied one-to-one, then optimal solutions might be cut off during the search (see section
2060 * For an example implementation we refer to cons_linear.h. Additional documentation and the complete list of all
2065 * This method is the counter part to CONSPRINT. The ideal idea is that a constraint handler is able to parse the output
2066 * which it generated via the CONSPRINT method and creates the corresponding constraint. If the parsing was successfully
2067 * the result pointer success should be set to TRUE. An example implementation can be found in the \ref cons_linear.h
2072 * This method should iterate over the given constraints and delete all variables that were marked for deletion by SCIPdelVar().
2073 * Variable deletion is especially interesting for branch-cut-and-price applications. If your constraint handler allows
2074 * the addition of variables during the solving process (see "modifiable" attribute of constraints), then you might also want to
2075 * implement this callback. This would allow you to not only create variables during solving, but also remove them dynamically
2077 * During presolving, SCIP may also find that some variables are not needed anymore and then try
2078 * to delete them. Thus, if you do not implement this callback, the constraint handler should capture its variables via
2081 * Additional documentation and the complete list of all parameters can be found in the file type_cons.h.
2085 * The CONSGETVARS callback of a constraint handler can be implemented to give access to the constraint variables
2087 * is already passed, together with its length. Consider implementing @ref CONSGETNVARS, too, to have
2092 * This callback can be implemented to return the number of variables involved into a particular constraint.
2097 * Further documentation can be found in @ref type_cons.h for callback descriptions and a complete
2102 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
2107 * The \ref PRICERREDCOST and \ref PRICERFARKAS methods are called after each LP solve to generate additional
2108 * variables which may improve the objective value or decrease the LP infeasibility, respectively.
2112 * If the pricer finds one or more variables with negative reduced costs or negative Farkas value, it should
2113 * call SCIPcreateVar() and SCIPaddPricedVar() to create and add the variable to the problem. Additionally,
2114 * the pricer has to add the variable to all constraints in which it appears. Therefore, a pricer needs to
2115 * know the constraints of the model and their meaning. Note that all constraints for which additional variables
2119 * For example, look into the stable set pricer for the coloring problem (examples/Coloring/src/pricer_coloring.c) of the
2121 * The example is written in C. C++ users can easily adapt the code by using the scip::scip::ObjPricer wrapper base class and
2122 * implement the scip_...() virtual methods instead of the SCIP_DECL_PRICER... callback methods.
2127 * Notice that if your pricer cannot cope with variable bounds other than 0 and infinity, you have to mark
2128 * all constraints containing priced variables as modifiable, and you may have to disable reduced cost
2132 * -# Copy the template files src/scip/pricer_xyz.c and src/scip/pricer_xyz.h into files "pricer_mypricer.c"
2135 * Make sure to adjust your Makefile such that these files are compiled and linked to your project.
2143 * -# Implement the additional callback methods (see \ref PRICER_ADDITIONALCALLBACKS). This is optional.
2150 * In the C++ wrapper class, you have to provide the pricer properties by calling the constructor
2156 * Additionally, if you are searching for a pricer with SCIPfindPricer(), this name is looked up.
2163 * In each pricing round during the price-and-cut loop of the subproblem processing, the included pricers are
2166 * Usually, you will have only one pricer in your application and the priority is therefore irrelevant.
2168 * \par PRICER_DELAY: the default for whether the pricer should be delayed, if other variables with negative reduced
2170 * Variables may be declared to be "removable" in the SCIPcreateVar() call. This means that SCIP may remove the variable
2171 * from the LP if it was inactive (i.e., sitting at zero) for a number of LP solves. Nevertheless, after the removal of the
2172 * column from the LP, the variable still exists, and SCIP can calculate reduced costs and add it to the LP again if
2175 * If the PRICER_DELAY flag is set to TRUE (which is the common setting), all those existing variables with negative reduced costs
2176 * are added to the LP, and the LP is resolved before the pricer is called. Thus, the pricer can assume that all existing variables
2177 * have non-negative reduced costs if the \ref PRICERREDCOST method is called or non-positive Farkas value if the \ref PRICERFARKAS
2180 * In some applications, this inner pricing loop on the already existing variables can significantly slow down the solving process,
2181 * since it may lead to the addition of only very few variables in each pricing round. If this is an issue in your application,
2182 * you should consider setting the PRICER_DELAY flag to FALSE. You must, however, be aware of the fact that there may be already
2183 * existing variables with negative reduced costs. For example, this may lead to the issue that your pricer generates the same
2184 * variable twice. In some models, this is not critical because an optimal solution would choose only one of the two identical
2185 * variables anyway, but for other models this can lead to wrong results because the duplication of a variable essentially doubles
2191 * Below the header "Data structures" you can find a struct which is called "struct SCIP_PricerData".
2192 * In this data structure, you can store the data of your pricer. For example, it may be convenient to store pointers to the
2193 * constraints of the problem instance here, because the pricer has to add variables to those constraints.
2201 * At the bottom of "pricer_mypricer.c" you can find the interface method SCIPincludePricerMypricer(), which also appears in "pricer_mypricer.h".
2202 * It is called by the user, if (s)he wants to include the pricer, i.e., if (s)he wants to solve a model for which variables should
2206 * It is responsible for notifying SCIP of the presence of the pricer. For this, you can either call SCIPincludePricer(),
2207 * or SCIPincludePricerBasic() since SCIP version 3.0. In the latter variant, \ref PRICER_ADDITIONALCALLBACKS "additional callbacks"
2208 * must be added via setter functions as, e.g., SCIPsetPricerCopy(). We recommend this latter variant because
2209 * it is more stable towards future SCIP versions which might have more callbacks, whereas source code using the first
2210 * variant must be manually adjusted with every SCIP release containing new callbacks for pricers in order to compile.
2213 * In addition, the pricer has to be activated before the solution process starts, like it is done
2226 * You may also add user parameters for your pricer, see the method SCIPincludePricerColoring() in the pricer of the Coloring example
2232 * The fundamental callback methods have to be implemented in order to obtain an operational algorithm.
2233 * They are passed together with the pricer itself to SCIP using SCIPincludePricer() or SCIPincludePricerBasic(),
2236 * In the case of a pricer, there are two fundamental callback methods, namely the @ref PRICERREDCOST and the
2237 * @ref PRICERFARKAS callbacks, which both search for new variables and add them to the problem.
2238 * These methods have to be implemented for every pricer; the other callback methods are optional.
2239 * In the C++ wrapper class scip::ObjPricer, the scip_redcost() method (which corresponds to the PRICERREDCOST callback)
2240 * is a virtual abstract member function. You have to implement it in order to be able to construct an object of your
2247 * The PRICERREDCOST callback is called inside the price-and-cut loop of the subproblem solving process if the current LP relaxation
2249 * It should search for additional variables that can contribute to improve the current LP's solution value.
2250 * In standard branch-and-price, these are variables with negative dual feasibility, that is negative
2254 * Whenever the pricer finds a variable with negative dual feasibility, it should call SCIPcreateVar()
2255 * and SCIPaddPricedVar() to add the variable to the problem. Furthermore, it should call the appropriate
2256 * methods of the constraint handlers to add the necessary variable entries to the constraints, see pub_cons.h.
2258 * In the usual case that the pricer either adds a new variable or ensures that there are no further variables with negative dual feasibility,
2259 * the result pointer should be set to SCIP_SUCCESS. Only if the pricer aborts pricing without creating a new variable, but
2260 * there might exist additional variables with negative dual feasibility, the result pointer should be set to SCIP_DIDNOTRUN.
2261 * In this case, which sometimes is referred to as "early branching", the LP solution will not be used as a lower bound.
2265 * Since SCIP does not know the semantics of the individual constraints in the problem, the dual solution
2267 * For example, the \ref cons_setppc.h "setppc constraint handler", which deals with set partitioning, packing, and covering constraints, provides
2269 * Similarly, the dual solution of a linear constraint can be queried with the method SCIPgetDualsolLinear() of cons_linear.h.
2270 * The reduced costs of the existing variables can be accessed with the method SCIPgetVarRedcost().
2274 * If the current LP relaxation is infeasible, it is the task of the pricer to generate additional variables that can
2275 * potentially render the LP feasible again. In standard branch-and-price, these are variables with positive Farkas values,
2278 * If the LP was proven to be infeasible, we have an infeasibility proof by the dual Farkas multipliers \f$y\f$.
2279 * With the values of \f$y\f$, an implicit inequality \f$y^T A x \ge y^T b\f$ is associated, with \f$b\f$ given
2284 * \f$y\f$ is chosen in a way, such that the valid inequality \f$y^T A x \ge y^T b\f$ is violated by all \f$x\f$,
2288 * Pricing in this case means to add variables \f$i\f$ with positive Farkas value, i.e., \f$y^T A_i x'_i > 0\f$.
2290 * To apply Farkas pricing, the pricer needs to know the Farkas values of the constraints. Like the dual solution values for
2291 * feasible LP solutions, the dual Farkas values for infeasible solutions can be obtained by constraint handler interface
2293 * The Farkas values for the bounds of the variables are just the regular reduced costs and can be accessed with SCIPgetVarRedcost().
2295 * It is useful to note that Farkas pricing is the same as the regular pricing with a zero objective function.
2296 * Therefore, a typical implementation of a pricer would consist of a generic pricing algorithm that gets a dual solution and an
2297 * objective function vector as input and generates variables by calling SCIPcreateVar() and SCIPaddPricedVar().
2298 * The PRICERREDCOST callback would call this function with the regular objective function and the regular dual solution vector,
2299 * while the PRICERFARKAS callback would call this function with a zero objective function and the Farkas vector.
2300 * From a practical point of view, it is usually the simplest approach to provide just one Boolean flag to the generic pricing
2301 * algorithm in order to identify whether it is reduced cost or Farkas pricing. Then, the algorithm would just call the appropriate
2307 * However, some of them have to be implemented for most applications. They can either be passed directly with
2308 * SCIPincludePricer() to SCIP or via specific <b>setter functions</b> after a call of SCIPincludePricerBasic(),
2313 * If you are using pricer data, you have to implement this method in order to free the pricer data.
2338 * The PRICERCOPY callback is executed when the SCIP instance is copied, e.g. to solve a sub-SCIP. By defining this
2339 * callback as <code>NULL</code> the user disables the inclusion of the pricer into all copied SCIP
2340 * instances. This means that primal heuristics will work on a sub-SCIP that contains only a part of the variables
2341 * and no variables are priced in during the solving process of the sub-SCIP. Therefore, primal solutions found in the
2342 * copied problem are typically still valid for the original problem and used for its solving process,
2345 * <b>Note:</b> If you implement this callback, be careful when setting the valid pointer. The valid pointer should be
2346 * set to TRUE if (and only if!) you can make sure that all necessary data of the pricer are copied
2347 * correctly. If the complete problem is validly copied, i.e. if the copy methods of all problem defining plugins
2348 * (constraint handlers and pricers) return <code>*valid = TRUE</code>, then dual reductions found for the copied problem can be
2349 * transferred to the original SCIP instance. Thus, if the valid pointer is wrongly set to TRUE, it might happen that
2355 * The pricer may, e.g., use this call to replace the original constraints stored in its pricer data by transformed
2361 * In this method, the pricer should free all resources that have been allocated for the solving process in PRICERINIT.
2365 * The PRICERINITSOL callback is executed when the presolving is finished and the branch-and-bound process is about to begin.
2371 * The pricer should use this call to clean up its branch-and-bound data, which was allocated in PRICERINITSOL.
2375 * If you use your own branching rule (e.g., to branch on constraints), make sure that it is able to branch on \a "pseudo solutions".
2376 * Otherwise, SCIP will use its default branching rules, if necessary (which all branch on variables). This
2377 * could disturb the pricing problem or branching might not even be possible, e.g., if all variables created thus far have already been fixed.
2379 * Note that if the original problem is a maximization problem, SCIP will transform the problem into a minimization
2380 * problem by multiplying the objective function by -1. The pricer has to take care of this by multiplying
2381 * the original objective function value of all variables created during the solving process by -1.
2383 * In some cases, bounds on variables are implicitly enforced by constraints of the problem and the objective function.
2384 * Therefore, these bounds do not need to be added to the LP explicitly, which has the advantage that the pricing routine does not need to
2386 * We call these bounds lazy bounds, they may be set by SCIPchgVarLbLazy() and SCIPchgVarUbLazy() for upper or lower bounds, respectively.
2387 * If the lazy bound is tighter than the local bound, the corresponding bound is not put into the LP.
2388 * In diving mode, lazy bounds are explicitly put into the LP, because changing the objective (which is only possible in diving)
2389 * might reverse the implicitly given bounds. When diving is finished, the bounds are again removed from the LP.
2392 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
2395 * Presolvers are used to reduce the size of the model by removing irrelevant information like redundant constraints,
2396 * to strengthen the LP relaxation by exploiting integrality information, and to extract useful information in the
2398 * Constraint based presolving is done in the CONSPRESOL callback methods of the constraint handlers, see \ref CONSPRESOL.
2399 * The presolver plugins complement the constraint based presolving by additional, usually optimality based, presolving
2402 * A complete list of all presolvers contained in this release can be found \ref PRESOLVERS "here".
2406 * As all other default plugins, it is written in C. C++ users can easily adapt the code by using the scip::ObjPresol wrapper
2407 * base class and implement the scip_...() virtual methods instead of the SCIP_DECL_PRESOL... callback methods.
2409 * Additional documentation for the callback methods of a presolver, in particular for their input parameters,
2413 * -# Copy the template files src/scip/presol_xyz.c and src/scip/presol_xyz.h into files named "presol_mypresolver.c"
2416 * Make sure to adjust your Makefile such that these files are compiled and linked to your project.
2417 * -# Use SCIPincludePresolMypresolver() in order to include the presolver into your SCIP instance,
2419 * -# Open the new files with a text editor and replace all occurrences of "xyz" by "mypresolver".
2424 * -# Implement the additional callback methods (see \ref PRESOL_ADDITIONALCALLBACKS). This is optional.
2431 * In the C++ wrapper class, you have to provide the presolver properties by calling the constructor
2437 * Additionally, if you are searching for a presolver with SCIPfindPresol(), this name is looked up.
2444 * In each presolving round, the presolvers and presolving methods of the constraint handlers are called in
2445 * a predefined order, which is given by the priorities of the presolvers and the check priorities of the
2447 * First, the presolvers with non-negative priority are called in the order of decreasing priority.
2448 * Next, the presolving methods of the different constraint handlers are called in the order of decreasing check
2450 * Finally, the presolvers with negative priority are called in the order of decreasing priority.
2452 * The priority of the presolver should be set according to the complexity of the presolving algorithm and the impact of the reduction:
2453 * presolvers that provide fast algorithms that usually have a high impact (i.e., remove lots of variables or tighten
2455 * priorities of all presolvers and constraint handlers is to type "display presolvers" and "display conshdlrs" in
2459 * The presolving is conducted in rounds: the presolvers and presolving methods of the constraint handlers
2460 * are called iteratively until no more reductions have been found or some other abort criterion applies.
2461 * The "maxrounds" parameter of a presolver imposes a limit on the number of presolving rounds in which the
2462 * presolver is called. The PRESOL_MAXROUNDS property specifies the default value for this parameter.
2465 * \par PRESOL_DELAY: the default for whether the presolver should be delayed, if other presolvers found reductions.
2466 * If the presolver is marked to be delayed, it is only executed if no other presolvers found a reduction during the current
2468 * If the presolver is very expensive, you may want to mark it to be delayed until all cheap presolving methods have been executed.
2473 * Below the header "Data structures" you can find a struct which is called "struct SCIP_PresolData".
2474 * In this data structure, you can store the data of your presolver. For example, you should store the adjustable parameters
2483 * At the bottom of "presol_mypresolver.c", you can find the interface method SCIPincludePresolMypresolver(),
2485 * SCIPincludePresolMypresolver() is called by the user, if (s)he wants to include the presolver,
2489 * It is responsible for notifying SCIP of the presence of the presolver. For this, you can either call SCIPincludePresol(),
2490 * or SCIPincludePresolBasic() since SCIP version 3.0. In the latter variant, \ref PRESOL_ADDITIONALCALLBACKS "additional callbacks"
2491 * must be added via setter functions as, e.g., SCIPsetPresolCopy(). We recommend this latter variant because
2492 * it is more stable towards future SCIP versions which might have more callbacks, whereas source code using the first
2493 * variant must be manually adjusted with every SCIP release containing new callbacks for presolvers in order to compile.
2503 * You may also add user parameters for your presolver, see \ref PARAM for how to add user parameters and
2509 * The fundamental callback methods of the plugins are the ones that have to be implemented in order to obtain
2511 * They are passed together with the presolver itself to SCIP using SCIPincludePresol() or SCIPincludePresolBasic(),
2514 * Presolver plugins have only one fundamental callback method, namely the @ref PRESOLEXEC method.
2515 * This method has to be implemented for every presolver; the other callback methods are optional.
2516 * In the C++ wrapper class scip::ObjPresol, the scip_exec() method (which corresponds to the PRESOLEXEC callback) is a virtual
2525 * The PRESOLEXEC callback is called inside the presolving loop and should perform the actual presolving reductions.
2526 * It should inspect the problem instance at hand and simplify it by tightening bounds of variables, aggregating or fixing
2527 * variables, changing the type of variables, modifying the graph that represents the instance of your application, and
2530 * Typical methods called by a presolver are, for example, SCIPchgVarType(), SCIPfixVar(), SCIPaggregateVars(), SCIPtightenVarLb(),
2536 * The additional callback methods do not need to be implemented in every case. However, some of them have to be
2537 * implemented for most applications, they can be used, for example, to initialize and free private data.
2538 * Additional callbacks can either be passed directly with SCIPincludePresol() to SCIP or via specific
2539 * <b>setter functions</b> after a call of SCIPincludePresolBasic(), see also @ref PRESOL_INTERFACE.
2543 * If you are using presolver data (see \ref PRESOL_DATA and \ref PRESOL_INTERFACE), you have to implement this method in order to free the presolver data.
2585 * In this method, the presolver should free all resources that have been allocated for the solving process in PRESOLINIT.
2590 * The presolver may use this call to initialize its presolving data which only need to exist during the presolving stage.
2594 * The PRESOLEXITPRE callback is executed after presolving finishes and before the branch-and-bound process begins.
2595 * The presolver should use this call to clean up its presolving data, which was allocated in PRESOLINITPRE.
2598 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
2602 * Constraint based cutting planes, the second type of cutting planes in SCIP, are separated in the CONSSEPALP and
2603 * CONSSEPASOL callback methods of the constraint handlers, see \ref CONSSEPALP and \ref CONSSEPASOL. These cuts are
2604 * valid inequalities or even facets of the polyhedron described by a single constraint or a subset of the constraints of
2605 * a single constraint class. In contrast, general purpose cuts do not require or exploit any knowledge about the
2606 * underlying problem structure but use only the current LP relaxation and the integrality conditions. See also
2607 * "When should I implement a constraint handler, when should I implement a separator?" on \ref FAQ.
2609 * A complete list of all separators contained in this release can be found \ref SEPARATORS "here".
2612 * Take the separator for the class of Gomory mixed integer inequalities (src/scip/sepa_gomory.c) as an example.
2613 * As all other default plugins, it is written in C. C++ users can easily adapt the code by using the scip::ObjSepa wrapper
2614 * base class and implement the scip_...() virtual methods instead of the SCIP_DECL_SEPA... callback methods.
2616 * Additional documentation for the callback methods of a separator, in particular for the input parameters,
2620 * -# Copy the template files src/scip/sepa_xyz.c and src/scip/sepa_xyz.h into files "sepa_myseparator.c"
2623 * Make sure to adjust your Makefile such that these files are compiled and linked to your project.
2624 * -# Use SCIPincludeSepaMyseparator() in order to include the separator into your SCIP instance,
2626 * -# Open the new files with a text editor and replace all occurrences of "xyz" by "myseparator".
2631 * -# Implement the additional callback methods (see \ref SEPA_ADDITIONALCALLBACKS). This is optional.
2638 * In the C++ wrapper class, you have to provide the separator properties by calling the constructor
2644 * Additionally, if you are searching for a separator with SCIPfindSepa(), this name is looked up.
2651 * In each separation round during the price-and-cut loop of the subproblem processing or the separation loop
2652 * of the primal solution separation, the separators and separation methods of the constraint handlers are called in
2653 * a predefined order, which is given by the priorities of the separators and the separation priorities
2655 * First, the separators with non-negative priority are called in the order of decreasing priority.
2656 * Next, the separation methods of the constraint handlers are called in the order of decreasing separation
2658 * Finally, the separators with negative priority are called in the order of decreasing priority. An easy way to list the
2659 * priorities of all separators and constraint handlers is to type "display separators" and "display conshdlrs" in
2662 * The priority of the separator should be set according to the complexity of the cut separation algorithm and the
2663 * impact of the resulting cuts: separators that provide fast algorithms that usually have a high impact (i.e., cut off
2668 * The frequency defines the depth levels at which the separation methods \ref SEPAEXECLP and \ref SEPAEXECSOL are called.
2669 * For example, a frequency of 7 means, that the separation callback is executed for subproblems that are in depth
2670 * 0, 7, 14, ... of the branching tree. A frequency of 0 means, that the separation method is only called at the root node.
2673 * The frequency can be adjusted by the user. This property of the separator only defines the default value of the frequency.
2674 * If you want to have a more flexible control of when to execute the separation algorithm, you have to assign
2675 * a frequency of 1 and implement a check at the beginning of your separation methods whether you really want to execute
2679 * \par SEPA_MAXBOUNDDIST: the default maximal relative distance from the current node's dual bound to primal bound compared to best node's dual bound for applying separation.
2680 * At the current branch-and-bound node, the relative distance from its dual bound (local dual bound)
2681 * to the primal bound compared to the best node's dual bound (global dual bound) is considered. The separation method
2682 * of the separator will only be applied at the current node if this relative distance does not exceed SEPA_MAXBOUNDDIST.
2684 * For example, if the global dual bound is 50 and the primal bound is 60, SEPA_MAXBOUNDDIST = 0.25 means that separation
2685 * is only applied if the current node's dual bound is in the first quarter of the interval [50,60], i.e., if it is less
2688 * In particular, the values 0.0 and 1.0 mean that separation is applied at the current best node only or at all
2689 * nodes, respectively. Since separation seems to be most important to apply at nodes that define to the global
2692 * Obviously, at the root node the local dual bound is equal to the global dual bound and thus, the separator is called
2696 * Some heuristics and separators solve MIPs or SAT problems and use a secondary SCIP instance. Examples are
2697 * Large Neighborhood Search heuristics such as RINS and Local Branching or the CGMIP separator. To avoid recursion,
2698 * these plugins usually deactivate all other plugins that solve MIPs. If a separator uses a secondary SCIP instance,
2699 * this parameter has to be TRUE and it is recommended to call SCIPsetSubscipsOff() for the secondary SCIP instance.
2701 * \par SEPA_DELAY: the default for whether the separation method should be delayed, if other separators or constraint handlers found cuts.
2702 * If the separator's separation method is marked to be delayed, it is only executed after no other separator
2704 * If the separation method of the separator is very expensive, you may want to mark it to be delayed until all cheap
2709 * Below the header "Data structures" you can find a struct which is called "struct SCIP_SepaData".
2710 * In this data structure, you can store the data of your separator. For example, you should store the adjustable
2711 * parameters of the separator in this data structure. In a separator, user parameters for the maximal number of
2712 * separation rounds per node and for the maximal number of cuts separated per separation round might be useful.
2719 * At the bottom of "sepa_myseparator.c", you can find the interface method SCIPincludeSepaMyseparator(),
2725 * It is responsible for notifying SCIP of the presence of the separator. For this, you can either call SCIPincludeSepa(),
2726 * or SCIPincludeSepaBasic() since SCIP version 3.0. In the latter variant, \ref SEPA_ADDITIONALCALLBACKS "additional callbacks"
2727 * must be added via setter functions as, e.g., SCIPsetSepaCopy(). We recommend this latter variant because
2728 * it is more stable towards future SCIP versions which might have more callbacks, whereas source code using the first
2729 * variant must be manually adjusted with every SCIP release containing new callbacks for separators in order to compile.
2739 * You may also add user parameters for your separator, see \ref PARAM for how to add user parameters and
2745 * The fundamental callback methods of the plugins are the ones that have to be implemented in order to obtain
2747 * They are passed together with the separator itself to SCIP using SCIPincludeSepa() or SCIPincludeSepaBasic(),
2750 * Separator plugins have two callbacks, @ref SEPAEXECLP and @ref SEPAEXECSOL, of which at least one must be implemented.
2757 * The SEPAEXECLP callback is executed during the price-and-cut loop of the subproblem processing.
2758 * It should try to generate general purpose cutting planes in order to separate the current LP solution.
2761 * Usually, the callback searches and produces cuts, that are added with a call to SCIPaddCut().
2763 * In addition to LP rows, the callback may also produce domain reductions or add additional constraints.
2765 * Overall, the SEPAEXECLP callback has the following options, which is indicated by the possible return values of
2767 * - detecting that the node is infeasible in the variable's bounds and can be cut off (result SCIP_CUTOFF)
2771 * - stating that the separator searched, but did not find domain reductions, cutting planes, or cut constraints
2775 * - stating that a new separation round should be started without calling the remaining separator methods (result SCIP_NEWROUND)
2779 * The SEPAEXECSOL callback is executed during the separation loop on arbitrary primal solutions.
2780 * It should try to generate general purpose cutting planes in order to separate the given primal solution.
2781 * The method is not called in the LP solution loop, which means that there is no valid LP solution.
2783 * In the standard SCIP environment, the SEPAEXECSOL callback is not used because only LP solutions are
2784 * separated. The SEPAEXECSOL callback provides means to support external relaxation handlers like semidefinite
2785 * relaxations that want to separate an intermediate primal solution vector. Thus, if you do not want to support
2788 * Usually, the callback searches and produces cuts, that are added with a call to SCIPaddCut().
2790 * In addition to LP rows, the callback may also produce domain reductions or add other constraints.
2792 * Overall, the SEPAEXECSOL callback has the following options, which is indicated by the possible return values of
2794 * - detecting that the node is infeasible in the variable's bounds and can be cut off (result SCIP_CUTOFF)
2798 * - stating that the separator searched, but did not find domain reductions, cutting planes, or cut constraints
2802 * - stating that a new separation round should be started without calling the remaining separator methods (result SCIP_NEWROUND)
2807 * The additional callback methods do not need to be implemented in every case. However, some of them have to be
2808 * implemented for most applications, they can be used, for example, to initialize and free private data.
2809 * Additional callbacks can either be passed directly with SCIPincludeSepa() to SCIP or via specific
2810 * <b>setter functions</b> after a call of SCIPincludeSepaBasic(), see also @ref SEPA_INTERFACE.
2814 * If you are using separator data (see \ref SEPA_DATA and \ref SEPA_INTERFACE), you have to implement this method
2856 * In this method, the separator should free all resources that have been allocated for the solving process in SEPAINIT.
2860 * The SEPAINITSOL callback is executed when the presolving is finished and the branch-and-bound process is about to
2865 * The SEPAEXITSOL callback is executed before the branch-and-bound process is freed. The separator should use this call
2866 * to clean up its branch-and-bound data, in particular to release all LP rows that it has created or captured.
2869 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
2872 * Propagators are used to tighten the domains of the variables. Like for cutting planes, there are two different types
2873 * of domain propagations. Constraint based (primal) domain propagation algorithms are part of the corresponding
2874 * constraint handlers, see \ref CONSPROP. In contrast, domain propagators usually provide dual propagations, i.e.,
2875 * propagations that can be applied using the objective function and the current best known primal solution. This
2878 * A complete list of all propagators contained in this release can be found \ref PROPAGATORS "here".
2880 * We now explain how users can add their own propagators. Take the pseudo objective function propagator
2881 * (src/scip/prop_pseudoobj.c) as an example. As all other default plugins, it is written in C. C++ users can easily
2882 * adapt the code by using the scip::ObjProp wrapper base class and implement the @c scip_...() virtual methods instead
2885 * Additional documentation for the callback methods of a propagator can be found in the file type_prop.h.
2888 * -# Copy the template files src/scip/prop_xyz.c and src/scip/prop_xyz.h into files named "prop_mypropagator.c"
2891 * Make sure to adjust your Makefile such that these files are compiled and linked to your project.
2892 * -# Use SCIPincludePropMypropagator() in order to include the propagator into your SCIP instance,
2894 * -# Open the new files with a text editor and replace all occurrences of "xyz" by "mypropagator".
2899 * -# Implement the additional callback methods (see \ref PROP_ADDITIONALCALLBACKS). This is optional.
2903 * At the top of the new file "prop_mypropagator.c" you can find the propagator properties. These are given as compiler
2906 * In the C++ wrapper class, you have to provide the propagator properties by calling the constructor of the
2907 * abstract base class scip::ObjProp from within your constructor. The properties you have the following meaning:
2912 * This name is used in the interactive shell to address the propagator. Additionally, if you are searching for a
2913 * propagator with SCIPfindProp(), this name is searched for. Names have to be unique: no two propagators may have the
2920 * In each propagation round, the propagators and propagation methods of the constraint handlers are called in a
2921 * predefined order, which is given by the priorities of the propagators and the check priorities of the constraint
2922 * handlers. First, the propagators with non-negative priority are called in order of decreasing priority. Next, the
2923 * propagation methods of the different constraint handlers are called in order of decreasing check priority. Finally,
2924 * the propagators with negative priority are called in order of decreasing priority. \n The priority of the
2925 * propagators should be set according to the complexity of the propagation algorithm and the impact of the domain
2926 * propagations: propagators providing fast algorithms that usually have a high impact (i.e., tighten many bounds)
2930 * The frequency defines the depth levels at which the propagation method \ref PROPEXEC is called. For example, a
2931 * frequency of 7 means, that the propagation callback is executed for subproblems that are in depth 0, 7, 14, ... of
2932 * the branching tree. A frequency of 0 means that propagation is only applied in preprocessing and at the root node. A
2935 * The frequency can be adjusted by the user. This property of the propagator only defines the default value of the
2937 * <b>Note:</b> If you want to have a more flexible control of when to execute the propagation algorithm, you have to
2938 * assign a frequency of 1 and implement a check at the beginning of your propagation algorithm whether you really want
2939 * to execute the domain propagation or not. If you do not want to execute it, set the result code to SCIP_DIDNOTRUN.
2941 * \par PROP_DELAY: the default for whether the propagation method should be delayed, if other propagators or constraint handlers found domain reductions.
2942 * If the propagator's propagation method is marked to be delayed, it is only executed after no other propagator or
2943 * constraint handler found a domain reduction in the current iteration of the domain propagation loop. If the
2944 * propagation method of the propagator is very expensive, you may want to mark it to be delayed until all cheap
2950 * Possible values are defined in type_timing.h and can be concatenated, e.g., as in SCIP_PROPTIMING_ALWAYS.
2958 * This attribute is analogous to the PROP_PRIORITY flag, but deals with the preprocessing method of the presolver.
2960 * \par PROP_PRESOL_MAXROUNDS: the default maximal number of presolving rounds the propagator participates in.
2962 * If enough changes have been applied to the model, an additional preprocessing round is performed.
2963 * The MAXROUNDS parameter of a propagator denotes the maximal number of preprocessing rounds, the propagator
2968 * \par PROP_PRESOL_DELAY: the default for whether the presolving method should be delayed, if other propagators or constraint handlers found presolving reductions.
2969 * This property is analogous to the PROP_DELAY flag, but deals with the preprocessing method of the propagator.
2973 * Below the title "Data structures" you can find a struct called <code>struct SCIP_PropData</code>. In this data
2974 * structure, you can store the data of your propagator. For example, you should store the adjustable parameters of the
2975 * propagator in this data structure. If you are using C++, you can add propagator data as object variables to your
2983 * At the bottom of "prop_mypropagator.c", you can find the interface method SCIPincludeSepaMypropagator(),
2985 * SCIPincludePropMypropagator() is called by the user, if (s)he wants to include the propagator,
2989 * It is responsible for notifying SCIP of the presence of the propagator. For this, you can either call SCIPincludeProp(),
2990 * or SCIPincludePropBasic() since SCIP version 3.0. In the latter variant, \ref PROP_ADDITIONALCALLBACKS "additional callbacks"
2991 * must be added via setter functions as, e.g., SCIPsetPropCopy(). We recommend this latter variant because
2992 * it is more stable towards future SCIP versions which might have more callbacks, whereas source code using the first
2993 * variant must be manually adjusted with every SCIP release containing new callbacks for separators in order to compile.
2996 * If you are using propagator data, you have to allocate the memory for the data at this point. You can do this by
3003 * You may also add user parameters for your propagator, see the method SCIPincludePropPseudoobj() in
3009 * The fundamental callback methods of the plugins are the ones that have to be implemented in order to obtain
3011 * They are passed together with the propagator itself to SCIP using SCIPincludeProp() or SCIPincludePropBasic(),
3015 * method. This method has to be implemented for every propagator; the other callback methods are optional. In the
3016 * C++ wrapper class scip::ObjProp, the scip_exec() method (which corresponds to the \ref PROPEXEC
3024 * The PROPEXEC callback is called during presolving and during the subproblem processing. It should perform the actual
3025 * domain propagation, which means that it should tighten the variables' bounds. The technique of domain propagation,
3026 * which is the main workhorse of constraint programming, is called "node preprocessing" in the Integer Programming
3030 * - detecting that the node is infeasible in the variables' bounds and can be cut off (result SCIP_CUTOFF)
3032 * - stating that the propagator searched, but did not find domain reductions, cutting planes, or cut constraints
3041 * The additional callback methods do not need to be implemented in every case. However, some of them have to be
3042 * implemented for most applications, they can be used, for example, to initialize and free private data.
3043 * Additional callbacks can either be passed directly with SCIPincludeProp() to SCIP or via specific
3044 * <b>setter functions</b> after a call of SCIPincludePropBasic(), see also @ref PROP_INTERFACE.
3048 * If the propagator wants to support \ref CONF "conflict analysis", it has to supply the PROPRESPROP method. It also should call
3049 * SCIPinferVarLbProp() or SCIPinferVarUbProp() in the domain propagation instead of SCIPchgVarLb() or SCIPchgVarUb() in
3050 * order to deduce bound changes on variables. In the SCIPinferVarLbProp() and SCIPinferVarUbProp() calls, the
3051 * propagator provides a pointer to itself and an integer value "inferinfo" that can be arbitrarily chosen.
3053 * The propagation conflict resolving method PROPRESPROP must then be implemented to provide the "reasons" for the bound
3054 * changes, i.e., the bounds of variables at the time of the propagation, which forced the propagator to set the
3055 * conflict variable's bound to its current value. It can use the "inferinfo" tag to identify its own propagation rule
3056 * and thus identify the "reason" bounds. The bounds that form the reason of the assignment must then be provided by
3057 * calls to SCIPaddConflictLb() and SCIPaddConflictUb() in the propagation conflict resolving method.
3059 * See the description of the propagation conflict resolving method \ref CONSRESPROP of constraint handlers for
3062 * Omitting the PROPRESPROP callback circumvents the implementation of the usually rather complex conflict resolving method.
3064 * will make the conflict analysis less effective. We suggest to first omit the conflict resolving method and check how
3065 * effective the propagation method is. If it produces a lot of propagations for your application, you definitely should
3071 * If you are using propagator data, you have to implement this method in order to free the propagator data.
3089 * If you have allocated memory for fields in your propagator data, remember to free this memory
3096 * The PROPINIT callback is executed after the problem is transformed. The propagator may, e.g., use this call to
3111 * In this method, the propagator should free all resources that have been allocated for the solving process in PROPINIT.
3115 * The PROPINITPRE callback is executed before the preprocessing is started, even if presolving is turned off.
3116 * The propagator may use this call to initialize its presolving data before the presolving process begins.
3120 * The PROPEXITPRE callback is executed after the preprocessing has been finished, even if presolving is turned off.
3126 * The PROPINITSOL callback is executed when the presolving is finished and the branch-and-bound process is about to
3140 * To inform SCIP that the presolving method found a reduction the result pointer has to be set in a proper way.
3143 * - SCIP_UNBOUNDED : at least one variable is not bounded by any constraint in objective direction
3144 * - SCIP_CUTOFF : at least one domain reduction that renders the problem infeasible has been found
3152 * PROP_PRESOL_PRIORITY, PROP_PRESOL_MAXROUNDS, and PROP_PRESOL_DELAY, which influence the behaviour of SCIP
3157 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
3160 * Branching rules are used to split the problem at the current node into smaller subproblems. Branching rules can be called at three
3163 * - the LP solution of the current problem is fractional. In this case, the integrality constraint handler calls the
3165 * - the list of external branching candidates is not empty. This will only be the case if branching candidates were added
3166 * by a user's \ref RELAX "relaxation handler" or \ref CONS "constraint handler" plugin, calling SCIPaddExternBranchCand().
3168 * - if an integral solution violates one or more constraints and this infeasibility could not be resolved in the callback methods
3169 * \ref CONSENFOLP and \ref CONSENFOPS of the corresponding constraint handlers. In this case, the \ref BRANCHEXECPS method will be called. This is the
3170 * standard case, if you use SCIP as a pure CP or SAT solver. If the LP or any other type of relaxation is used, then
3173 * The idea of branching rules is to take a global view on the problem. In contrast, branching paradigms which are
3174 * specific to one type of constraint are best implemented within the enforcement callbacks of your constraint handler.
3175 * See, e.g., the constraint specific branching rules provided by the constraint handlers for special ordered sets
3178 * All branching rules that come with the default distribution of SCIP create two subproblems by splitting a single
3179 * variable's domain. It is, however, fully supported to implement much more general branching schemes, for example by
3180 * creating more than two subproblems, or by adding additional constraints to the subproblems instead of tightening the
3183 * A complete list of all branching rules contained in this release can be found \ref BRANCHINGRULES "here".
3185 * We now explain how users can add their own branching rules. Take the most infeasible LP branching rule
3186 * (src/scip/branch_mostinf.c) as an example. As all other default plugins, it is written in C. C++ users can easily
3187 * adapt the code by using the scip::ObjBranchrule wrapper base class and implement the scip_...() virtual methods instead of
3190 * Additional documentation for the callback methods of a branching rule can be found in the file type_branch.h.
3196 * Make sure to adjust your Makefile such that these files are compiled and linked to your project.
3197 * -# Use SCIPincludeBranchruleMybranchingrule() in order to include the branching rule into your SCIP instance,
3199 * -# Open the new files with a text editor and replace all occurrences of "xyz" by "mybranchingrule".
3204 * -# Implement the additional callback methods (see \ref BRANCHRULE_ADDITIONALCALLBACKS). This is optional.
3209 * At the top of the new file "branch_mybranchingrule.c" you can find the branching rule properties.
3211 * In the C++ wrapper class, you have to provide the branching rule properties by calling the constructor
3217 * Additionally, if you are searching for a branching rule with SCIPfindBranchrule(), this name is looked up.
3224 * In the subproblem processing, the branching rules are called in decreasing order of their priority until
3225 * one succeeded to branch. Since most branching rules are able to generate a branching in all situations,
3227 * BRANCHRULE_MAXBOUNDDIST settings, however, interesting strategies can be easily employed. For example,
3228 * the user can set the priority of the "full strong branching" strategy to the highest value and assign the
3229 * second highest value to the "reliable pseudo cost" rule. If (s)he also sets the maximal depth for the
3230 * "full strong branching" to 5, in the top 5 depth levels of the search tree the "full strong branching" is
3233 * Note that the BRANCHRULE_PRIORITY property only specifies the default value of the priority. The user can
3236 * \par BRANCHRULE_MAXDEPTH: the default value for the maximal depth level of the branching rule.
3237 * This parameter denotes the maximal depth level in the branch-and-bound tree up to which the branching method of the
3240 * Note that this property only specifies the default value. The user can change this value arbitrarily.
3242 * \par BRANCHRULE_MAXBOUNDDIST: the default value for the maximal relative distance from current node's dual bound to primal bound compared to best node's dual bound for applying branching.
3243 * At the current branch-and-bound node, the relative distance from its dual bound (local dual bound)
3244 * to the primal bound compared to the best node's dual bound (global dual bound) is considered. The branching method of
3245 * the branching rule will only be applied at the node if this relative distance does not exceed BRANCHRULE_MAXBOUNDDIST.
3247 * For example, if the global dual bound is 50 and the primal bound is 60, BRANCHRULE_MAXBOUNDDIST = 0.25 means that
3248 * branching is only applied if the current node's dual bound is in the first quarter of the interval [50,60], i.e., if it
3249 * is less than or equal to 52.5. In particular, the values 0.0 and 1.0 mean that the branching rule is applied at the
3252 * Note that the BRANCHRULE_MAXBOUNDDIST property only specifies the default value of the maximal bound distance.
3258 * Below the header "Data structures" you can find a struct which is called "struct SCIP_BranchruleData".
3259 * In this data structure, you can store the data of your branching rule. For example, you should store the adjustable
3261 * If you are using C++, you can add branching rule data as usual as object variables to your class.
3268 * At the bottom of "branch_mybranchingrule.c", you can find the interface method SCIPincludeBranchruleMybranchingrule(),
3270 * SCIPincludeBranchruleMybranchingrule() is called by the user, if (s)he wants to include the branching rule,
3274 * It is responsible for notifying SCIP of the presence of the branching rule. For this, you can either call
3276 * or SCIPincludeBranchruleBasic() since SCIP version 3.0. In the latter variant, \ref BRANCHRULE_ADDITIONALCALLBACKS "additional callbacks"
3277 * must be added via setter functions as, e.g., SCIPsetBranchruleCopy(). We recommend this latter variant because
3278 * it is more stable towards future SCIP versions which might have more callbacks, whereas source code using the first
3279 * variant must be manually adjusted with every SCIP release containing new callbacks for branchrule in order to compile.
3282 * If you are using branching rule data, you have to allocate the memory for the data at this point.
3289 * You may also add user parameters for your branching rule, see the method SCIPincludeBranchruleRelpscost() in
3295 * Branching rules do not have any fundamental callback methods, i.e., all callback methods are optional.
3296 * In most cases, however, you want to implement the \ref BRANCHEXECLP method and sometimes the \ref BRANCHEXECPS method.
3301 * The additional callback methods do not need to be implemented in every case. However, some of them have to be
3302 * implemented for most applications, they can be used, for example, to initialize and free private data.
3303 * Additional callbacks can either be passed directly with SCIPincludeBranchrule() to SCIP or via specific
3304 * <b>setter functions</b> after a call of SCIPincludeBranchruleBasic(), see also @ref BRANCHRULE_INTERFACE.
3313 * The BRANCHEXECLP callback is executed during node processing if a fractional LP solution is available. It should
3314 * split the current problem into smaller subproblems. Usually, the branching is done in a way such that the current
3315 * fractional LP solution is no longer feasible in the relaxation of the subproblems. It is, however, possible to
3316 * create a child node for which the fractional LP solution is still feasible in the relaxation, for example, by
3317 * branching on a variable with integral LP value. In every case, you have to make sure that each subproblem is a
3318 * proper restriction of the current problem. Otherwise, you risk to produce an infinite path in the search tree.
3320 * The user gains access to the branching candidates, i.e., to the fractional variables, and their LP solution values by
3321 * calling the method SCIPgetLPBranchCands(). Furthermore, SCIP provides two methods for performing the actual
3324 * Given an integral variable \f$x\f$ with fractional LP solution value \f$x^*\f$, the method SCIPbranchVar() creates
3325 * two child nodes; one contains the bound \f$x \le \lfloor x^* \rfloor\f$ and the other one contains the bound \f$x \ge
3326 * \lceil x^* \rceil\f$, see the BRANCHEXECLP callback in src/scip/branch_mostinf.c for an example. In addition, if a
3327 * proven lower objective bound of a created child node is known, like after strong branching has been applied, the user
3328 * may call the method SCIPupdateNodeLowerbound() in order to update the child node's lower bound.
3334 * The BRANCHEXECEXT callback is executed during node processing if no LP solution is available and the list of
3335 * external branching candidates is not empty. It should split the current problem into smaller subproblems. If you
3336 * do not use relaxation handlers or constraints handlers that provide external branching candidates, you do not need to
3339 * In contrast to the LP branching candidates and the pseudo branching candidates, the list of external branching
3340 * candidates will not be generated automatically. The user has to add all variables to the list by calling
3341 * SCIPaddExternBranchCand() for each of them. Usually, this will happen in the execution method of a relaxation handler or in the
3344 * The user gains access to these branching candidates by calling the method SCIPgetExternBranchCands(). Furthermore,
3345 * SCIP provides two methods for performing the actual branching with a given solution value, namely SCIPbranchVarVal()
3346 * and SCIPcreateChild(). SCIPbranchVarVal() allows users to specify the branching point for a variable in contrast to
3349 * This paragraph contains additional information regarding how the method SCIPbranchVarVal() works. For external branching candidates,
3351 * - Given a continuous variable \f$x\f$ with solution value \f$x^*\f$, the method SCIPbranchVarVal() creates
3352 * two child nodes; one contains the bound \f$x \le x^* \f$ and the other one contains the bound \f$x \ge x^* \f$.
3354 * SCIPbranchVarVal() creates two child nodes; one contains the bound \f$x \le \lfloor x^* \rfloor\f$ and the other
3356 * - Given an integer variable \f$x\f$ with integral solution value \f$x^*\f$, the method SCIPbranchVarVal()
3357 * creates three child nodes; one contains the bound \f$x \le x^* -1\f$, one contains the bound \f$x \ge x^* +1\f$,
3360 * See the BRANCHEXECEXT callback in src/scip/branch_random.c for an example. In addition, if a proven lower bound of a
3361 * created child node is known the user may call the method SCIPupdateNodeLowerbound() in order to update the child
3368 * The BRANCHEXECPS callback is executed during node processing if no LP solution is available and at least one of the
3369 * integer variables is not yet fixed. It should split the current problem into smaller subproblems. PS stands for
3370 * pseudo solution which is the vector of all variables set to their locally best (w.r.t. the objective function)
3373 * The user gains access to the branching candidates, i.e., to the non-fixed integer variables, by calling the method
3374 * SCIPgetPseudoBranchCands(). Furthermore, SCIP provides two methods for performing the actual branching, namely
3377 * Given an integer variable \f$x\f$ with bounds \f$[l,u]\f$ and not having solved the LP, the method SCIPbranchVar()
3379 * - If both bounds are finite, then the two children will contain the domain reductions \f$x \le x^*\f$, and \f$x \ge
3380 * x^*+1\f$ with \f$x^* = \lfloor \frac{l + u}{2}\rfloor\f$. The current pseudo solution will remain feasible in one
3382 * - If only one of the bounds is finite, the variable will be fixed to that bound in one of the child nodes. In the
3384 * - If both bounds are infinite, three children will be created: \f$x \le 1\f$, \f$x \ge 1\f$, and \f$x = 0\f$.
3387 * See the BRANCHEXECPS callback in src/scip/branch_random.c for an example. In addition, if a proven lower bound of a
3388 * created child node is known, the user may call the method SCIPupdateNodeLowerbound() in order to update the child
3395 * In order to apply more general branching schemes, one should use the method SCIPcreateChild().
3396 * After having created a child node, the additional restrictions of the child node have to be added with calls to
3399 * In the method SCIPcreateChild(), the branching rule has to assign two values to the new nodes: a node selection
3400 * priority for each node and an estimate for the objective value of the best feasible solution contained in the subtree
3401 * after applying the branching. If the method SCIPbranchVar() is used, these values are automatically assigned. For
3402 * variable based branching schemes, one might use the methods SCIPcalcNodeselPriority() and the method
3405 * In some cases, the branching rule can tighten the current subproblem instead of producing a branching. For example,
3406 * strong branching might have proven that rounding up a variable would lead to an infeasible LP relaxation and thus,
3407 * the variable must be rounded down. Therefore, the BRANCHEXECLP, BRANCHEXECPS and BRANCHEXECREL callbacks may also
3412 * - adding an additional constraint (e.g. a conflict constraint) (result SCIP_CONSADDED; note that this action
3414 * - reducing the domain of a variable such that the current LP solution becomes infeasible (result SCIP_REDUCEDDOM)
3418 * Only the BRANCHEXECLP callback has the possibility to add a cutting plane to the LP (result SCIP_SEPARATED).
3422 * If you are using branching rule data, you have to implement this method in order to free the branching rule data.
3440 * If you have allocated memory for fields in your branching rule data, remember to free this memory
3462 * In this method, the branching rule should free all resources that have been allocated for the solving process in
3467 * The BRANCHINITSOL callback is executed when the presolving is finished and the branch-and-bound process is about to
3477 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
3480 * Node selectors are used to decide which of the leaves in the current branching tree is selected as next subproblem
3481 * to be processed. The ordering relation of the tree's leaves for storing them in the leaf priority queue is also
3484 * A complete list of all node selectors contained in this release can be found \ref NODESELECTORS "here".
3488 * As all other default plugins, it is written in C. C++ users can easily adapt the code by using the scip::ObjNodesel wrapper
3489 * base class and implement the scip_...() virtual methods instead of the SCIP_DECL_NODESEL... callback methods.
3491 * Additional documentation for the callback methods of a node selector can be found in the file type_nodesel.h.
3494 * -# Copy the template files src/scip/nodesel_xyz.c and src/scip/nodesel_xyz.h into files named "nodesel_mynodeselector.c"
3497 * Make sure to adjust your Makefile such that these files are compiled and linked to your project.
3498 * -# Use SCIPincludeNodeselMynodeselector() in oder to include the node selector into your SCIP instance,
3500 * -# Open the new files with a text editor and replace all occurrences of "xyz" by "mynodeselector".
3505 * -# Implement the additional callback methods (see \ref NODESEL_ADDITIONALCALLBACKS). This is optional.
3510 * At the top of the new file "nodesel_mynodeselector.c" you can find the node selector properties.
3512 * In the C++ wrapper class, you have to provide the node selector properties by calling the constructor
3518 * Additionally, if you are searching for a node selector with SCIPfindNodesel(), this name is looked up.
3525 * The first step of each iteration of the main solving loop is the selection of the next subproblem to be processed.
3526 * The node selector of highest priority (the active node selector) is called to do this selection.
3527 * In particular, if you implemented your own node selector plugin which you want to be applied, you should choose a priority
3529 * Note that SCIP has two different operation modes: the standard mode and the memory saving mode. If the memory
3530 * limit - given as a parameter by the user - is almost reached, SCIP switches from the standard mode to the memory saving
3531 * mode in which different priorities for the node selectors are applied. NODESEL_STDPRIORITY is the priority of the
3534 * Note that this property only defines the default value of the priority. The user may change this value arbitrarily by
3537 * \par NODESEL_MEMSAVEPRIORITY: the default priority of the node selector in the memory saving mode.
3538 * The priority NODESEL_MEMSAVEPRIORITY of the node selector has the same meaning as the priority NODESEL_STDPRIORITY, but
3540 * Usually, you want the best performing node selector, for example best estimate search, to have maximal
3541 * standard priority, while you want a node selector which tends to keep the growth of the search tree limited, for example
3544 * Note that this property only defines the default value of the priority. The user may change this value arbitrarily by
3550 * Below the header "Data structures" you can find a struct which is called "struct SCIP_NodeselData".
3551 * In this data structure, you can store the data of your node selector. For example, you should store the adjustable
3553 * If you are using C++, you can add node selector data as usual as object variables to your class.
3560 * At the bottom of "nodesel_mynodeselector.c", you can find the interface method SCIPincludeNodeselMynodeselector(),
3562 * SCIPincludeNodeselMynodeselector() is called by the user, if (s)he wants to include the node selector,
3566 * It is responsible for notifying SCIP of the presence of the node selector. For this, you can either call
3568 * or SCIPincludeNodeselBasic() since SCIP version 3.0. In the latter variant, \ref NODESEL_ADDITIONALCALLBACKS "additional callbacks"
3569 * must be added via setter functions as, e.g., SCIPsetNodeselCopy(). We recommend this latter variant because
3570 * it is more stable towards future SCIP versions which might have more callbacks, whereas source code using the first
3571 * variant must be manually adjusted with every SCIP release containing new callbacks for node selectors in order to compile.
3574 * If you are using node selector data, you have to allocate the memory for the data at this point.
3581 * You may also add user parameters for your node selector, see the method SCIPincludeNodeselRestartdfs() in
3587 * The fundamental callback methods of the plugins are the ones that have to be implemented in order to obtain
3589 * They are passed together with the node selector itself to SCIP using SCIPincludeNodesel() or SCIPincludeNodeselBasic(),
3592 * Node selector plugins have two fundamental callback methods, namely the NODESELSELECT method and the NODESELCOMP method.
3593 * These methods have to be implemented for every node selector; the other callback methods are optional.
3594 * They implement the two requirements every node selector has to fulfill: Selecting a node from the queue to be processed
3595 * next and, given two nodes, deciding which of both is favored by the node selector's selection rule. The first
3596 * task is implemented in the NODESELSELECT callback, the second one in the NODESELCOMP callback.
3597 * In the C++ wrapper class scip::ObjNodesel, the scip_select() method and the scip_comp() method (which correspond to the
3598 * NODESELSELECT callback and the NODESELCOMP callback, respectively) are virtual abstract member functions.
3599 * You have to implement them in order to be able to construct an object of your node selector class.
3605 * The NODESELSELECT callback is the first method called in each iteration in the main solving loop. It should decide
3606 * which of the leaves in the current branching tree is selected as the next subproblem to be processed.
3607 * It can arbitrarily decide between all leaves stored in the tree, but for performance reasons,
3608 * the current node's children and siblings are often treated different from the remaining leaves.
3609 * This is mainly due to the warm start capabilities of the simplex algorithm and the expectation that the bases of
3612 * have a large impact on the solver's performance, because it influences the finding of feasible solutions and the
3615 * Besides the ranking of the node selector, every node gets assigned a node selection priority by the branching rule
3616 * that created the node. See the \ref BRANCHEXECLP and \ref BRANCHEXECPS callbacks of the branching rules for details.
3617 * For example, the node where the branching went in the same way as the deviation from the branching variable's
3618 * root solution could be assigned a higher priority than the node where the branching went in the opposite direction.
3621 * - SCIPgetPrioChild() returns the child of the current node with the largest node selection priority, as assigned by the
3623 * If no child is available (for example, because the current node was pruned), a NULL pointer is returned.
3624 * - SCIPgetBestChild() returns the best child of the current node with respect to the node selector's ordering relation as
3625 * defined by the \ref NODESELCOMP callback. If no child is available, a NULL pointer is returned.
3626 * - SCIPgetPrioSibling() returns the sibling of the current node with the largest node selection priority.
3627 * If no sibling is available (for example, because all siblings of the current node have already been processed), a NULL
3629 * Note that in binary branching every node has at most one sibling, but since SCIP supports arbitrary branching rules,
3631 * - SCIPgetBestSibling() returns the best sibling of the current node with respect to the node selector's ordering relation
3632 * as defined by the \ref NODESELCOMP callback. If no sibling is available, a NULL pointer is returned.
3633 * - SCIPgetBestNode() returns the best leaf from the tree (children, siblings, or other leaves) with respect to the node
3634 * selector's ordering relation as defined by the \ref NODESELCOMP callback. If no open leaf exists, a NULL pointer is
3635 * returned. In this case, the optimization is finished, and the node selector should return a NULL pointer as 'selnode'.
3636 * - SCIPgetBestboundNode() returns a leaf from the tree (children, siblings, or other leaves) with the smallest lower (dual)
3637 * objective bound. If the queue is empty, a NULL pointer is returned. In this case, the optimization is finished, and the
3643 * The NODESELCOMP callback is called to compare two leaves of the current branching tree (say node 1 and node 2)
3653 * The additional callback methods do not need to be implemented in every case. However, some of them have to be
3654 * implemented for most applications, they can be used, for example, to initialize and free private data.
3655 * Additional callbacks can either be passed directly with SCIPincludeNodesel() to SCIP or via specific
3656 * <b>setter functions</b> after a call of SCIPincludeNodeselBasic(), see also @ref NODESEL_INTERFACE.
3660 * If you are using node selector data, you have to implement this method in order to free the node selector data.
3678 * If you have allocated memory for fields in your node selector data, remember to free this memory
3700 * In this method, the node selector should free all resources that have been allocated for the solving process
3705 * The NODESELINITSOL callback is executed when the presolving is finished and the branch-and-bound process is about to
3716 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
3719 * Feasible solutions can be found in two different ways during the traversal of the branch-and-bound tree. On one
3720 * hand, the solution of a node's relaxation may be feasible with respect to the constraints (including the integrality).
3723 * A complete list of all primal heuristics contained in this release can be found \ref PRIMALHEURISTICS "here".
3726 * Take the simple and fast LP rounding heuristic (src/scip/heur_simplerounding.c) as an example.
3727 * The idea of simple rounding is to iterate over all fractional variables of an LP solution and round them down,
3728 * if the variables appears only with nonnegative coefficients in the system Ax <= b and round them up if
3730 * If one of both conditions applies for each of the fractional variables, this will give a feasible solution.
3731 * As all other default plugins, it is written in C. C++ users can easily adapt the code by using the scip::ObjHeur wrapper
3732 * base class and implement the scip_...() virtual methods instead of the SCIP_DECL_HEUR... callback methods.
3734 * Additional documentation for the callback methods of a primal heuristic can be found in the file type_heur.h.
3737 * -# Copy the template files src/scip/heur_xyz.c and src/scip/heur_xyz.h into files named "heur_myheuristic.c"
3740 * Make sure to adjust your Makefile such that these files are compiled and linked to your project.
3741 * -# Use SCIPincludeHeurMyheuristic() in order to include the heuristic into your SCIP instance,
3743 * -# Open the new files with a text editor and replace all occurrences of "xyz" by "myheuristic".
3748 * -# Implement the additional callback methods (see \ref HEUR_ADDITIONALCALLBACKS). This is optional.
3753 * At the top of the new file "heur_myheuristic.c" you can find the primal heuristic properties.
3755 * In the C++ wrapper class, you have to provide the primal heuristic properties by calling the constructor
3757 * Of course, all of them are of relevant, but the most important ones for controlling the performance
3763 * Additionally, if you are searching for a primal heuristic with SCIPfindHeur(), this name is looked up.
3767 * This string is printed as a description of the primal heuristic in the interactive shell when you call "display heuristics".
3770 * In the interactive shell, this character is printed in the first column of a status information row, if the primal
3771 * heuristic found the feasible solution belonging to the primal bound. Note that a star '*' stands for an integral
3773 * In order to avoid confusion, display characters should be unique: no two primal heuristics should have the same display character.
3774 * You can get a list of all primal heuristics along with their display characters by entering "display heuristics" in the
3778 * At each of the different entry points of the primal heuristics during the solving process (see HEUR_TIMING), they are
3781 * The priority of a primal heuristic should be set according to the complexity of the heuristic and the likelihood to find
3782 * feasible solutions: primal heuristics that provide fast algorithms that often succeed in finding a feasible solution should have
3783 * a high priority (like simple rounding). In addition, the interaction between different types of primal heuristics should be taken into account.
3784 * For example, improvement heuristics, which try to generate improved solutions by inspecting one or more of the feasible
3785 * solutions that have already been found, should have a low priority (like Crossover which by default needs at least 3 feasible solutions).
3788 * The frequency together with the frequency offset (see HEUR_FREQOFS) defines the depth levels at which the execution
3789 * method of the primal heuristic \ref HEUREXEC is called. For example, a frequency of 7 together with a frequency offset
3790 * of 5 means, that the \ref HEUREXEC callback is executed for subproblems that are in depth 5, 12, 19, ... of the branching tree. A
3791 * frequency of 0 together with a frequency offset of 3 means, that the execution method is only called at those nodes that are in
3794 * the heuristic is only called at the root node and a frequency of -1 which disables the heuristic.
3796 * The frequency can be adjusted by the user. This property of the primal heuristic only defines the default value of the
3797 * frequency. If you want to have a more flexible control of when to execute the primal heuristic, you have to assign
3798 * a frequency of 1 and implement a check at the beginning of your execution method whether you really want to search for feasible
3799 * solutions or not. If you do not want to execute the method, set the result code to SCIP_DIDNOTRUN.
3802 * The frequency offset defines the depth of the branching tree at which the primal heuristic is executed for the first
3803 * time. For example, a frequency of 7 (see HEUR_FREQ) together with a frequency offset of 10 means, that the
3804 * callback is executed for subproblems that are in depth 10, 17, 24, ... of the branching tree. In particular, assigning
3805 * different offset values to heuristics of the same type, like diving heuristics, can be useful for evenly spreading the
3807 * Note that if the frequency is equal to 1, the heuristic is applied for all nodes with depth level larger or equal to
3811 * This parameter denotes the maximal depth level in the branching tree up to which the execution method of the primal
3815 * Primal heuristics have different entry points during the solving process and the execution timing parameter defines the
3822 * - after the processing of a node <em>with solved LP</em> was finished (SCIP_HEURTIMING_AFTERLPNODE)
3823 * - after the processing of a node <em>without solved LP</em> was finished (SCIP_HEURTIMING_AFTERPSEUDONODE)
3824 * - after the processing of the last node in the current plunge was finished, <em>and only if the LP was solved for
3826 * - after the processing of the last node in the current plunge was finished, <em>and only if the LP was not solved
3830 * The flags listed above can be combined to call the heuristic at multiple times by concatenating them with a bitwise OR.
3832 * - after the processing of a node was finished (SCIP_HEURTIMING_AFTERNODE; combines SCIP_HEURTIMING_AFTERLPNODE and
3834 * - after the processing of the last node in the current plunge was finished (SCIP_HEURTIMING_AFTERPLUNGE; combines
3837 * Calling a primal heuristic "before the processing of the node starts" is particularly useful for heuristics
3838 * that do not need to access the LP solution of the current node. If such a heuristic finds a feasible solution, the
3839 * leaves of the branching tree exceeding the new primal bound are pruned. It may happen that even the current node can
3840 * be cut off without solving the LP relaxation. Combinatorial heuristics, like the farthest insert heuristic for the TSP
3843 * Very fast primal heuristics that require an LP solution can also be called "after each LP solve during the
3848 * (e.g. expensive rounding heuristics like RENS), or even only after a full plunge was finished (e.g., diving heuristics).
3851 * Some heuristics and separators solve MIPs or SAT problems using a secondary SCIP instance. Examples are
3852 * Large Neighborhood Search heuristics such as RINS and Local Branching or the CGMIP separator. To avoid recursion,
3853 * these plugins usually deactivate all other plugins that solve MIPs. If a heuristic uses a secondary SCIP instance,
3854 * this parameter has to be TRUE and it is recommended to call SCIPsetSubscipsOff() for the secondary SCIP instance.
3856 * Computational experiments indicate that for the overall performance of a MIP solver, it is important to evenly
3857 * spread the application of the heuristics across the branch-and-bound tree. Thus, the assignment of the parameters
3860 * Note that all diving heuristics in the SCIP distribution (see, e.g., src/scip/heur_guideddiving.c) check whether other diving
3861 * heuristics have already been called at the current node. This can be done by comparing SCIPgetLastDivenode(scip) and
3862 * SCIPgetNNodes(scip). If the two are equal, and if the current node is not the root node (SCIPgetDepth(scip) > 0), diving
3863 * heuristics should be delayed by returning the result code 'SCIP_DELAYED'. This is an additional contribution to the goal of
3869 * Below the header "Data structures" you can find a struct which is called "struct SCIP_HeurData".
3870 * In this data structure, you can store the data of your primal heuristic. For example, you should store the adjustable
3872 * If you are using C++, you can add primal heuristic data as usual as object variables to your class.
3879 * At the bottom of "heur_myheuristic.c", you can find the interface method SCIPincludeHeurMyheuristic(),
3885 * It is responsible for notifying SCIP of the presence of the heuristic. For this, you can either call
3887 * or SCIPincludeHeurBasic() since SCIP version 3.0. In the latter variant, \ref HEUR_ADDITIONALCALLBACKS "additional callbacks"
3888 * must be added via setter functions as, e.g., SCIPsetHeurCopy(). We recommend this latter variant because
3889 * it is more stable towards future SCIP versions which might have more callbacks, whereas source code using the first
3890 * variant must be manually adjusted with every SCIP release containing new callbacks for heuristics in order to compile.
3892 * If you are using primal heuristic data, you have to allocate the memory for the data at this point.
3899 * You may also add user parameters for your primal heuristic, see the method SCIPincludeHeurFeaspump() in
3905 * The fundamental callback methods of the plugins are the ones that have to be implemented in order to obtain
3907 * They are passed together with the primal heuristic itself to SCIP using SCIPincludeHeur() or SCIPincludeHeurBasic(),
3911 * Primal heuristic plugins have only one fundamental callback method, namely the HEUREXEC method.
3912 * This method has to be implemented for every primal heuristic; the other callback methods are optional.
3913 * In the C++ wrapper class scip::ObjHeur, the scip_exec() method (which corresponds to the HEUREXEC callback) is a virtual
3914 * abstract member function. You have to implement it in order to be able to construct an object of your primal heuristic
3921 * The HEUREXEC callback is called at different positions during the node processing loop, see HEUR_TIMING. It should
3922 * search for feasible solutions and add them to the solution pool. For creating a new feasible solution, the
3923 * methods SCIPcreateSol() and SCIPsetSolVal() can be used. Afterwards, the solution can be added to the storage by
3926 * The HEUREXEC callback gets a SCIP pointer, a pointer to the heuristic itself, the current point in the
3932 * - stating that the primal heuristic searched, but did not find a feasible solution (result SCIP_DIDNOTFIND)
3934 * - stating that the primal heuristic was skipped, but should be called again (result SCIP_DELAYED).
3939 * The additional callback methods do not need to be implemented in every case. However, some of them have to be
3940 * implemented for most applications, they can be used, for example, to initialize and free private data.
3941 * Additional callbacks can either be passed directly with SCIPincludeHeur() to SCIP or via specific
3942 * <b>setter functions</b> after a call of SCIPincludeHeurBasic(), see also @ref HEUR_INTERFACE.
3946 * If you are using primal heuristic data, you have to implement this method in order to free the primal heuristic data.
3964 * If you have allocated memory for fields in your primal heuristic data, remember to free this memory
3986 * In this method, the primal heuristic should free all resources that have been allocated for the solving process in
3991 * The HEURINITSOL callback is executed when the presolving is finished and the branch-and-bound process is about to
3992 * begin. The primal heuristic may use this call to initialize its branch-and-bound specific data.
3996 * The HEUREXITSOL callback is executed before the branch-and-bound process is freed. The primal heuristic should use this
4000 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
4003 * SCIP provides specific support for LP relaxations of constraint integer programs. In addition, relaxation handlers,
4004 * also called relaxators, can be used to include other relaxations, e.g. Lagrange relaxations or semidefinite
4005 * relaxations. The relaxation handler manages the necessary data structures and calls the relaxation solver to generate dual
4008 * However, the data to define a single relaxation must either be extracted by the relaxation handler itself (e.g., from
4009 * the user defined problem data, the LP information, or the integrality conditions), or be provided by the constraint
4010 * handlers. In the latter case, the constraint handlers have to be extended to support this specific relaxation.
4013 * We now explain how users can add their own relaxation handlers using the C interface. It is very easy to
4014 * transfer the C explanation to C++: whenever a method should be implemented using the SCIP_DECL_RELAX... notion,
4015 * reimplement the corresponding virtual member function of the abstract scip::ObjRelax wrapper base class.
4016 * Unfortunately, SCIP does not contain a default relaxation handler plugin, which could be used as an example.
4018 * Additional documentation for the callback methods of a relaxation handler can be found in the file type_relax.h.
4021 * -# Copy the template files src/scip/relax_xyz.c and src/scip/relax_xyz.h into files named "relax_myrelaxator.c"
4024 * Make sure to adjust your Makefile such that these files are compiled and linked to your project.
4025 * -# Use SCIPincludeRelaxMyrelaxator() in order to include the relaxation handler into your SCIP instance,
4027 * -# Open the new files with a text editor and replace all occurrences of "xyz" by "myrelaxator".
4032 * -# Implement the additional callback methods (see \ref RELAX_ADDITIONALCALLBACKS). This is optional.
4037 * At the top of the new file "relax_myrelaxator.c" you can find the relaxation handler properties.
4039 * In the C++ wrapper class, you have to provide the relaxation handler properties by calling the constructor
4045 * Additionally, if you are searching for a relaxation handler with SCIPfindRelax(), this name is looked up.
4053 * price-and-cut loop for solving the LP relaxation are called in a predefined order, which is given by the priorities
4055 * First, the relaxation handlers with non-negative priority are called in the order of decreasing priority.
4057 * Finally, the relaxation handlers with negative priority are called in the order of decreasing priority.
4059 * Usually, you will have only one relaxation handler in your application and thus only have to decide whether it should
4060 * be called before or after solving the LP relaxation. For this decision you should consider the complexity of
4061 * the relaxation solving algorithm and the impact of the resulting solution: if your relaxation handler provides a fast
4063 * feasible region of the subproblem and the solution severely improves the dual bound), it should have a non-negative
4066 * Note that for certain applications, it is useful to disable the LP relaxation and only use your custom relaxation.
4070 * The frequency defines the depth levels at which the relaxation solving method \ref RELAXEXEC is called.
4071 * For example, a frequency of 7 means, that the relaxation solving callback is executed for subproblems that are in depth
4072 * 0, 7, 14, ... of the branching tree. A frequency of 0 means that the callback is only executed at the root node, i.e.,
4073 * only the relaxation of the root problem is solved. A frequency of -1 disables the relaxation handler.
4078 * Below the header "Data structures" you can find a struct which is called "struct SCIP_RelaxData".
4079 * In this data structure, you can store the data of your relaxation handler. For example, you should store the adjustable
4081 * If you are using C++, you can add relaxation handler data as usual as object variables to your class.
4088 * At the bottom of "relax_myrelaxator.c", you can find the interface method SCIPincludeRelaxMyrelaxator(),
4090 * SCIPincludeRelaxMyrelaxator() is called by the user, if (s)he wants to include the relaxation handler,
4094 * It is responsible for notifying SCIP of the presence of the relaxation handler. For this, you can either call
4096 * or SCIPincludeRelaxBasic() since SCIP version 3.0. In the latter variant, \ref RELAX_ADDITIONALCALLBACKS "additional callbacks"
4097 * must be added via setter functions as, e.g., SCIPsetRelaxCopy(). We recommend this latter variant because
4098 * it is more stable towards future SCIP versions which might have more callbacks, whereas source code using the first
4099 * variant must be manually adjusted with every SCIP release containing new callbacks for relaxation handlers in order to compile.
4101 * If you are using relaxation handler data, you have to allocate the memory for the data at this point.
4108 * You may also add user parameters for your relaxation handler, see the method SCIPincludeConshdlrKnapsack() in
4109 * the \ref cons_knapsack.h "knapsack constraint handler" for an example of how to add user parameters.
4114 * The fundamental callback methods of the plugins are the ones that have to be implemented in order to obtain
4116 * They are passed together with the relaxation handler itself to SCIP using SCIPincludeRelax() or SCIPincludeRelaxBasic(),
4120 * Relaxation handler plugins have only one fundamental callback method, namely the \ref RELAXEXEC method.
4121 * This method has to be implemented for every relaxation handler; the other callback methods are optional.
4122 * In the C++ wrapper class scip::ObjRelax, the scip_exec() method (which corresponds to the \ref RELAXEXEC callback) is a virtual
4124 * You have to implement it in order to be able to construct an object of your relaxation handler class.
4132 * Note that, like the LP relaxation, the relaxation handler should only operate on variables for which the corresponding
4133 * column exists in the transformed problem. Typical methods called by a relaxation handler are SCIPconstructLP() and SCIPflushLP() to
4134 * make sure that the LP of the current node is constructed and its data can be accessed via calls to SCIPgetLPRowsData()
4135 * and SCIPgetLPColsData(), SCIPseparateSol() to call the cutting plane separators for a given primal solution, and
4136 * SCIPupdateLocalLowerbound() to update the current node's dual bound after having solved the relaxation.
4137 * In addition, you may want to call SCIPtrySolFree() if you think that you have found a feasible primal solution.
4140 * <code>SCIPsetRelaxSolVal()</code> and <code>SCIPsetRelaxSolVals()</code> and later accessed by
4142 * Furthermore, there is a list of external branching candidates, that can be filled by relaxation handlers and constraint handlers,
4143 * allowing branching rules to take these candidates as a guide on how to split the problem into subproblems.
4144 * Relaxation handlers should store appropriate candidates in this list using the method <code>SCIPaddExternBranchCand()</code>.
4146 * Usually, the RELAXEXEC callback only solves the relaxation and provides a lower (dual) bound with a call to
4148 * However, it may also produce domain reductions, add additional constraints or generate cutting planes. It has the
4150 * - detecting that the node is infeasible in the variable's bounds and can be cut off (result SCIP_CUTOFF)
4151 * - adding an additional constraint and stating that the relaxation handler should not be called again on the same
4153 * - reducing a variable's domain and stating that the relaxation handler should not be called again on the same
4155 * - adding a cutting plane to the LP and stating that the relaxation handler should not be called again on the same
4157 * - stating that the relaxation handler solved the relaxation and should not be called again on the same relaxation
4159 * - interrupting the solving process to wait for additional input, e.g., cutting planes (result SCIP_SUSPENDED)
4162 * In the above criteria, "the same relaxation" means that the LP relaxation stayed unmodified. This means in particular
4163 * that no row has been added and no bounds have been modified. For example, changing the bounds of a variable will, as
4164 * long as it was a COLUMN variable, lead to a modification in the LP such that the relaxation handler is called again
4170 * The additional callback methods do not need to be implemented in every case. However, some of them have to be
4171 * implemented for most applications, they can be used, for example, to initialize and free private data.
4172 * Additional callbacks can either be passed directly with SCIPincludeRelax() to SCIP or via specific
4173 * <b>setter functions</b> after a call of SCIPincludeRelaxBasic(), see also @ref RELAX_INTERFACE.
4177 * If you are using relaxation handler data, you have to implement this method in order to free the relaxation handler
4195 * If you have allocated memory for fields in your relaxation handler data, remember to free this memory
4217 * In this method, the relaxation handler should free all resources that have been allocated for the solving process in
4222 * The RELAXINITSOL callback is executed when the presolving is finished and the branch-and-bound process is about to
4223 * begin. The relaxation handler may use this call to initialize its branch-and-bound specific data.
4231 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
4234 * Mainly, file readers are called to parse an input file and generate a constraint integer programming model. They
4235 * create constraints and variables and activate variable pricers if necessary. However, they can also be called, for
4236 * example, to parse an input file containing information about a primal solution or fixing of variables. Besides that
4237 * it is possible to use some of them for writing (exporting) the problem in a specific format. \n A complete list of
4252 * Take the file reader for MIPs in IBM's Mathematical Programming System format (src/scip/reader_mps.c) as an example.
4253 * As all other default plugins, it is written in C. C++ users can easily adapt the code by using the scip::ObjReader wrapper
4254 * base class and implement the scip_...() virtual methods instead of the SCIP_DECL_READER... callback methods.
4256 * Additional documentation for the callback methods of a file reader can be found in the file type_reader.h.
4262 * Make sure to adjust your Makefile such that these files are compiled and linked to your project.
4263 * -# Use SCIPincludeReaderMyreader() in order to include the file reader into your SCIP instance,
4270 * -# Implement the \ref READER_ADDITIONALCALLBACKS "additional callback methods". This is optional.
4277 * In the C++ wrapper class, you have to provide the file reader properties by calling the constructor
4283 * Additionally, if you are searching for a file reader with SCIPfindReader(), this name is looked up.
4290 * Each file reader is hooked to a single file name extension. It is automatically called if the user wants to read in a
4292 * Note that the additional extension '.gz', '.z', or '.Z' (indicating a gzip compressed file) are ignored for assigning
4296 * It is, however, not necessary to implement the same (parsing/writing) methods more than once, if you want to
4303 * Below the header "Data structures" you can find a struct which is called "struct SCIP_ReaderData".
4304 * In this data structure, you can store the data of your file reader. For example, you should store the adjustable
4306 * If you are using C++, you can add file reader data as usual as object variables to your class.
4313 * At the bottom of "reader_myreader.c", you can find the interface method SCIPincludeReaderMyreader(),
4319 * It is responsible for notifying SCIP of the presence of the reader. For this, you can either call
4321 * or SCIPincludeReaderBasic() since SCIP version 3.0. In the latter variant, \ref READER_ADDITIONALCALLBACKS "additional callbacks"
4322 * must be added via setter functions as, e.g., SCIPsetReaderCopy(). We recommend this latter variant because
4323 * it is more stable towards future SCIP versions which might have more callbacks, whereas source code using the first
4324 * variant must be manually adjusted with every SCIP release containing new callbacks for readers in order to compile.
4326 * If you are using file reader data, you have to allocate the memory for the data at this point.
4333 * You may also add user parameters for your file reader, see the method SCIPincludeReaderLp() in
4344 * methods \ref READERCOPY and \ref READERFREE are optional. In the C++ wrapper class scip::ObjReader, the
4354 * Additional callbacks can either be passed directly with SCIPincludeReader() to SCIP or via specific
4355 * <b>setter functions</b> after a call of SCIPincludeReaderBasic(), see also @ref READER_INTERFACE.
4358 * File reader plugins contain only additional callback methods, namely the methods \ref READERREAD,
4359 * \ref READERWRITE, \ref READERFREE, and \ref READERCOPY. Therefore, these are not needed to be implemented. However,
4366 * The READERREAD callback is called when the user invokes SCIP to read in a file with file name extension
4367 * corresponding to the READER_EXTENSION property of the file reader. This is usually triggered by a call to the method
4369 * The READERREAD callback should parse the input file and perform the desired action, which usually means
4370 * generating a constraint integer programming model, adding a primal solution, fixing variables
4377 * - creating the variables: SCIPcreateVar(), SCIPchgVarType(), SCIPchgVarLb(), SCIPchgVarUb(), SCIPaddVar(), and
4380 * - creating the constraints: SCIPcreateConsLinear(), SCIPaddCoefLinear(), SCIPchgLhsLinear(), SCIPchgRhsLinear(),
4383 * Primal solutions can only be created for the transformed problem. Therefore, the user has to call SCIPtransformProb()
4384 * before (s)he reads in the file containing the solution and adds it to the solution pool via the method SCIPreadSol().
4389 * The READERWRITE callback is called when the user invokes SCIP to write a problem (original or transformed)
4390 * in the format the reader supports. This is only possible if this callback is implemented. To write the problem
4391 * all necessary information is given through the parameters of this callback method (see type_reader.h). This
4392 * information should be used to output the problem in the requested format. This callback method is usually
4393 * triggered by the call of the methods SCIPwriteOrigProblem(), SCIPwriteTransProblem(), SCIPprintOrigProblem(),
4397 * integer programming model is SCIPinfoMessage(). This method outputs a given string into a file
4405 * The READERCOPY callback is executed when a SCIP instance is copied, e.g. to solve a sub-SCIP. By defining this
4406 * callback as <code>NULL</code> the user disables the execution of the specified reader for all copied SCIP
4407 * instances. The question might arise why to copy that plugin. In case of debugging it is nice to be able to
4408 * write/display the copied instances. Since the reader is in charge of that, you might want to copy the plugin. Below
4427 * If you are using file reader data, you have to implement this method in order to free the file reader data.
4445 * If you have allocated memory for fields in your file reader data, remember to free this memory
4452 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
4455 * SCIP comes with a command line shell which allows the user to read in problem instances, modify the solver's
4456 * parameters, initiate the optimization and display certain statistics and solution information. This shell consists
4457 * of dialogs, which are organized as a tree in SCIP. A node of this tree which is not a leaf represents a menu in
4458 * the shell and the children of this node correspond to the entries of this menu (which can again be menus). All
4459 * different dialogs are managed by a dialog handler, which, in particular, is responsible for executing the dialog
4460 * corresponding to the user's command in the shell. The concept of a dialog handler is different to that
4461 * of a constraint handler, which is used to manage objects of the same structure, see \ref CONS. In particular, SCIP
4462 * features only one dialog handler (dialog_default.h), whereas there may exist different constraint handlers.
4467 * We give the explanation for creating your own source file for each additional dialog. Of course, you can collect
4468 * different dialogs in one source file. Take src/scip/dialog_default.c, where all default dialog plugins are collected, as an
4470 * As all other default plugins, the default dialog plugin and the template dialog are written in C. C++ users can easily
4471 * adapt the code by using the scip::ObjDialog wrapper base class and implement the scip_...() virtual methods instead of the
4474 * Additional documentation for the callback methods of a dialog can be found in the file type_dialog.h.
4477 * -# Copy the template files src/scip/dialog_xyz.c and src/scip/dialog_xyz.h into files named "dialog_mydialog.c"
4480 * Make sure to adjust your Makefile such that these files are compiled and linked to your project.
4481 * -# Use SCIPincludeDialogMydialog() in order to include the dialog handler into your SCIP instance,
4488 * -# Implement the \ref DIALOG_ADDITIONALCALLBACKS "additional callback methods". This is optional.
4495 * In the C++ wrapper class, you have to provide the dialog properties by calling the constructor
4500 * In the interactive shell, this name appears as the command name of the dialog in the parent dialog.
4501 * Additionally, if you are searching an entry in a menu with SCIPdialogFindEntry(), this name is looked up.
4502 * Names within one menu have to be unique: no two dialogs in the same menu may have the same name.
4505 * This string is printed as a description of the dialog in the interactive shell if the additional
4509 * This parameter states whether the dialog is a menu in the interactive shell, i.e., is the parent of further
4515 * Below the header "Data structures" you can find a struct which is called "struct SCIP_DialogData".
4524 * At the bottom of "dialog_mydialog.c" you can find the interface method SCIPincludeDialogMydialog(), which also appears
4528 * It is responsible for notifying SCIP of the presence of the dialog, which can be done by the following lines of code:
4532 * SCIP_CALL( SCIPcreateDialog(scip, &dialog, dialogExecMydialog, dialogDescMydialog, dialogFreeMydialog,
4540 * Here "parentdialog" has to be an existing dialog which is defined to be a menu (see DIALOG_ISSUBMENU), e.g.,
4543 * The interface method is called by the user, if (s)he wants to include the dialog, i.e., if (s)he wants to use the dialog in
4547 * default dialogs plugin</b>, i.e., the SCIPincludeDialogMydialog() call has to occur after the
4548 * SCIPincludeDialogDefault() call. The SCIPincludeDialogDefault() method is called from within the SCIPincludeDefaultPlugins()
4549 * method. Therefore, it suffices to include your dialog plugins after you have called SCIPincludeDefaultPlugins().
4574 * Consider the following example. The user wants to add a "drawgraph" command to the root menu of SCIP.
4575 * (S)he copies the "dialog_xyz.c" and "dialog_xyz.h" files into files "dialog_drawgraph.c" and "dialog_drawgraph.h", respectively.
4576 * Then, (s)he puts the following code into the SCIPincludeDialogDrawgraph() method, compare SCIPincludeDialogDefault() in
4605 * Using this code, it is even possible to call SCIPincludeDialogDrawgraph() before including the default dialog plugins,
4606 * and you can also call it multiple times without causing inconsistencies in the dialog structure.
4613 * In the C++ wrapper class scip::ObjDialog, the scip_exec() method (which corresponds to the \ref DIALOGEXEC callback) is a virtual
4621 * The DIALOGEXEC method is invoked, if the user selected the dialog's command name in the parent's menu. It should
4622 * execute what is stated in DIALOG_DESC, e.g., the display constraint handlers dialog should display information about
4625 * For typical methods called by the execution method, have a look at src/scip/dialog_default.c.
4627 * The callback has to return which dialog should be processed next. This can be, for example, the root dialog
4628 * (SCIPdialoghdlrGetRoot()), the parent dialog (SCIPdialogGetParent()) or NULL, which stands for closing the interactive
4639 * If you are using dialog data, you have to implement this method in order to free the dialog data.
4664 * This method is called when the help menu of the parent is displayed. It should output (usually a single line of)
4667 * If this callback is not implemented, the description string of the dialog (DIALOG_DESC) is displayed instead.
4671 * The DIALOGCOPY callback is executed when a SCIP instance is copied, e.g. to solve a sub-SCIP. By defining this
4672 * callback as <code>NULL</code> the user disables the execution of this dialog for all copied SCIP instances. In
4673 * general there is no need to copy any dialog since it is most unlikely to start the interactive shell of the copied
4678 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
4681 * While solving a constraint integer program, SCIP displays status information in a column-like fashion. The current
4682 * number of processed branching tree nodes, the solving time, and the relative gap between primal and dual bound are
4683 * examples of such display columns. There already exists a wide variety of display columns which can be activated or
4684 * deactivated on demand, see src/scip/disp_default.c. Additionally, the user can implement his/her own display columns
4690 * We give the explanation for creating your own source file for each additional display column. Of course, you can collect
4692 * Take src/scip/disp_default.c, where all default display columns are collected, as an example.
4693 * As all other default plugins, the default display column plugins and the display column template are written in C.
4694 * C++ users can easily adapt the code by using the scip::ObjDisp wrapper base class and implement the scip_...() virtual methods
4698 * Additional documentation for the callback methods of a display column can be found in the file type_disp.h.
4700 * Here is what you have to do to implement a display column (assuming your display column is named "mydisplaycolumn"):
4701 * -# Copy the template files src/scip/disp_xyz.c and src/scip/disp_xyz.h into files named "disp_mydisplaycolumn.c"
4704 * Make sure to adjust your Makefile such that these files are compiled and linked to your project.
4705 * -# Use SCIPincludeDispMydisplaycolumn() in order to include the display column into your SCIP instance,
4707 * -# Open the new files with a text editor and replace all occurrences of "xyz" by "mydisplaycolumn".
4712 * -# Implement the \ref DISP_ADDITIONALCALLBACKS "additional callback methods". This is optional.
4717 * At the top of the new file "disp_mydisplaycolumn.c" you can find the display column properties.
4719 * In the C++ wrapper class, you have to provide the display column properties by calling the constructor
4725 * Additionally, if you are searching for a display column with SCIPfindDisp(), this name is looked up.
4732 * This string is printed as the header of the display column in the status information display.
4735 * This parameter defines the width (number of characters) of the display column. The value of the parameter has to be
4739 * The total width of status information lines is bounded by the parameter "display width". The display columns actually contained
4740 * in the status information display are selected in decreasing order of their priority. Furthermore, the user can force
4741 * columns to be displayed or not to be displayed in the status information display. For that, (s)he has to switch the value
4742 * of the display column's parameter "active" from "auto" (its default value) to "on" or "off", respectively.
4745 * In the status information display, the display columns are arranged from left to right in increasing order of their
4748 * \par DISP_STRIPLINE: the default for whether the display column should be separated with a line from its right neighbor.
4749 * This parameter states whether the display column should be separated with the string "|" from its right neighbor. In so
4754 * Below the header "Data structures" you can find a struct which is called "struct SCIP_DispData".
4755 * In this data structure, you can store the data of your display column. For example, you should store the adjustable
4757 * If you are using C++, you can add display column data as usual as object variables to your class.
4764 * At the bottom of "disp_mydisplaycolumn.c" you can find the interface method SCIPincludeDispMydisplaycolumn(), which also
4768 * It is responsible for notifying SCIP of the presence of the display column by calling the method
4771 * The interface method is called by the user, if (s)he wants to include the display column, i.e., if (s)he wants to use the display column in his
4774 * If you are using display column data, you have to allocate the memory for the data at this point.
4781 * Although this is very uncommon, you may also add user parameters for your display column, see the method
4782 * SCIPincludeConshdlrKnapsack() in the \ref cons_knapsack.h "knapsack constraint handler" for an example.
4787 * Display column plugins have only one fundamental callback method, namely the \ref DISPOUTPUT method.
4788 * This method has to be implemented for every display column; the other callback methods are optional.
4789 * In the C++ wrapper class scip::ObjDisp, the scip_output() method (which corresponds to the \ref DISPOUTPUT callback) is a virtual
4791 * You have to implement it in order to be able to construct an object of your display column class.
4797 * The DISPOUTPUT callback is called after each pricing loop during node processing and after a node has been processed.
4798 * In addition, at the root node, the callback is executed after each iteration of the price-and-cut loop.
4799 * It should write the display column information for the current node to a given output file stream.
4801 * Typical methods called by a display column are, for example, SCIPdispLongint(), SCIPdispInt(), SCIPdispTime(), and
4812 * The DISPCOPY callback is executed when a SCIP instance is copied, e.g. to solve a sub-SCIP. By defining this callback
4813 * as <code>NULL</code> the user disables the execution of the specified column. In general it is probably not needed to
4814 * implement that callback since the output of the copied instance is usually suppressed. In the other case or for
4820 * If you are using display column data, you have to implement this method in order to free the display column data.
4838 * If you have allocated memory for fields in your display column data, remember to free this memory
4851 * In this method, the display column should free all resources that have been allocated for the solving process in
4856 * The DISPINITSOL callback is executed when the presolving is finished and the branch-and-bound process is about to
4857 * begin. The display column may use this call to initialize its branch-and-bound specific data.
4861 * The DISPEXITSOL callback is executed before the branch-and-bound process is freed. The display column should use this
4865 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
4868 * While solving a constraint integer program, SCIP drops thousands of events such as SCIP_EVENTTYPE_VARFIXED (a
4869 * complete list of all events is given in type_event.h). These events can be caught and used to do something after a
4870 * certain event happens. Events can be used to speed up the solution process. For example, the set partitioning
4871 * constraint is only worth propagating if one of the involved variables is fixed. This can be detected by
4872 * catching the event SCIP_EVENTTYPE_VARFIXED. To be able to catch an event it is necessary to write an event handler
4875 * We now explain how users can add their own event handlers. We give the explanation for creating your own
4876 * source file for each additional event handler. Of course, you can collect different event handlers in one source file
4877 * or you can put the event handler directly into the constraint handler. In a \ref EVENTUSAGE "second step" we discuss
4878 * the usage of an event handler. This means how to catch and drop events. \ref EVENTTYPES "Finally", we give some notes on the existing
4881 * Take src/scip/cons_logior.c, where the event handler is directly included into the constraint handler. As all other
4882 * default plugins, the event handlers are written in C. C++ users can easily adapt the code by using the scip::ObjEventhdlr
4883 * wrapper base class and implement the scip_...() virtual methods instead of the SCIP_DECL_EVENT... callback methods.
4885 * Additional documentation for the callback methods of an event handler can be found in the file type_event.h. There is
4886 * also an example written in C which deals with an event handler. You find this example in the directory
4887 * "examples/Eventhdlr/". An C++ example can be found within the TSP project (examples/TSP/src/EventhdlrNewSol.cpp).
4889 * Here is what you have to do to implement an event handler (assuming your event handler is named "bestsol"):
4890 * -# Copy the template files src/scip/event_xyz.c and src/scip/event_xyz.h into files named "event_bestsol.c"
4893 * Make sure to adjust your Makefile such that these files are compiled and linked to your project.
4894 * -# Use SCIPincludeEventBestsol() in order to include the event handler into your SCIP instance,
4900 * -# Implement the \ref EVENT_ADDITIONALCALLBACKS "additional callback methods". This is optional.
4907 * In the C++ wrapper class, you have to provide the event handler properties by calling the constructor
4912 * This name has to be unique with respect to all other event handlers. If you are searching for an event handler with
4920 * Below the header "Data structures" you can find a struct which is called "struct SCIP_EventhdlrData".
4921 * In this data structure, you can store the data of your event handler. For example, you should store the adjustable
4923 * If you are using C++, you can add event handler data as usual as object variables to your class.
4930 * At the bottom of "event_bestsol.c", you can find the interface method SCIPincludeEventBestsol(),
4932 * SCIPincludeEventBestsol() is called by the user, if (s)he wants to include the event handler,
4936 * It is responsible for notifying SCIP of the presence of the event handler. For this, you can either call
4938 * or SCIPincludeEventhdlrBasic() since SCIP version 3.0. In the latter variant, \ref EVENT_ADDITIONALCALLBACKS "additional callbacks"
4939 * must be added via setter functions as, e.g., SCIPsetReaderCopy(). We recommend this latter variant because
4940 * it is more stable towards future SCIP versions which might have more callbacks, whereas source code using the first
4941 * variant must be manually adjusted with every SCIP release containing new callbacks for event handlers in order to compile.
4943 * If you are using event handler data, you have to allocate the memory for the data at this point.
4950 * Although this is very uncommon, you may also add user parameters for your event handler, see the method
4951 * SCIPincludeConshdlrKnapsack() in the \ref cons_knapsack.h "knapsack constraint handler" for an example.
4956 * The fundamental callback methods of the plugins are the ones that have to be implemented in order to obtain
4958 * They are passed together with the event handler itself to SCIP using SCIPincludeEventhdlr() or SCIPincludeEventhdlrBasic(),
4962 * Event handler plugins have only one fundamental callback method, namely the \ref EVENTEXEC method. This method has
4963 * to be implemented for every event handler; the other callback methods are optional. In the C++ wrapper class
4964 * scip::ObjEventhdlr, the scip_exec() method (which corresponds to the \ref EVENTEXEC callback) is a virtual abstract member
4965 * function. You have to implement it in order to be able to construct an object of your event handler class.
4971 * The EVENTEXEC callback is called after the requested event happened. Then the event handler can do some action in
4974 * Typical the execution method sets a parameter to TRUE to indicate later in solving process that something happened
4975 * which should be analyzed further. In the \ref cons_knapsack.h "knapsack constraint handler" you find such a typical
4980 * The additional callback methods do not need to be implemented in every case. However, some of them have to be
4981 * implemented for most applications, they can be used, for example, to initialize and free private data.
4982 * Additional callbacks can either be passed directly with SCIPincludeEventhdlr() to SCIP or via specific
4983 * <b>setter functions</b> after a call of SCIPincludeEventhdlrBasic(), see also @ref EVENT_INTERFACE.
4987 * The EVENTCOPY callback is executed when a SCIP instance is copied, e.g. to solve a sub-SCIP. By defining this
4988 * callback as <code>NULL</code> the user disables the execution of the specified event handler for all copied SCIP
4989 * instances. Note that in most cases the event handler in the copied instance will be initialize by those objects (such
4990 * as constraint handlers or propagators) which need this event handler (see \ref cons_knapsack.h). In these cases the copy
4992 * (SCIP_EVENTTYPE_BESTSOLFOUND), you might want to implement that callback. The event handler example which you find
5012 * If you are using event handler data, you have to implement this method in order to free the event handler data.
5030 * If you have allocated memory for fields in your event handler data, remember to free this memory
5044 * In this method, the event handler should free all resources that have been allocated for the solving process in
5049 * The EVENTINITSOL callback is executed when the presolving is finished and the branch-and-bound process is about to
5054 * The EVENTEXITSOL callback is executed before the branch-and-bound process is freed. The event handler should use this
5059 * After you have implemented the event handler, you have to tell SCIP for which events this event handler should be
5060 * used. This can be a general events, such as <code>SCIP_EVENTTYPE_BESTSOLFOUND</code>, or a variable event which is the most common
5063 * In case of a general (not variable) event you use the function SCIPcatchEvent() to attach to an event and
5074 * If you want trigger some variable event, you use the method SCIPcatchVarEvent() to attach the variable event and
5087 * All available events are listed in type_event.h. There are atomic events such as <code>SCIP_EVENTTYPE_VARFIXED</code>
5088 * and combined events such as <code>SCIP_EVENTTYPE_VARCHANGED</code>. The events are encoded via bit masks. Each atomic
5091 * SCIP only throws atomic events. However, an event handler might be interested in bunch of events. Through the
5092 * underlying bit masks it is possible to combine the atomic events. For example, <code>SCIP_EVENTTYPE_VARCHANGED</code>
5093 * is an event which combines the events <code>SCIP_EVENTTYPE_VARFIXED</code>, <code>SCIP_EVENTTYPE_VARUNLOCKED</code>,
5098 * #define SCIP_EVENTTYPE_VARCHANGED (SCIP_EVENTTYPE_VARFIXED | SCIP_EVENTTYPE_VARUNLOCKED | SCIP_EVENTTYPE_OBJCHANGED
5102 * Depending on the event type, the event offers different information. The methods which can be used to gain
5107 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
5111 * It is used, e.g., to solve convex relaxations of the problem or to find locally optimal solutions of
5115 * While the NLPI itself corresponds to the solver interface, the NLPIPROBLEM corresponds to the
5117 * An NLP is specified as a set of indexed variables with variable bounds, an objective function,
5118 * and a set of constraints, where each constraint is specified as a function which is restricted to lie
5121 * The linear and quadratic parts are specified via variable indices and coefficients, while the
5123 * That is, the user of the NLPI does not provide function evaluation callbacks but an algebraic representation of the NLP.
5124 * Interfaces for solvers that require function evaluations can make use of the NLPIORACLE, which
5125 * provides a set of methods to compute functions values, gradients, Jacobians, and Hessians for a given NLP.
5133 * Additional documentation for the callback methods of an NLPI, in particular for their input parameters,
5137 * -# Copy the template files src/nlpi/nlpi_xyz.c and src/nlpi/nlpi_xyz.h into files named "nlpi_mynlpi.c"
5140 * Make sure to adjust your Makefile such that these files are compiled and linked to your project.
5168 * solvers that provide fast algorithms that are usually successful on a wide range of problems should have a high priority.
5169 * An easy way to list the priorities of all NLPIs is to type "display nlpis" in the interactive shell of SCIP.
5173 * Below the header "Data structures" you can find structs which are called "struct SCIP_NlpiData" and "struct SCIP_NlpiProblem".
5174 * In this data structure, you can store the data of your solver interface and of a specific NLP problem.
5175 * For example, you could store a pointer to the block memory data structure in the SCIP_NlpiData data structure
5180 * At the bottom of "nlpi_mynlpi.c", you can find the interface method SCIPcreateNlpSolverXyz(),
5184 * It is responsible for creating an NLPI that contains all properties and callback methods of your
5186 * SCIPcreateNlpSolverXyz() is called by the user (e.g., SCIP), if (s)he wants to use this solver interface in his/her application.
5199 * The fundamental callback methods of the plugins are the ones that have to be implemented in order to obtain
5207 * The NLPICOPY callback is executed if the plugin should be copied, e.g., when a SCIP instance is copied.
5211 * The NLPIFREE callback is executed if the NLP solver interface data structure should be freed, e.g., when a SCIP instance is freed.
5215 * The NLPIGETSOLVERPOINTER callback can be used to pass a pointer to a solver specific data structure to the user.
5220 * The callback method should initialize a SCIP_NlpiProblem struct here that corresponds to an empty NLP.
5229 * The NLPIGETPROBLEMPOINTER callback can be used to pass a pointer to a solver specific data structure of the NLP to the user.
5233 * The NLPIADDVARS callback is executed if a set of variables with lower and upper bounds and names should be added to a particular NLP.
5234 * The callback method must add the new variables behind the previously added variables, if any.
5235 * If NULL is given for the lower bounds arguments, -infinity is assumed as lower bound for each new variable.
5236 * If NULL is given for the upper bounds arguments, +infinity is assumed as upper bound for each new variable.
5241 * The NLPIADDCONSTRAINTS callback is executed if a set of constraints should be added to a particular NLP.
5242 * Constraints are specified by providing left and right hand sides, linear and quadratic coefficients, expression trees, and constraint names.
5243 * All of these arguments are optional, giving NULL for left hand sides corresponds to -infinity, giving NULL for right hand sides corresponds to +infinity.
5251 * The NLPICHGVARBOUNDS callback is executed to change the bounds on a set of variables of an NLP.
5255 * The NLPICHGCONSSIDES callback is executed to change the sides on a set of constraints of an NLP.
5260 * The caller provides an array in which for each variable it is marked whether it should be deleted.
5261 * In the same array, the method should return the new position of each variable in the NLP, or -1 if it was deleted.
5266 * The caller provides an array in which for each constraint it is marked whether it should be deleted.
5267 * In the same array, the method should return the new position of each constraint in the NLP, or -1 if it was deleted.
5271 * The NLPICHGLINEARCOEFS callback is executed to change the coefficients in the linear part of the objective function or a constraint of an NLP.
5275 * The NLPICHGQUADCOEFS callback is executed to change the coefficients in the quadratic part of the objective function or a constraint of an NLP.
5279 * The NLPICHGEXPRTREE callback is executed to replace the expression tree of the objective function or a constraint of an NLP.
5283 * The NLPICHGNONLINCOEF callback is executed to change a single parameter in the (parametrized) expression tree of the objective function or a constraint of an NLP.
5287 * The NLPICHGOBJCONSTANT callback is executed to change the constant offset of the objective function of an NLP.
5291 * The NLPISETINITIALGUESS callback is executed to provide primal and dual initial values for the variables and constraints of an NLP.
5293 * It is possible to pass a NULL pointer for any of the arguments (primal values of variables, dual values of variable bounds, dual values of constraints).
5294 * In this case, the solver should clear previously set starting values and setup its own starting point.
5305 * The NLPIGETSOLSTAT callback can be used to request the solution status (solved, infeasible, ...) after an NLP has been solved.
5309 * The NLPIGETTERMSTAT callback can be used to request the termination reason (normal, iteration limit, ...) after an NLP has been solved.
5313 * The NLPIGETSOLUTION callback can be used to request the primal and dual solution values after an NLP solve.
5315 * It is possible to return only primal values for the variables, but no values for the dual variables, e.g., if a solver does not compute such values.
5319 * The NLPIGETSTATISTICS callback can be used to request the statistical values (number of iterations, time, ...) after an NLP solve.
5323 since they are currently not used, not implemented, and likely to change with a next version. -->
5327 * The NLPIGETINTPAR callback can be used to request the value of an integer valued NLP parameter.
5343 * The NLPIGETSTRINGPAR callback can be used to request the value of a string valued NLP parameter.
5350 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
5353 * An expression interpreter is a tool to compute point-wise and interval-wise the function values, gradients, and
5355 * It is used, e.g., by an NLP solver interface to compute Jacobians and Hessians for the solver.
5357 * The expression interpreter interface in SCIP has been implemented similar to those of the LP solver interface (LPI).
5359 * The expression interpreter API has been designed such that it can be used independently from SCIP.
5361 * A complete list of all expression interpreters contained in this release can be found \ref EXPRINTS "here".
5367 * Additional documentation for the callback methods of an expression interpreter, in particular for their input parameters,
5370 * Note that the expression interpreter API has <b>BETA status</b> and thus may change in the next version.
5373 * -# Copy the file \ref exprinterpret_none.c into a file named "exprinterpreti_myexprinterpret.c".
5375 * Make sure to adjust your Makefile such that these files are compiled and linked to your project.
5389 * In your "exprinterpret_myexprinterpret.c", these methods are mostly dummy methods that return error codes.
5397 * The SCIPexprintGetDesc method should return a short description of the expression interpreter, e.g., the name of the developer of the code.
5401 * The SCIPexprintGetCapability method should return a bitmask that indicates the capabilities of the expression interpreter,
5416 * The SCIPexprintCompile method is called to initialize the data structures that are required to evaluate
5418 * The expression interpreter can store data that is particular to a given expression tree in the tree by using
5428 * The SCIPexprintNewParametrization method is called when the values of the parameters in a parametrized expression tree have changed.
5432 * The SCIPexprintEval method is called when the value of an expression represented by an expression tree should be computed for a point.
5436 * The SCIPexprintEvalInt method is called when an interval that contains the range of an expression represented by an expression tree with respect to intervals for the variables should be computed.
5440 * The SCIPexprintGrad method is called when the gradient of an expression represented by an expression tree should be computed for a point.
5444 * The SCIPexprintGradInt method is called when an interval vector that contains the range of the gradients of an expression represented by an expression tree with respect to intervals for the variables should be computed.
5448 * The SCIPexprintHessianSparsityDense method is called when the sparsity structure of the Hessian matrix should be computed and returned in dense form.
5452 * The SCIPexprintHessianDense method is called when the Hessian of an expression represented by an expression tree should be computed for a point.
5455 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
5458 * Conflict analysis is a way to automatically use the information obtained from infeasible nodes
5461 * Once a node is declared infeasible, SCIP automatically tries to infer a constraint that explains the reason for the
5462 * infeasibility, in order to avoid similar situations later in the search. This explanation essentially consists of a
5463 * constraint stating that at least one of its variables should have a bound different from the current infeasible node,
5464 * because the current setting led to infeasibility. Clearly, all variables that are fixed in the current infeasible
5465 * node would yield such a constraint (since this leads to infeasibility). The key point rather is to infer a "small"
5466 * constraint that does the same job. SCIP handles this by several heuristics. For this, SCIP sets up a
5467 * so-called (directed) conflict graph. The nodes in this graph correspond to bound changes of variables and an arc (@a
5468 * u, @a v) means that the bound change corresponding to @a v is based on the bound change of @a u. In general, a node
5469 * will have several ingoing arcs which represent all bound changes that have been used to infer (propagate) the bound
5470 * change in question. The graph also contains source nodes for each bound that has been changed during branching and an
5471 * artificial target node representing the conflict, i.e., the infeasibility. Essentially, SCIP heuristically constructs
5472 * a cut in this graph that involves few "branching nodes". For details on the techniques that SCIP uses,
5480 * -# If one detects infeasibility, one should initiate conflict analysis, see \ref INITCONFS "below".
5484 * If this functionality is not implemented, SCIP will still work correctly, but cannot use the information of the constraint
5485 * handler or the propagator for conflict analysis. In this case, each bound reduction performed by the constraint
5492 * -# Inform SCIP about the variable bounds that are the reason for the detection of infeasibility
5494 * SCIPaddConflictBinvar(). If there is more than one valid explanation of infeasibility, either one can be used.
5496 * -# Call SCIPanalyzeConflict() from a propagator or SCIPanalyzeConflictCons() from a constraint
5503 * When propagating variable domains, SCIP needs to be informed that the deduced variable bounds should be
5505 * SCIPinferVarUbCons(), and SCIPinferBinvarCons() for constraint handlers and SCIPinferVarLbProp(),
5512 * Reverse Propagation is used to build up the conflict graph. Essentially, it provides an algorithm to detect the arcs
5513 * leading to a node in the conflict graph, i.e., the bound changes responsible for the new bound change deduced during
5514 * propagation. Reverse Propagation needs to be implemented in the RESPROP callback functions of
5516 * These callbacks receive the following information: the variable which is under investigation (@p
5517 * infervar), the corresponding bound change (@p bdchgidx, @p boundtype), and the integer (@p inferinfo) that has been
5520 * One can use SCIPvarGetUbAtIndex() or SCIPvarGetLbAtIndex() to detect the bounds before or after the propagation that
5521 * should be investigated. Then the bounds that were involved should be passed to SCIP via SCIPaddConflictLb() and
5522 * SCIPaddConflictUb(). If there is more than one valid explanation of infeasibility, either one can be used.
5532 * (see @p example/LOP directory). This constraint handler propagates the equations \f$x_{ij} + x_{ji} =
5535 * When propagating the equation and <code>vars[i][j]</code> is fixed to 1, the constraint handler uses
5537 * SCIP_CALL( SCIPinferBinvarCons(scip, vars[j][i], FALSE, cons, i*n + j, &infeasible, &tightened) );
5539 * Thus, variable <code>vars[j][i]</code> is fixed to 0 (@p FALSE), and it passes <code>i*n + j </code> as @p inferinfo.
5541 * When it propagates the triangle inequality and both <code>vars[i][j]</code> and <code>vars[j][k]</code>
5544 * SCIP_CALL( SCIPinferBinvarCons(scip, vars[k][i], FALSE, cons, n*n + i*n*n + j*n + k, &infeasible, &tightened) );
5546 * Thus, in this case, variable <code>vars[k][i]</code> is fixed to 0 and <code>n*n + i*n*n + j*n + k</code> is
5549 * In reverse propagation, the two cases can be distinguished by @p inferinfo: if it is less than @p n*n,
5550 * we deal with an equation, otherwise with a triangle inequality. The constraint handler can then extract the
5553 * In the first case, it has to distinguish whether <code>vars[i][j]</code> is fixed to 0 or 1 –
5555 * or SCIPaddConflictUb(), respectively, with variable <code>vars[j][i]</code>. In the second case, it is clear that the only
5556 * possible propagation is to fix <code>vars[i][j]</code> to 0 when both <code>vars[k][i]</code> and <code>vars[j][k]</code>
5561 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
5567 * reference counter to one. Capturing an object (e.g., by calling SCIPcaptureVar()) increases the reference counter,
5568 * releasing it (e.g., by calling SCIPreleaseVar()) decreases the counter. If the reference counter gets zero, the
5574 * When a data object is added to SCIP (e.g., by calling SCIPaddVar()) , it is captured again, such that a
5584 * the reference counter will be 1 afterwards, and the variable will be destroyed, if SCIP frees the problem.
5585 * If the user wants to use this variable, e.g. for extracting statistics after SCIP was finished, the user must not call
5589 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
5611 * If this is the case, the user can define a method by the PARAMCHGD callback and use this method as
5612 * the @c paramchgd parameter of the @c SCIPaddXyzParam() method, also giving a pointer to the data, which is
5617 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
5622 * - Use <b>asserts</b> in your code to show preconditions for the parameters, invariants and postconditions.
5623 * Assertions are boolean expressions which inevitably have to evaluate to <code>TRUE</code>. Consider the
5640 * As you can see, both pointers and integers are checked for valid values at the beginning of the
5641 * function <code>consdataCatchEvent()</code>. This is particularly important for, e.g., array indices like
5642 * the variable <code>pos</code> in this example, where using the <code>consdata->nvars[pos]</code>
5644 * if the asserted precondition on <code>pos</code> were not matched and <pos> were an arbitrary index
5650 * \endcode and run the code. See \ref MAKE for further information about compiler options for SCIP.
5659 * at the top of SCIP files you want to analyze. This will output messages included in the code using
5661 * We recommend to also use <code>SCIPdebugMessage()</code> in your own code for being able to activate
5666 * - If available on your system, you can use software like <a href="http://valgrind.org">valgrind</a> to check for uninitialized
5671 * - If there are memory leaks for which you cannot detect the origin, you can remake your code with the option NOBLKBUFMEM=true
5672 * (do not forget to clean your code before with <code>make OPT=... LPS=... clean</code>). After that valgrind (or similar) helps
5674 * - If your code cuts off a feasible solution, but you do not know which component is responsible,
5675 * you can define <code>SCIP_DEBUG_SOLUTION</code> in the file <code>debug.h</code> to be a filename
5677 * This solution is then read and it is checked for every cut, whether the solution violates the cut.
5680 * For example, if we include a <code>\#define SCIP_DEBUG</code> at the top of \ref heur_oneopt.h, recompile SCIP
5684 * SCIP version 1.1.0 [precision: 8 byte] [memory: block] [mode: debug] [LP solver: SoPlex 1.4.0]
5693 * 0.1s| 1 | 0 | 132 | 257k| 0 | 14 | 30 | 13 | 13 | 30 | 51 | 39 | 0 | 0 | 3.026472e+03 | 3.347000e+03 | 10.59%
5698 * [src/scip/heur_oneopt.c:102] debug: lb:<-0> <= val:<1> <= ub:<1> and obj:<171> by at most: <1>
5699 * [src/scip/heur_oneopt.c:135] debug: -> The shift value had to be reduced to <0>, because of row <R122>.
5702 * [src/scip/heur_oneopt.c:383] debug: Only one shiftcand found, var <t_C167>, which is now shifted by<-1.0>
5703 * k 0.1s| 1 | 0 | 132 | 258k| 0 | 14 | 30 | 13 | 13 | 30 | 51 | 39 | 0 | 0 | 3.026472e+03 | 3.164000e+03 | 4.54%
5753 * <code>\#define SCIP_DEBUG_SOLUTION "check/p0033.sol"</code> in debug.h, recompile and run SCIP,
5768 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
5778 * At first you should create a file listing all problem instances that should be part of the test.
5784 * e.g., <code>../../problems/instance1.lp</code> or absolute path, e.g., <code>/home/problems/instance2.mps</code>
5785 * in this file. Only one problem should be listed each on line (since the command <code>cat</code> is used to parse this file).
5789 * Optionally, you can provide a solution file in the <code>scip/check/testset/</code> directory containing
5790 * known information about the feasibility and the best known objective values for the test instances.
5791 * SCIP can use these values to verify the results. The file has to have the same basename as the
5792 * <code>.test</code>-file, i.e., in our case <code>testrun.solu</code>. One line can only contain
5799 * With these information types you can encode for an instance named <code>instance1.lp</code> the following
5826 * See the files <code>scip/check/testset/short.test</code> and <code>scip/check/testset/short.solu</code>
5839 * <code>test</code>-file (<code>testrun.test</code>). This will cause SCIP to solve our test instances
5845 * During computation, SCIP automatically creates the directory <code>scip/check/results/</code>
5854 * \arg <code>*.pav</code> - <a href="http://www.gamsworld.org/performance/paver/">PAVER</a> output
5856 * The last three files in the above list, i.e., the files containing a summary of the computational results,
5857 * can also be generated manually. Therefore the user has to call the <code>evalcheck.sh</code> script in the
5858 * @c check directory with the corresponding @c out file as argument. For example, this may be useful if the user stopped the
5859 * test before it was finished, in which case the last three files will not be automatically generated by SCIP.
5861 * The last column of the ASCII summary table contains the solver status. We distinguish the following statuses: (in order of priority)
5864 * \arg fail: solver cut off a known feasible solution (value of the <code>solu</code>-file is beyond the dual bound;
5867 * \arg solved: solver solved problem which has no (optimal) value in solu-file (since we here cannot detect the direction
5868 * of optimization, it is possible that a solver claims an optimal solution which contradicts a known feasible solution)
5869 * \arg better: solver found solution better than known best solution (or no solution was noted in the <code>solu</code>-file so far)
5870 * \arg gaplimit, sollimit: solver reached gaplimit or limit of number of solutions (at present: only in SCIP)
5874 * Additionally the <code>evalcheck.sh</code> script can generate a <code>solu</code>-file by calling
5878 * where <code><solu-file></code> denotes the filename of the new file where the solutions shall be
5885 * The output has two additional columns containing the solving time until the first and the best solution was found.
5895 * \arg <<code>test name</code>> indicates the name of the the test file, e.g., <code>testrun</code>
5896 * \arg <<code>binary</code>> defines the used binary, e.g., <code>scip-1.1.0.linux.x86.gnu.opt.spx</code>
5897 * \arg <<code>machine name</code>> tells the name of the machine, e.g., <code>mycomputer</code>
5898 * \arg <<code>setting name</code>> denotes the name of the used settings, e.g., <code>default</code>
5910 * It is possible to use customized settings files for the test run instead of testing SCIP with default settings.
5913 * @b Note: Accessing setting files in subfolders of the @c settings directory is currently not supported.
5926 * We can further customize the test run by specifying the following options in the <code>make</code> call:
5933 * \arg <code>LOCK</code> - should the test run be locked to prevent other machines from performing the same test run [default: "false"]
5934 * \arg <code>CONTINUE</code> - continue the test run if it was previously aborted [default: "false"]
5935 * \arg <code>VALGRIND</code> - run valgrind on the SCIP binary; errors and memory leaks found by valgrind are reported as fails [default: "false"]
5940 * Often test runs are performed on the basis of different settings. In this case, it is useful to
5941 * have a performance comparison. For this purpose, we can use the <code>allcmpres.sh</code> script in
5944 * Suppose, we performed our test run with two different settings, say <code>fast.set</code> and
5945 * <code>slow.set</code>. Assuming that all other parameters (including the SCIP binary), were the same,
5946 * we may have the following <code>res</code>-files in the directory <code>scip/check/results/</code>
5960 * in the @c check directory. This produces an ASCII table on the console that provide a detailed
5961 * performance comparison of both test runs. Note that the first <code>res</code>-file serves as reference
5963 * (The term "solver" can be considered as the combination of SCIP with a specific setting file.)
5968 * \arg <code>NodQ</code> - Equals Nodes(i) / Nodes(0), where 'i' denotes the current solver and '0' stands for the reference solver.
5973 * \arg <code>eval</code> - Number of instances evaluated (bounds check = "ok", i.e., solved to optimality
5974 * within the time and memory limit and result is correct). Only these instances are used in the calculation
5992 * \arg <code>gnodes</code> - Geometric mean of the processed nodes over all evaluated instances.
5993 * \arg <code>shnodes</code> - Shifted geometric mean of the processed nodes over all evaluated instances.
5997 * \arg <code>gtime</code> - Geometric mean of the computation time over all evaluated instances.
5998 * \arg <code>shtime</code> - Shifted geometric mean of the computation time over all evaluated instances.
6004 * \arg <code>optimal auto settings</code> - Theoretical result for a solver that performed 'best of all' for every instance.
6005 * \arg <code>diff</code> - Solvers with instances that differ from the reference solver in the number of
|