Scippy

SCIP

Solving Constraint Integer Programs

type_pricer.h
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2024 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 type_pricer.h
26 * @ingroup TYPEDEFINITIONS
27 * @brief type definitions for variable pricers
28 * @author Tobias Achterberg
29 */
30
31/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32
33#ifndef __SCIP_TYPE_PRICER_H__
34#define __SCIP_TYPE_PRICER_H__
35
36#include "scip/def.h"
37#include "scip/type_retcode.h"
38#include "scip/type_scip.h"
39
40#ifdef __cplusplus
41extern "C" {
42#endif
43
44typedef struct SCIP_Pricer SCIP_PRICER; /**< variable pricer data */
45typedef struct SCIP_PricerData SCIP_PRICERDATA; /**< locally defined variable pricer data */
46
47
48/** copy method for pricer plugins (called when SCIP copies plugins)
49 *
50 * input:
51 * - scip : SCIP main data structure
52 * - pricer : the variable pricer itself
53 * - valid : was the copying process valid?
54 */
55#define SCIP_DECL_PRICERCOPY(x) SCIP_RETCODE x (SCIP* scip, SCIP_PRICER* pricer, SCIP_Bool* valid)
56
57/** destructor of variable pricer to free user data (called when SCIP is exiting)
58 *
59 * input:
60 * - scip : SCIP main data structure
61 * - pricer : the variable pricer itself
62 */
63#define SCIP_DECL_PRICERFREE(x) SCIP_RETCODE x (SCIP* scip, SCIP_PRICER* pricer)
64
65/** initialization method of variable pricer (called after problem was transformed and pricer is active)
66 *
67 * input:
68 * - scip : SCIP main data structure
69 * - pricer : the variable pricer itself
70 */
71#define SCIP_DECL_PRICERINIT(x) SCIP_RETCODE x (SCIP* scip, SCIP_PRICER* pricer)
72
73/** deinitialization method of variable pricer (called before transformed problem is freed and pricer is active)
74 *
75 * input:
76 * - scip : SCIP main data structure
77 * - pricer : the variable pricer itself
78 */
79#define SCIP_DECL_PRICEREXIT(x) SCIP_RETCODE x (SCIP* scip, SCIP_PRICER* pricer)
80
81/** solving process initialization method of variable pricer (called when branch and bound process is about to begin)
82 *
83 * This method is called when the presolving was finished and the branch and bound process is about to begin.
84 * The variable pricer may use this call to initialize its branch and bound specific data.
85 *
86 * input:
87 * - scip : SCIP main data structure
88 * - pricer : the variable pricer itself
89 */
90#define SCIP_DECL_PRICERINITSOL(x) SCIP_RETCODE x (SCIP* scip, SCIP_PRICER* pricer)
91
92/** solving process deinitialization method of variable pricer (called before branch and bound process data is freed)
93 *
94 * This method is called before the branch and bound process is freed.
95 * The variable pricer should use this call to clean up its branch and bound data.
96 *
97 * input:
98 * - scip : SCIP main data structure
99 * - pricer : the variable pricer itself
100 */
101#define SCIP_DECL_PRICEREXITSOL(x) SCIP_RETCODE x (SCIP* scip, SCIP_PRICER* pricer)
102
103/** reduced cost pricing method of variable pricer for feasible LPs
104 *
105 * Searches for variables that can contribute to improve the current LP's solution value.
106 * In standard branch-and-price, these are variables with negative dual feasibility, that is negative
107 * reduced costs for non-negative variables, positive reduced costs for non-positive variables,
108 * and non-zero reduced costs for variables that can be negative and positive.
109 *
110 * The method is called in the LP solving loop after an LP was proven to be feasible.
111 *
112 * Whenever the pricer finds a variable with negative dual feasibility, it should call SCIPcreateVar()
113 * and SCIPaddPricedVar() to add the variable to the problem. Furthermore, it should call the appropriate
114 * methods of the constraint handlers to add the necessary variable entries to the constraints.
115 *
116 * In the usual case that the pricer either adds a new variable or ensures that there are no further variables with
117 * negative dual feasibility, the result pointer should be set to SCIP_SUCCESS. Only if the pricer aborts pricing
118 * without creating a new variable, but there might exist additional variables with negative dual feasibility, the
119 * result pointer should be set to SCIP_DIDNOTRUN. In this case, which sometimes is referred to as "early branching",
120 * the lp solution will not be used as a lower bound. The pricer can, however, store a valid lower bound in the
121 * lowerbound pointer. If you use your own branching rule (e.g., to branch on constraints), make sure that it is able
122 * to branch on pseudo solutions. Otherwise, SCIP will use its default branching rules (which all branch on
123 * variables). This could disturb the pricing problem or branching might not even be possible, e.g., if all yet created
124 * variables have already been fixed.
125 *
126 * input:
127 * - scip : SCIP main data structure
128 * - pricer : the variable pricer itself
129 * - lowerbound : pointer to store a lower bound found by the pricer
130 * - stopearly : should pricing be stopped, although new variables were added? (doing early branching)
131 * - result : pointer to store the result of the pricer call
132 *
133 * possible return values for *result:
134 * - SCIP_SUCCESS : at least one improving variable was found, or it is ensured that no such variable exists
135 * - SCIP_DIDNOTRUN : the pricing process was aborted by the pricer, there is no guarantee that the current LP solution is
136 * optimal
137 *
138 */
139#define SCIP_DECL_PRICERREDCOST(x) SCIP_RETCODE x (SCIP* scip, SCIP_PRICER* pricer, SCIP_Real* lowerbound, SCIP_Bool* stopearly, SCIP_RESULT* result)
140
141/** Farkas pricing method of variable pricer for infeasible LPs
142 *
143 * Searches for variables that can contribute to the feasibility of the current LP.
144 * In standard branch-and-price, these are variables with positive Farkas values:
145 *
146 * The LP was proven infeasible, so we have an infeasibility proof by the dual Farkas multipliers y.
147 * With the values of y, an implicit inequality y^T A x >= y^T b is associated, with b given
148 * by the sides of the LP rows and the sign of y:
149 * - if y_i is positive, b_i is the left hand side of the row,
150 * - if y_i is negative, b_i is the right hand side of the row.
151 *
152 * y is chosen in a way, such that the valid inequality y^T A x >= y^T b is violated by all x,
153 * especially by the (for this inequality least infeasible solution) x' defined by
154 * x'_i := ub_i, if y^T A_i >= 0
155 * x'_i := lb_i, if y^T A_i < 0.
156 * Pricing in this case means to add variables i with positive Farkas value, i.e. y^T A_i x'_i > 0.
157 *
158 * The method is called in the LP solving loop after an LP was proven to be infeasible.
159 *
160 * Whenever the pricer finds a variable with positive Farkas value, it should call SCIPcreateVar()
161 * and SCIPaddPricedVar() to add the variable to the problem. Furthermore, it should call the appropriate
162 * methods of the constraint handlers to add the necessary variable entries to the constraints.
163 *
164 * input:
165 * - scip : SCIP main data structure
166 * - pricer : the variable pricer itself
167 * - result : pointer to store the result of the pricer call
168 *
169 * possible return values for *result:
170 * - SCIP_SUCCESS : at least one variable was found, which can contribute to the feasibility of the current LP,
171 * or it is ensured that no such variable exists
172 * - SCIP_DIDNOTRUN : the pricing process was aborted by the pricer, there is no guarantee that the current LP is indeed infeasible
173 */
174#define SCIP_DECL_PRICERFARKAS(x) SCIP_RETCODE x (SCIP* scip, SCIP_PRICER* pricer, SCIP_RESULT* result)
175
176#ifdef __cplusplus
177}
178#endif
179
180#endif
def.h
common defines and data types used in all packages of SCIP
SCIP_Pricer
Definition: struct_pricer.h:47
SCIP_PRICERDATA
struct SCIP_PricerData SCIP_PRICERDATA
Definition: type_pricer.h:45
type_retcode.h
type definitions for return codes for SCIP methods
type_scip.h
type definitions for SCIP's main datastructure