Use SCIP to solve a problem

Why SCIP?

Charlotte lectures at a university and she wants her students to get in touch with solving constraint integer programs (CIPs). She would like to use SCIP for this purpose because it allows the students to look at the full source code and SCIP comes with a permissive open source license. Also, her advisor told her that there are various interfaces to SCIP.

What Kinds Of Problems?

As a first step she checks what types of problems SCIP can solve and what are readable formats, and is happy to find MIPs to be among them.

Setup

Charlotte now needs to install SCIP. She works on a recent computer with a windows system and already has the Visual C++ Redistributable Packages and TBB installed.

Having these prerequisites in place, Charlotte downloads the 64-bit windows exectuable from the download page and installs it without a problem. They also read about the dockerized SCIP container which she wants to recommend to her students, in case they are unable to install SCIP on their own machines.

Solve A First Problem

To test her installation and get a first feeling for SCIP, Charlotte follows the steps described in the quickstart section to solve a first simple lp problem.

She has just solved a problem, using SCIP in the command-based mode, by passing a command to the scip call via the -c flag. These commands can also be typed into the interactive shell, that one uses by just calling the binary scip.

After the first solution process worked like a charm, Charlotte downloads a more complicated problem file from the MIPLIB 2017 page and follows the interactive shell tutorial. There, she already learns quite a lot about the solving process and how to work with the interactive shell.

Getting Help

Feeling happy about having already solved some instances and having worked in interactive mode, Charlotte is curious on what more options SCIP has. She types scip -h to find out.

She feels confident to being able to understand and use some of the other options, like -l to write the output to a logfile, or -b to pass a file containing the commands to be executed by scip. There are some commands that do not yet make a lot of sense to her, but she doesn't worry about it for now. She will familiarize herself with it over time and with experience.

Develop A Custom Plugin

Alex is a researcher in Charlotte's group and is working on problems that have a very special structure that he hopes to be able to exploit in the solving process.

Alex heard Charlotte talk about SCIP. She explained that SCIP is plugin-based, that is, different components (plugins) are implemented using a generic interface and that it is very easy to write your own plugins, like constraint handlers, heuristics etc. So Alex decides to give it a go and dive into SCIP.

Prerequisites And Setup

After some time of using SCIP, he feels confident enough to dig into the source code and decides to write his own plugin. Alex likes to use his linux machine for developing code, because in his experience compilation is easiest there.

He starts by downloading the latest source code tarball, unpacking it and compiling via cmake, typing mkdir build; cd build; cmake ..; make.

Getting help

Before writing any code, he quickly scans over the contents of the Programming with SCIP page, so that he knows about some of the pitfalls, best practices and mechanisms. If a problem comes up later or he gets stuck, he knows what to look out for and where to find help.

Whenever Alex gets stuck inside the code, he makes use of the extensive documentation to search for interface methods.

Writing An Example

Alex is now ready to write his very first example, he creates a new folder MinEx under examples and puts two files in there: CMakeLists.txt:

cmake_minimum_required(VERSION 3.3)
 
project(minex)
find_package(SCIP REQUIRED)
include_directories(${SCIP_INCLUDE_DIRS})
 
add_executable(minex
  src/cmain.c)
 
target_link_libraries(minex ${SCIP_LIBRARIES})
 
if( TARGET examples )
    add_dependencies( examples minex )
endif()

and cmain.c in a subfolder src:

#include <string.h>
#include <scip/scip.h>
 
int main( int argc, char** argv )
{
   SCIP* scip = NULL;
   SCIP_CALL( SCIPcreate(&scip) ); // initialize SCIP
   SCIPinfoMessage(scip, NULL, "Hello world.\n"); // output greeting
   SCIP_CALL( SCIPfree(&scip) ); // free SCIP
   BMScheckEmptyMemory();
   return 0;
}

This is a minimal example that just prints "Hello world." and exits. Alex compiles and runs it via cmake with the following command:

mkdir build; cd build; cmake .. -DSCIP_DIR=../../build/; make; ./minex

After having successfully written this minimal example, Alex follows the instructions to start a new project to start his actual project and extend this most basic code.

Writing A Plugin

Alex now needs a custom constraint handler in his project, for that he will write a custom plugin. He looks up the instructions in the How to add... page and is very happy to find a page with a detailed description what he has to do.

Furthermore he found exercises for implementing plugins for the example of the linear ordering problem. The corresponding code framework (Python or C/C++) could form a good starting point for a new project as well.

Using Functionality In A Plugin

After implementing his own constraint handler Alex realizes that he needs to use repotimization in his project. He looks up the How to use... section and finds some more information about how to use reoptimization.