1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB) */ 7 /* */ 8 /* Licensed under the Apache License, Version 2.0 (the "License"); */ 9 /* you may not use this file except in compliance with the License. */ 10 /* You may obtain a copy of the License at */ 11 /* */ 12 /* http://www.apache.org/licenses/LICENSE-2.0 */ 13 /* */ 14 /* Unless required by applicable law or agreed to in writing, software */ 15 /* distributed under the License is distributed on an "AS IS" BASIS, */ 16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */ 17 /* See the License for the specific language governing permissions and */ 18 /* limitations under the License. */ 19 /* */ 20 /* You should have received a copy of the Apache-2.0 license */ 21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */ 22 /* */ 23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 24 25 /**@file presol_dualsparsify.h 26 * @brief cancel nonzeros of the constraint matrix based on the columns 27 * @author Dieter Weninger 28 * @author Leona Gottwald 29 * @author Ambros Gleixner 30 * @author Weikun Chen 31 * 32 * This presolver attempts to cancel non-zero entries of the constraint 33 * matrix by adding scaled columns to other columns. 34 * 35 * In more detail, for two columns A_{j.} and A_{k.}, suppose for a given value s, we have 36 * 37 * | A_{j.} | - | A_{j.} - s*A_{k.} | > eta, 38 * 39 * where eta is an nonnegative integer. Then we introduce a new variable y := s*x_j + x_k 40 * and aggregate the variable x_k = y - s*x_j. After aggregation, the column of the variable 41 * x_j is A_{j.} + s*A_{j.} which is sparser than A_{j.}. In the case that x_k is no implied 42 * free variable, we need to add a new constraint l_k <= y - weight*x_j <= u_k into the problem 43 * to keep the bounds constraints of variable x_k. 44 * 45 * Further information can be found in 46 * Chen et al. "Two-row and two-column mixed-integer presolve using hasing-based pairing methods". 47 * 48 * @todo add infrastructure to SCIP for handling aggregated binary variables 49 */ 50 51 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 52 53 #ifndef __SCIP_PRESOL_DUALSPARSIFY_H__ 54 #define __SCIP_PRESOL_DUALSPARSIFY_H__ 55 56 #include "scip/def.h" 57 #include "scip/type_retcode.h" 58 #include "scip/type_scip.h" 59 60 #ifdef __cplusplus 61 extern "C" { 62 #endif 63 64 /** creates the dual sparsify presolver and includes it in SCIP */ 65 SCIP_EXPORT 66 SCIP_RETCODE SCIPincludePresolDualsparsify( 67 SCIP* scip /**< SCIP data structure */ 68 ); 69 70 #ifdef __cplusplus 71 } 72 #endif 73 74 #endif 75