ViolationLS is a new a Constraint-Based Local Search (CBLS) solver developed by Google's Operations Research team based on the Feasibility Jump Mixed-Integer Programming Heuristic. It uses a novel approach for finding multi-variable moves without requiring any “implicit” or “one-way” constraints traditionally used by CBLS solvers. The new solver significantly outperforms other Local Search solvers on the MiniZinc challenge Constraint Programming benchmarks, both with and without multi-variable moves. ViolationLS is integrated into the parallel portfolio framework of the state-of-the-art CP-SAT Lazy Clause Generation Constraint Programming solver.

This talk introduces MathOpt, a software tool for modeling mathematical optimization problems (e.g., linear programs). MathOpt is part of Google's open source project OR-Tools and is used extensively within Google. MathOpt provides client libraries in various programming languages (including C++, Python, and Java) to build your optimization model, and then solves your model with a supported solver (e.g., Gurobi, SCIP, CP-SAT, GLOP, PDLP). A unified API solves models in process, in a subprocess, or remotely by HTTP or gRPC, which we refer to as execution independent solving. MathOpt supports many advanced features, including nonlinear constraints, duality, rays, LP basis, incremental solves, callbacks, and many solve parameters, all with solver independence and execution independence. The core library of MathOpt (and the C++ client) are written in portable C++ and can run on servers, mobile devices, or even in the browser via WASM. For non-C++ languages, the model building code in the client library is written entirely in that language. As a result, users solving by HTTP or gRPC can quickly get started without installing any C/C++ dependencies. Further, Google provides a (currently) free service for solving MathOpt models remotely.

The Operations Research API aims to solve high-level operations research problems using linear programming, mixed integer programming, constraint programming and more. It provides optimization solutions for specific problems to external users through REST or gRPC calls (details at https://developers.google.com/optimization/service). In this talk, we present the current API functionalities and discuss some of the software engineering advantages to using such an API.

We describe and discuss the duality contracts of OR-Tools' newest modeling language MathOpt. We study how these contracts can be used for testing of solvers that include linear and quadratic objectives, together with linear, conic and convex quadratic constraints. We also discuss how these contracts lead to abstract oracle-based decomposition methods.