Fast, Constrained Optimization in the Browser with SCIP

By Jacob Strieb.

Published on December 13, 2024.

Introduction

In June 2024, I released Poker Chipper, a web application that uses mixed-integer, nonlinear programming to optimally select poker chip denominations for cash games. In that project, I used a very fast solver called SCIP to power the constrained optimization.¹

Poker Chipper runs entirely client-side in the user’s browser, which means it does not talk to any back end server (except to load static files from GitHub Pages).² As a result, I had to get SCIP (a C/C++ application designed to run natively) working in the browser, so I could call it from my JavaScript front end code. To run SCIP in the browser, I used the Emscripten compiler to cross-compile the optimizer’s core C and C++ code to WebAssembly (WASM).

Try It

Input a constrained optimization problem formulation below, and SCIP will solve it locally, in your browser. SCIP accepts several different formats as input, depending on the mathematical properties of the problem you are trying to optimize:

• The LP format is very common and fairly easy to read, but not very expressive
  • The example constraint file below is in the LP format
  • The POLIP format seems to be an extension of the LP format
• The MPS format is “industry-standard” according to a lot of sources, but it’s quite old, and hard to read
• The ZIMPL format is affiliated with SCIP, and seems very expressive, if a little verbose
• The CIP format is the most powerful, but the least documented
  • SCIP can be used to convert other problems to CIP format by using the display problem command and viewing the results in the “logs” area below

No solution.

No logs.

Use It

If you want to use the WebAssembly port of SCIP to do optimization in your own web application, you can either download the pre-compiled files from the Poker Chipper repository, or you can hotlink the compiled code in a <script type="module"> tag on your site.

import createSCIP from "https://jstrieb.github.io/poker-chipper/assets/scip.js";

createSCIP({ arguments: ["-q", "-c", "quit"] })
  .then(({FS, callMain: main}) => {
    // Input your problem as text
    const problem = "";
    FS.writeFile("model.lp", problem);
    // Perform optimization and write results to the console
    main(["-f", "model.lp"]);
  });

Usage Notes

To use SCIP effectively in a web application, I recommend running it inside a web worker. Web workers are the closest thing the web has to subprocesses. They can make code more complex, but it is worthwhile if the solver has long-running computations. Running the solver outside a web worker will block the main thread, and therefore freeze the user interface for however long it takes the solver to complete.

Like all solvers, SCIP can take a while to perform optimization. Users may want to abort a running solve to start a new one (if input data changes, for example). Unfortunately, there is no standard mechanism for sending the equivalent of Unix signals to WebAssembly programs. The only reliable way to stop the solver is to kill the web worker running it, and start a new one.

If you run SCIP inside of a web worker, I recommend using a service worker to cache assets from the back end. For security reasons, web workers cannot use the normal HTTP cache.³ As a result, they re-download the multi-megabyte WASM and JavaScript files every time a new worker starts up, which can negatively impact the application’s perceived speed. This is exacerbated if users have slow Internet, or are on a limited data plan. A service worker that provides caching can speed up web worker startup, as well as overall application responsiveness.

For more information, and for a concrete implementation example, check out the architecture of Poker Chipper, which is outlined in a diagram in the project README file. Alternatively, view the source of this page, and find the <script type="module"> tag.

Cross-compile It

The remainder of the post contains information about how to cross-compile the WebAssembly version of SCIP yourself.⁴

At the time I was experimenting with cross-compiling SCIP, I did the builds in a Dockerfile, which is included below.⁵

FROM debian:bookworm-slim

# Install dependencies
RUN apt-get update \
  && apt-get install -y python3 python3-pip cmake git curl zip unzip tar automake autoconf libtool pkg-config

# Install a pinned version of the Emscripten compiler
WORKDIR /
RUN git clone https://github.com/emscripten-core/emsdk.git
WORKDIR /emsdk
RUN ./emsdk install 3.1.56 \
  && ./emsdk activate 3.1.56 \
  && echo '. "/emsdk/emsdk_env.sh"' >> /root/.bashrc

