SCIP Interview Questions & Answers

  1. Question 1. What Is Scip?

    Answer :

    SCIP is a solver for Mixed Integer Linear and Nonlinear Problems that allows for an easy integration of arbitrary constraints. It can be used as a framework for branch-cut-and-price and contains all necessary plugins to serve as a standalone solver for MIP and MINLP.

    • You can use the precompiled binaries to solve MIPs and MINLPs. Learn more about the file formats supported by SCIP, and get an overview of the supported problem classes and additional recommendations for solving them.
    • You can use SCIP as a subroutine for solving MINLPs and more general constraint integer programs from your own source code.
    • You can use SCIP as a framework in which you implement your own plugins.
    • You can use SCIP in any combination of the three purposes above.
  2. Question 2. When Should I Use Scip?

    Answer :

    If you are either looking for a fast non-commercial MIP/MILP-solver or for a branch-cut-and-price-framework in which you can directly implement your own methods and allows full control of the solving process.

  3. SSIS(SQL Server Integration Services) Interview Questions

  4. Question 3. How Do I Get Started?

    Answer :

    An easy way is to use the SCIP-binaries and call SCIP from a shell, see here for a tutorial. For that, you just have to download one of the precompiled binaries from the download section, or the zipped source code and compile it with your favorite settings. This is described in detail in the INSTALL file in the SCIP main directory.

    Another way is to use SCIP as a solver integrated into your own program source code. See the directories “examples/MIPsolver/” and “examples/Queens/” for simple examples and this point.

    A third way is to implement your own plugins into SCIP. This is explained in the How-to be for all plugin types, which you can find in the doxygen documentation.

  5. Question 4. Do I Need Any Extra Software?

    Answer :

    Unless you want to use SCIP as a pure CP-Solver (see here), you need an underlying LP-Solver installed and linked to the libraries (see the INSTALL file in the SCIP root directory).

    LP-solvers currently supported by SCIP are:

    • SoPlex
    • FICO XPress
    • Gurobi (version at least 7.0.2 required)
    • CLP (interface currently sometimes produces wrong results)
    • Glop, Google OR tools (experimental, LPI contained in OR tools)
    • Mosek
    • QSopt (experimental)

    We also provide some precompiled binaries. Besides that, you might need a modeling language like ZIMPL to generate *.mps or *.lp files. ZIMPL files can also directly be read by SCIP. You can download a package which includes SCIP, SoPlex and ZIMPL here.

    If you want to use SCIP for mixed integer nonlinear programming, you might want to use an underlying NLP solver (e.g., Ipopt). SCIP already comes with the CppAD expression interpreter (e.g., CppAD) as part of the source code.

  6. Question 5. How Can I Debug In Scip?

    Answer :

    Compile SCIP in debug mode: make OPT=dbg. Put the binary into a debugger, e.g., gdb and let it run again. If you get an impression which component is causing the trouble, set #define SCIP_DEBUG as the first line of the corresponding *.c file, recompile and let it run again. This will print debug messages from that piece of code.

  7. Advanced C++ Interview Questions

  8. Question 6. Can I Use Scip As A Pure Cp/sat Solver?

    Answer :

    Yes. SCIP can be used as a pure CP/SAT Solver by typing set emphasis cpsolver in the shell or by using the function SCIPsetEmphasis (). Furthermore, you can compile SCIP without any LP-Solver by make LPS=none.

  9. Question 7. Can I Use Scip As A Pure Lp-solver?

    Answer :

    Since LPs are only special types of MIPs and CIPs, the principal answer is yes. If you feed a pure LP to SCIP, it will first apply presolving and then hand this presolved problem to the underlying LP solver. If the LP is solved to optimality, you can query the optimal solution values as always. You can also access the values of an optimal dual solution by using display dual solution.

    However, there are certain limitations to this: Reduced costs are not accessible. If the LP turns out to be infeasible, you cannot currently obtain a Farkas proof. And recall that this approach is only meaningful if the problem is an LP (no integer variables, only linear constraints).

    Hence, if you need more, “LP specific”, information than the primal solution, you are better off using an LP-Solver directly. If you are using the SCIP Optimization Suite, you could, e.g., use the included LP solver SoPlex. If you want to solve an LP not from the command line, but within your C/C++ program, you could also use SCIP’s LP-Interface.

  10. C and C++ Interview Questions

  11. Question 8. Which Kind Of Minlps Is Supported By Scip?

    Answer :

    SCIP supports nonlinear constraints of the form lhs ≤ f(x) ≤ rhs, where the function f(x) is an algebraic expression that can be represented as expression tree. Such an expression tree has constants and variables as terminal nodes and operands as non-terminal nodes. Expression operands supported by SCIP include addition, subtraction, multiplication, division, exponentiation and logarithm. Trigonometric functions are not yet supported by SCIP.

    Nonlinear objective functions are not supported by SCIP and must be modeled as constraint function. Note, that the support for non-quadratic nonlinear constraints is not yet as robust as the rest of SCIP. Missing bounds on nonlinear variables and tiny or huge coefficients can easily lead to numerical problems, which can be avoided by careful modeling.

  12. Question 9. How Can I Build/compile Scip?

    Answer :

    SCIP can be compiled using either Make files or CMake. It’s recommended to use the new CMake build system both for new and long-time users of SCIP. Consult the CMake documentation for further information about the changes introduced in the new system (like Linux-conform naming conventions for libraries). We still support the traditional Make file system for backwards compatibility but it might be discontinued at some point.

  13. Question 10. What Is This Business With .a And .so Libraries In The Directory Lib?

    Answer :

    When SCIP builds the binary, it needs to link with the corresponding libraries, i.e., its own libraries and those of an LP-solver. There are usually two ways to distribute a library (on UNIX systems). In the first (with suffix “.a”), the library is linked statically to SCIP; this means that all information is packed into the binary. In the second way (with suffix “.so”), the library is a shared library. In this case, the code of the library is not inserted into the binary itself, but is loaded at runtime. This has the advantage that the binaries are smaller, but it comes at the cost that you have to make sure that the library is found at runtime. (SCIP adds rpath information containing the path to the shared libraries to the binary; this usually allows finding these libraries at runtime. If this does not work, for most systems it suffices to put the path of the library into the LD_LIBRARY_PATH environment variable).

    There are compiler-dependent preferences which version should be included if both a static and a shared version of the same library are available. In order to avoid confusion, SCIP separates shared from static libraries into the directories “lib/static” and “lib/shared” when using the Makefile system. Note that some LP-solvers are only shipped with a shared version.

  14. Question 11. Can I Compile Scip As A Shared Library?

    Answer :

    You can use the SHARED=true option when making SCIP. This will generate the libraries of SCIP in shared format. The binary then also uses this form. Note that the path to the lib/shared directory of SCIP is used to locate the libraries. If you want to move the libraries, you might need to set the LD_LIBRARY_PATH environment variable to include the new path. If you are using your own build system: The “magic” changes are the -fPIC compiler/linker option and the -Wl,-rpath option.

  15. Question 12. The Methods Scipgetvarsol () And Scipvargetsol () Seem To Have The Same Functionality. Which One Should I Use?

    Answer :

    In fact, there is a slight difference: SCIPvarGetSol () is also able to return pseudo solution values. If you do not have an idea, what pseudo solutions are, SCIPgetVarSol () should be just fine. This should be the only case of ‘duplicate methods’.

  16. SSIS(SQL Server Integration Services) Interview Questions

  17. Question 13. Is There A Way To Visualize The Branch And Bound Tree?

    Answer :

    Here is a list of external tools that can be used to create interactive and no interactive visualizations in various formats.

    • HyDraw can display a live visualization of the tree using Java View.
    • Vbctool comes with a viewer that has an option to uncover the nodes one-by-one (each time you hit the space key). Additional node information such as its lower bound, depth, and number are accessed through a context menu.
    • Vbc2dot is a script that generates a visualization of SCIP’s branch-and-bound tree in ps and pdf format. It is written in Ruby and requires dot (graphviz).
    • ZimplTblConverter is a small Ruby-script that converts a scip solution file to a file where all names are replaced according to a zimpl tbl-file output.
    • Grumpy is a Python tool that allows creating no interactive visualizations of the tree in various formats.

    For using one of these tools, SCIP lets you define file names set visual vbcfilename somefilename.vbc and set visual bakfilename somefilename.dat. Grumpy uses BAK files while the other tools parse vbc output.

    For those who want to use the step-by-step functionality of vbctool, it is necessary to use a time-step counter for the visualization instead of the real time. The corresponding parameter is changed via set visual realtime FALSE.

    For users of the callable library, the corresponding parameters are called “visual/bakfilename”, “visual/vbcfilename”, and “visual/realtime”.

  18. Question 14. Scip Has Found Decent Primal And Dual Bounds But Still Reports The Gap As “infinity”. Why?

    Answer :

    By default, the SCIP output contains the display column “gap”, which is computed as follows: If primal and dual bound have opposite signs, the gap is “Infinity”. If primal and dual bound have the same sign, the gap is |primal bound – dual bound|/min (|primalbound|,|dualbound|)| (see SCIPgetGap()). This definition has the advantage that the gap decreases monotonously during the solving process.

    An alternative definition of the gap is (dual bound – primal bound) / abs (primal bound). Using this definition, a finite gap is computed as soon as a dual and primal bound have been found. However, the gap may increase during the solving process, if both bounds have opposite signs in the beginning. In SCIP, this definition can be included in the output by enabling the display column “primal gap”: display/primal gap/active = 2

  19. Question 15. Scip Crashes During Symmetry Detection With Bliss. What Can I Do?

    Answer :

    The bliss library can be compiled with or without GMP support. If bliss is compiled with GMP the macro definition BLISS_USE_GMP must be added, otherwise the headers do not match the library which produces the crash. If bliss is compiled as shared library, the CMake system should be able to detect this automatically.

    In case you do not need symmetry handling, the easiest way to resolve the problem is to just disable symmetry handling during compilation (see Make files or CMake) or with the SCIP parameter misc/use symmetry = 0. Otherwise it can be resolved by either adding the macro definition with the compiler flag -DBLISS_USE_GMP or by compiling bliss differently, i.e. without GMP support.

  20. Question 16. The Output Is Too Wide For My Terminal Window. What Can I Do?

    Answer :

    In the interactive shell you can set the width of the output with the following command set display width followed by an appropriate number.

  21. Question 17. What Do The Cryptic Abbreviations For The Columns Mean Which Are Displayed During The Solving Process Of Scip?

    Answer :

    • Type display in the interactive shell to get an explanation of them.
    • By the way: If a letter appears in front of a display row, it indicates, which heuristic found the new primal bound, a star representing an integral LP-relaxation.
    • Typing display statistics after finishing or interrupting the solving process gives you plenty of extra information about the solving process (Typing display heuristics gives you a list of the heuristics including their letters.)
  22. Question 18. Why Does Scip Claim That It Could Not Find The User Parameters “scip. Set”? Where Can I Get Such A File?

    Answer :

    SCIP comes with default settings that are automatically active when you start the interactive shell. However, you have the possibility to save customized settings via the set save and set diffusive commands. Both commands will prompt you to enter a file name and save either all or customized parameters only to the specified file.

    A user parameter file that you save as “scip. Set” has a special meaning; whenever you invoke SCIP from a directory containing a file named “scip. Set”, the settings therein overwrite the default settings. For more information about customized settings, see the Tutorial on the interactive shell. Settings files can become incompatible with later releases if we decide to rename/delete a parameter. Information about this can be found in the CHANGELOG for every release.

  23. Advanced C++ Interview Questions

  24. Question 19. How Do I Change The Behavior Of Scip?

    Answer :

    You can switch the settings for all pre solving, heuristics, and separation plugins to three different modes via the set {pre solving, heuristics, separation} emphasis parameters in the interactive shell. off turns off the respective type of plugins, fast chooses settings that lead to less time spent in this type of plugins, decreasing their impact, and aggressive increases the impact of this type of plugins. You can combine these general settings for cuts, pre solving, and heuristics arbitrarily.

    Display parameters shows you which settings currently differ from their default, set default resets them all. Furthermore, there are complete settings that can be set by set emphasis, i.e. settings for pure feasibility problems, solution counting, and CP like search.

  25. Question 20. How Can I Input A Minlp Into Scip?

    Answer :

    Please consult this overview on the problem classes supported by SCIP and the recommendations and links for MINLPs therein.

  26. Question 21. How Do I Construct A Problem Instance In Scip?

    Answer :

    • For starters, SCIP comes with complete examples in source code that illustrate the problem creation process. Please refer to the examples of the Callable Library section in the Example Documentation of SCIP.
    • First you have to create a SCIP object via SCIPcreate (), then you start to build the problem via SCIPcreate Prob (). Then you create variables via SCIPcreate Var () and add them to the problem via SCIPaddVar ().
    • The same has to be done for the constraints. For example, if you want to fill in the rows of a general MIP, you have to call SCIPcreateConsLinear (), SCIPaddConsLinear () and additionally SCIPreleaseCons () after finishing. If all variables and constraints are present, you can initiate the solution process via SCIPsolve ().
    • Make sure to also call SCIPreleaseVar () if you do not need the variable pointer anymore. For an explanation of creating and releasing objects, please see the notes on releasing objects.
  27. Question 22. What Operational Stages Of Scip Are There And Are They Important For Me?

    Answer :

    There are fourteen different stages during a run of SCIP. There are some methods which cannot be called in all stages, consider

    For Example: SCIP trySol ().

  28. Question 23. What Is The Difference Between The Original And The Transformed Problem?

    Answer :

    Before the solving process starts, the original problem is copied. This copy is called “transformed problem”, and all modifications during the pre solving and solving process are only applied to the transformed problem.

    This has two main advantages: first, the user can also modify the problem after partially solving it. All modifications done by SCIP (pre solving, cuts, and variable fixings) during the partial solving process will be deleted together with the transformed problem; the user can modify the original problem and restart solving. Second, the feasibility of solutions is always tested on the original problem!

  29. Question 24. What Is Scip_call ()? Do I Need This?

    Answer :

    Yes, you do. SCIP_CALL () is a global define, which handles the return codes of all methods which return a SCIP_RETCODE and should therefore parenthesize each such method. SCIP_OKAY is the code which is returned if everything worked well; there are 17 different error codes, see type_retcode.h.

    Each method that calls methods which return a SCIP_RETCODE should itself return a SCIP_RETCODE. If this is not possible, use SCIP_CALL_ABORT () to catch the return codes of the methods. If you do not want to use this either, you have to do the exception handling (i.e. the case that the return code is not SCIP_OKAY) on your own.

  30. C and C++ Interview Questions

  31. Question 25. Is It Possible To Avoid That The Scip Library Overrides My Signal Handler For Interruptions?

    Answer :

    By default, the SCIP library has an internal handler for the handling of the SIGINT signal, which is usually emitted when a user presses CTRL-C during the solution process. In cases where this overrides the signal handling of a surrounding application, this may be undesirable. As a remedy, the parameter misc/catchctrlc can be set to FALSE or the SCIP library can be compiled with the special C compiler flag “-FNO SIGACTION”, both disabling SCIP’s internal signal handling.

  32. Question 26. Can I Remove Unnecessary Display Columns Or—even Better—add My Own Ones? Can I Change The Statistics Displayed At The End Of Solving?

    Answer :

    Setting the status of a display column to 0 turns it off. E.g., type set display memused status 0 in the interactive shell to disable the memory information column, or include the line SCIP setIntParam (scip, “display/memused/status”, 0) into your source code. Adding your own display column can be done by calling the SCIP includeDisp () method, see the doxygen documentation.

    The statistic display, which is shown by display statistics and SCIP print Statistics (), respectively, cannot be changed.

  33. Question 27. What Do Lp-rows Look Like In Scip?

    Answer :

    Each row is of the form lhs ≤ Σ(val[j]•col[j]) + const ≤ rhs. For now, val[j]•col[j] can be interpreted as aij•xj (for the difference between columns and variables see here). The constant is essentially needed for collecting the influence of presolving reductions like variable fixings and aggregations.

    The lhs and rhs may take infinite values: A less-than inequality would have lhs = -∞, and a greater-than inequality would have rhs = +∞. For equations lhs is equal to rhs. An infinite left hand side can be recognized by SCIPisInfinity (scip, -lhs), an infinite right hand side can be recognized by SCIPisInfinity (scip, rhs).

  34. Question 28. What Is The Difference Between Columns And Variables, Rows And Constraints?

    Answer :

    The terms columns and rows always refer to the representation in the current LP-relaxation, variables and constraints to your global Constraint Integer Program.

    Each column has an associated variable, which it represents, but not every variable must be part of the current LP-relaxation. E.g., it could be already fixed, aggregate to another variable, or be priced out if a column generation approach was implemented.

    Each row has either been added to the LP by a constraint handler or by a cutting plane separator. A constraint handler is able to, but does not need to; add one or more rows to the LP as a linear relaxation of each of its constraints. E.g., in the usual case (i.e. without using dynamic rows) the linear constraint handler adds one row to the LP for each linear constraint.

  35. Question 29. Are The Variables And Rows Sorted In Any Particular Order?

    Answer :

    The variable array which you get by SCIPgetVarSol () is internally sorted by variable types. The ordering is binary, integer, implicit integer and continuous variables, i.e., the binary variables are stored at position [0… nbinvars-1], the general integers at [nbinvars… nbinvars+nintvars-1], and so on. It holds that nvars = nbinvars + ninitvars + nimplvars + ncontvars. There is no further sorting within these sections, as well as there is no sorting for the rows. But each column and each row has a unique index, which can be obtained by SCIPcolGetIndex () and SCIPcolGetIndex (), respectively.