Skip to content

Computing Basic Gadgets

A gadget is a finite combinatorial structure that enables the translation of specific constraints from one optimization problem into corresponding constraints of another optimization problem. In this sense, gadgets are local structures designed to simulate components of the source problem inside the target problem, and they serve as the fundamental building blocks from which reductions are constructed.

We assume that the user is familiar with the concept of a gadget. For more information about this subject you can check the following resources: 1 2 3.

Defining Constraints

GadgetoCompiler allows defining custom constraints by inheriting from the Constraint abstract base class. We also provide an implementation for the Clause constraint.

These constraints can be both used as input constraints and as output constraints. For more details about the already-implemented constraints in GadgetoCompiler you can check the API Documentation.

You can find additional examples in the Examples section.

Computing Gadgets Automatically

Once we have the input and output constraints implemented, we can generate a gadget automatically using one of the Gadget Compilers that we have available.

For the example below, we generate a gadget from 3SAT to Max2SAT using the GurobiGadgetoCompiler:

from gadgetocompiler.constraints import Clause
from gadgetocompiler.compilers.gurobi import GurobiGadgetoCompiler

g = GurobiGadgetoCompiler.generate(
    Clause([1, 2, 3]),  # The input constraint
    [(Clause, 2), (Clause, 1)],  # The output family constraints
    alpha_ub=10,  # We must set an upper bound for the alpha
    max_auxs=1,  # As well as the maximum number of aux variables that we will use
)
g.show()

By default, GurobiGadgetoCompiler minimizes the \(\alpha\). We must specify the input constraint, the output family constraints, an upper bound for \(\alpha\) and the maximum number of auxiliary variables that GurobiGadgetoCompiler can use to generate the gadget.

The generated gadget is the following:

Input: 1 2 3
Gadget:
0.50: -1 -2     (Clause)
0.50: 1 2       (Clause)
0.50: 4 -1      (Clause)
0.50: 1 -4      (Clause)
0.50: 4 -2      (Clause)
0.50: 2 -4      (Clause)
1.00: 3 4       (Clause)
Sat_gadget_bounds: (2.5, 3.5)
Beta 4.0

We can verify and analyze the returned gadget using the different Verification Functionalities available in this tool.

  1. Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, and David P. Williamson. Gadgets, approximation, and linear programming. SIAM J. Comput., 29(6):2074–2097, 2000. ↩

  2. Carlos Ansótegui and Jordi Levy. Reducing SAT to max2sat. In Zhi-Hua Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021, 1367–1373. ijcai.org, 2021. ↩

  3. Carlos Ansótegui and Jordi Levy. Sat, gadgets, max2xor, and quantum annealers. Quantum Inf. Process., 24(10):338, 2025. ↩