cutsel_hybrid.h

Go to the documentation of this file.

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/*                                                                           */
/*                  This file is part of the program and library             */
/*         SCIP --- Solving Constraint Integer Programs                      */
/*                                                                           */
/*  Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB)                      */
/*                                                                           */
/*  Licensed under the Apache License, Version 2.0 (the "License");          */
/*  you may not use this file except in compliance with the License.         */
/*  You may obtain a copy of the License at                                  */
/*                                                                           */
/*      http://www.apache.org/licenses/LICENSE-2.0                           */
/*                                                                           */
/*  Unless required by applicable law or agreed to in writing, software      */
/*  distributed under the License is distributed on an "AS IS" BASIS,        */
/*  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
/*  See the License for the specific language governing permissions and      */
/*  limitations under the License.                                           */
/*                                                                           */
/*  You should have received a copy of the Apache-2.0 license                */
/*  along with SCIP; see the file LICENSE. If not visit scipopt.org.         */
/*                                                                           */
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

/**@file   cutsel_hybrid.h
 * @ingroup CUTSELECTORS
 * @brief  hybrid cut selector
 * @author Leona Gottwald
 * @author Felipe Serrano
 * @author Mark Turner
 *
 * The hybrid cut selector scores cuts by using a weighted sum of the efficacy, directed cutoff distance, objective
 * parallelism, and integer support of the cuts. Afterwards, it selects the cuts using the score and filtering for
 * parallelism after selecting each cut.
 *
 * If a cut is given by \f$ a^T x \leq b \f$, then
 *  - the efficacy is defined as the distance between the LP solution and the hyperplane \f$ a^T x = b \f$;
 *  - the directed cutoff distance is defined as the distance between the LP solution and the hyperplane \f$ a^T x = b \f$
 *    restricted to the line segment joining the LP solution to the currently best primal solution; therefore, it is only
 *    defined when a primal solution is available;
 *  - the objective parallelism is how parallel the vector \f$ a \f$ is w.r.t. the objective function \f$ c \f$. That
 *    is, the objective parallelism is given by \f$ \frac{a^T c}{\|a\| \|c\|} \f$. Notice that the vectors are parallel
 *    when this formula returns 1;
 *  - the integer support of a cut is the ratio between the number of nonzero integer columns and the number of nonzero
 *    columns.
 *
 * These features of a cut can be recovered and/or computed with the functions @ref SCIPgetCutEfficacy(), @ref
 * SCIPgetCutLPSolCutoffDistance(), @ref SCIPgetRowObjParallelism(), and @ref SCIPgetRowNumIntCols(), @ref
 * SCIProwGetNNonz().
 *
 * The filtering step works as follows.
 * After computing the scores, these are divided in two groups: good scores and bad scores.  Any score larger or equal
 * to 90% of the largest score is considered a good score.
 *
 * First, the forced cuts --- cuts that are going to enter the LP no matter what --- are used to filter the non-forced
 * cuts. This means that for each forced cut, @p fcut, the parallelism between @p fcut and
 * every non-forced cut, @p cut, is computed (the parallelism between two cuts \f$ a^T x \leq b \f$ and \f$ d^T x \leq e\f$
 * is \f$ \frac{a^T d}{\|a\| \|d\|} \f$).
 * If the score of cut is good, then cut is dropped if its parallelism with @p fcut is larger or equal than the maximum
 * between \f$ \frac{1}{2} \f$ and 1 - minimum orthogonality.
 * If the score of cut is not good, then cut is dropped if its parallelism with @p fcut is larger or equal than 1 - minimum
 * orthogonality.
 *
 * @note The minimum orthogonality is a parameter that can be set, as well as the weights for the score.
 *
 * @note In the case of no primal solution, the weight assigned to the directed cutoff distance is transfered to the
 * efficacy.
 */

/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/

#ifndef __SCIP_CUTSEL_HYBRID_H__
#define __SCIP_CUTSEL_HYBRID_H__


#include "scip/scip.h"

#ifdef __cplusplus
extern "C" {
#endif

/** creates the hybrid separator and includes it in SCIP
 *
 * @ingroup CutSelectorIncludes
 */
SCIP_EXPORT
SCIP_RETCODE SCIPincludeCutselHybrid(
   SCIP*                 scip                /**< SCIP data structure */
   );

/**@addtogroup CUTSELECTORS
 *
 * @{
 */

/** perform a cut selection algorithm for the given array of cuts
 *
 *  This is the selection method of the hybrid cut selector which uses a weighted sum of the
 *  efficacy, parallelism, directed cutoff distance, and the integral support.
 *  The input cuts array gets resorted s.t the selected cuts come first and the remaining
 *  ones are the end.
 */
SCIP_EXPORT
SCIP_RETCODE SCIPselectCutsHybrid(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_ROW**            cuts,               /**< array with cuts to perform selection algorithm */
   SCIP_ROW**            forcedcuts,         /**< array with forced cuts */
   SCIP_RANDNUMGEN*      randnumgen,         /**< random number generator for tie-breaking, or NULL */
   SCIP_Real             goodscorefac,       /**< factor of best score among the given cuts to consider a cut good
                                              *   and filter with less strict settings of the maximum parallelism */
   SCIP_Real             badscorefac,        /**< factor of best score among the given cuts to consider a cut bad
                                              *   and discard it regardless of its parallelism to other cuts */
   SCIP_Real             goodmaxparall,      /**< maximum parallelism for good cuts */
   SCIP_Real             maxparall,          /**< maximum parallelism for non-good cuts */
   SCIP_Real             dircutoffdistweight,/**< weight of directed cutoff distance in cut score calculation */
   SCIP_Real             efficacyweight,     /**< weight of efficacy in cut score calculation */
   SCIP_Real             objparalweight,     /**< weight of objective parallelism in cut score calculation */
   SCIP_Real             intsupportweight,   /**< weight of integral support in cut score calculation */
   int                   ncuts,              /**< number of cuts in cuts array */
   int                   nforcedcuts,        /**< number of forced cuts */
   int                   maxselectedcuts,    /**< maximal number of cuts from cuts array to select */
   int*                  nselectedcuts       /**< pointer to return number of selected cuts from cuts array */
   );

/** @} */

#ifdef __cplusplus
}
#endif

#endif