Pseudo-Boolean problems optimize or satisfy linear and polynomial constraints with integer coefficients over {0,1} variables, and can be recast as pure binary integer linear programs by turning each monomial into an AND constraint and each relaxable constraint into an indicator constraint. Students learn how a constraint-integer-programming solver attacks that reformulation: separating reformulation-linearization cuts from products hidden in AND constraints, separating k-flower inequalities over the hypergraph of multilinear constraints, detecting and breaking permutation and reflection symmetries with orbitopal and orbital fixing, and deriving conflict constraints from the linear constraints themselves rather than from extracted clauses. It also covers the exactness engineering this demands -- absolute rather than relative feasibility tolerances, rounding before feasibility checks, and integer-only heuristics for coefficients too large for floating point -- and how independent differently-parametrized solver runs are raced in parallel instead of splitting one branch-and-bound tree.
A Pseudo-Boolean problem constrains n Boolean {0,1} variables by linear or polynomial inequalities with integer coefficients, and asks either for a feasible assignment, for the minimum of a linear ob…