ENV PATH="/emsdk:/emsdk/upstream/emscripten:${PATH}"

# Download the SCIP sources
WORKDIR /
RUN curl 'https://scipopt.org/download/release/scipoptsuite-8.1.0.tgz' | tar -xvz

# Set flags and perform compilation
WORKDIR /scipoptsuite-8.1.0
ENV CXXFLAGS="-sINVOKE_RUN=0 -sFILESYSTEM=1 -sFORCE_FILESYSTEM=1 -sMODULARIZE=1 -sEXPORT_NAME=createSCIP -sEXPORTED_RUNTIME_METHODS=FS,callMain -sEXPORT_ES6=1 -sWASM=2 -sEXCEPTION_STACK_TRACES=1 -sDISABLE_EXCEPTION_CATCHING=0"
RUN mkdir build \
  && cd build \
  && emcmake cmake .. -DNO_EXTERNAL_CODE=on -DBUILD_TESTING=off \
  && make -j

CMD ["sleep", "infinity"]

The full sequence of commands to run the build process and copy the SCIP files out of the Docker image follows.

# Download the Dockerfile
curl \
  --remote-name \
  --location \
  https://github.com/jstrieb/poker-chipper/raw/master/experiments/Dockerfile

# Do compilation (this may take a while)
docker build --tag scip:latest .

# Copy the compiled files out of the image
docker run --rm --interactive --tty --detach --name scip scip:latest
for f in scip.js scip.js.mem scip.wasm scip.wasm.js; do 
  docker cp "scip:/scipoptsuite-8.1.0/build/bin/${f}" .
done
docker kill scip

The CXXFLAGS and CMake arguments used in the Dockerfile are of particular interest.

Though some possible options for CXXFLAGS are enumerated in the Emscripten documentation, at the time I originally compiled this code, many of them were only documented in a settings.js file in the Emscripten repository.⁶ For each option in that file, I decided whether to override the default value. The final argument -sDISABLE_EXCEPTION_CATCHING=0 fixed cases where SCIP was silently and inexplicably failing.⁷

The two additional flags passed to CMake (-DNO_EXTERNAL_CODE=on and -DBUILD_TESTING=off) are essential to cross-compile SCIP successfully. Without them, the build system will try to build optional dependencies for SCIP that are, themselves, error-prone to cross-compile for WebAssembly. Eliding all additional dependencies simplifies the compilation process.

The NO_EXTERNAL_CODE CMake argument does not seem to be documented anywhere in the SCIP docs. It’s also not in the CMakeLists.txt file in the core SCIP repo. It is, however, included in the CMakeLists.txt file that comes with the source tarball downloaded directly from the SCIP project website. A relevant snippet of that file is included below.

if(NOT NO_EXTERNAL_CODE)
   option(AUTOBUILD "find and use dependencies on availability (ignores PAPILO, IPOPT, ZLIB, GMP, PAPILO, ZIMPL, READLINE, WORHP flags)" OFF)
   option(PAPILO "should papilo library be linked" ON)
   option(ZIMPL "should zimpl be linked" ON)
   option(GMP "should GMP be linked" ON)
   option(GCG "should GCG be included" ON)
   option(UG "should ug be included" ON)
   option(BOOST "Use Boost (required to build the binary). Disable if you only want to build libsoplex." ON)
else()
   option(PAPILO "should papilo library be linked" OFF)
   option(ZIMPL "should zimpl be linked" OFF)
   option(GMP "should GMP be linked" OFF)
   option(GCG "should GCG be included" OFF)
   option(UG "should ug be included" OFF)
   option(ZLIB "should zlib be linked" OFF)
   option(READLINE "should readline be linked" OFF)
   option(IPOPT "should ipopt be linked" OFF)
   option(WORHP "should worhp be linked" OFF)
   option(BOOST "Use Boost (required to build the binary). Disable if you only want to build libsoplex." OFF)
   option(QUADMATH "should quadmath library be used" OFF)
   option(MPFR "Use MPFR" OFF)
   set(SYM none CACHE STRING "options for symmetry computation")
endif()