Solving Constraint Integer Programs

Detailed Description

Generates a no-good cut for solutions that are integer infeasible.

Stephen J. Maher

The no-good cut is generated for the Benders' decomposition master problem if an integer solution is identified as infeasible in at least one CIP subproblems. The no-good cut is required, because the classical Benders' decomposition feasibility cuts (see benderscut_feas.c) will only cut off the solution \(\bar{x}\) if the LP relaxation of the CIP is infeasible.

Consider a Benders' decomposition subproblem that is a CIP and it infeasible. Let \(S_{r}\) be the set of indices for master problem variables that are 1 in \(\bar{x}\). The no-good cut is given by

\[ 1 \leq \sum_{i \in S_{r}}(1 - x_{i}) + \sum_{i \notin S_{r}}x_{i} \]

Definition in file benderscut_nogood.h.

#include "scip/def.h"
#include "scip/type_benders.h"
#include "scip/type_retcode.h"
#include "scip/type_scip.h"

Go to the source code of this file.


SCIP_RETCODE SCIPincludeBenderscutNogood (SCIP *scip, SCIP_BENDERS *benders)