SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
conflict_dualproofanalysis.c
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 conflict_dualproofanalysis.c
26 * @ingroup OTHER_CFILES
27 * @brief internal methods for dual proof conflict analysis
28 * @author Timo Berthold
29 * @author Jakob Witzig
30 *
31 * In dual proof analysis, an infeasible LP relaxation is analysed.
32 * Using the dual solution, a valid constraint is derived that is violated
33 * by all values in the domain. This constraint is added to the problem
34 * and can then be used for domain propagation. More details can be found in [1]
35 *
36 * [1] J. Witzig, T. Berthold, en S. Heinz, ‘Computational aspects of infeasibility analysis in mixed integer programming’,
37 * Math. Prog. Comp., mrt. 2021, doi: 10.1007/s12532-021-00202-0.
38 */
39
40/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
41
42#include "lpi/lpi.h"
43#include "scip/clock.h"
46#include "scip/conflictstore.h"
47#include "scip/cons.h"
48#include "scip/cons_linear.h"
49#include "scip/cuts.h"
50#include "scip/history.h"
51#include "scip/lp.h"
52#include "scip/presolve.h"
53#include "scip/prob.h"
54#include "scip/prop.h"
55#include "scip/pub_conflict.h"
56#include "scip/pub_cons.h"
57#include "scip/pub_lp.h"
58#include "scip/pub_message.h"
59#include "scip/pub_misc.h"
60#include "scip/pub_misc_sort.h"
61#include "scip/pub_paramset.h"
62#include "scip/pub_prop.h"
63#include "scip/pub_tree.h"
64#include "scip/pub_var.h"
65#include "scip/scip_conflict.h"
66#include "scip/scip_cons.h"
67#include "scip/scip_mem.h"
68#include "scip/scip_sol.h"
69#include "scip/scip_var.h"
70#include "scip/set.h"
71#include "scip/sol.h"
73#include "scip/struct_lp.h"
74#include "scip/struct_prob.h"
75#include "scip/struct_set.h"
76#include "scip/struct_stat.h"
77#include "scip/struct_tree.h"
78#include "scip/struct_var.h"
79#include "scip/tree.h"
80#include "scip/var.h"
81#include "scip/visual.h"
82
83#define BOUNDSWITCH 0.51 /**< threshold for bound switching - see cuts.c */
84#define POSTPROCESS FALSE /**< apply postprocessing to the cut - see cuts.c */
85#define USEVBDS FALSE /**< use variable bounds - see cuts.c */
86#define ALLOWLOCAL FALSE /**< allow to generate local cuts - see cuts. */
87#define MINFRAC 0.05 /**< minimal fractionality of floor(rhs) - see cuts.c */
88#define MAXFRAC 0.999 /**< maximal fractionality of floor(rhs) - see cuts.c */
89
90
91/*
92 * Proof Sets
93 */
94
95/** return the char associated with the type of the variable */
96static
98 SCIP_VAR* var /**< variable */
99 )
100{
102
103 return (!SCIPvarIsIntegral(var) ? 'C' :
104 (vartype == SCIP_VARTYPE_BINARY ? 'B' :
105 (vartype == SCIP_VARTYPE_INTEGER ? 'I' : 'M')));
106}
107
108/** resets the data structure of a proofset */
109static
111 SCIP_PROOFSET* proofset /**< proof set */
112 )
113{
114 assert(proofset != NULL);
115
116 proofset->nnz = 0;
117 proofset->rhs = 0.0;
118 proofset->validdepth = 0;
120}
121
122/** creates a proofset */
123static
125 SCIP_PROOFSET** proofset, /**< proof set */
126 BMS_BLKMEM* blkmem /**< block memory of transformed problem */
127 )
128{
129 assert(proofset != NULL);
130
131 SCIP_ALLOC( BMSallocBlockMemory(blkmem, proofset) );
132 (*proofset)->vals = NULL;
133 (*proofset)->inds = NULL;
134 (*proofset)->rhs = 0.0;
135 (*proofset)->nnz = 0;
136 (*proofset)->size = 0;
137 (*proofset)->validdepth = 0;
138 (*proofset)->conflicttype = SCIP_CONFTYPE_UNKNOWN;
139
140 return SCIP_OKAY;
141}
142
143/** frees a proofset */
145 SCIP_PROOFSET** proofset, /**< proof set */
146 BMS_BLKMEM* blkmem /**< block memory */
147 )
148{
149 assert(proofset != NULL);
150 assert(*proofset != NULL);
151 assert(blkmem != NULL);
152
153 BMSfreeBlockMemoryArrayNull(blkmem, &(*proofset)->vals, (*proofset)->size);
154 BMSfreeBlockMemoryArrayNull(blkmem, &(*proofset)->inds, (*proofset)->size);
155 BMSfreeBlockMemory(blkmem, proofset);
156 (*proofset) = NULL;
157}
158
159/** return the indices of variables in the proofset */
160static
162 SCIP_PROOFSET* proofset /**< proof set */
163 )
164{
165 assert(proofset != NULL);
166
167 return proofset->inds;
168}
169
170/** return coefficient of variable in the proofset with given probindex */
171static
173 SCIP_PROOFSET* proofset /**< proof set */
174 )
175{
176 assert(proofset != NULL);
177
178 return proofset->vals;
179}
180
181/** return the right-hand side if a proofset */
182static
184 SCIP_PROOFSET* proofset /**< proof set */
185 )
186{
187 assert(proofset != NULL);
188
189 return proofset->rhs;
190}
191
192/** returns the number of variables in the proofset */
194 SCIP_PROOFSET* proofset /**< proof set */
195 )
196{
197 assert(proofset != NULL);
198
199 return proofset->nnz;
200}
201
202/** returns the number of variables in the proofset */
203static
205 SCIP_PROOFSET* proofset /**< proof set */
206 )
207{
208 assert(proofset != NULL);
209
210 return proofset->conflicttype;
211}
212
213/** adds given data as aggregation row to the proofset */
214static
216 SCIP_PROOFSET* proofset, /**< proof set */
217 BMS_BLKMEM* blkmem, /**< block memory */
218 SCIP_Real* vals, /**< variable coefficients */
219 int* inds, /**< variable array */
220 int nnz, /**< size of variable and coefficient array */
221 SCIP_Real rhs /**< right-hand side of the aggregation row */
222 )
223{
224 assert(proofset != NULL);
225 assert(blkmem != NULL);
226
227 if( proofset->size == 0 )
228 {
229 assert(proofset->vals == NULL);
230 assert(proofset->inds == NULL);
231
232 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &proofset->vals, vals, nnz) );
233 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &proofset->inds, inds, nnz) );
234
235 proofset->size = nnz;
236 }
237 else
238 {
239 int i;
240
241 assert(proofset->vals != NULL);
242 assert(proofset->inds != NULL);
243
244 if( proofset->size < nnz )
245 {
246 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &proofset->vals, proofset->size, nnz) );
247 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &proofset->inds, proofset->size, nnz) );
248 proofset->size = nnz;
249 }
250
251 for( i = 0; i < nnz; i++ )
252 {
253 proofset->vals[i] = vals[i];
254 proofset->inds[i] = inds[i];
255 }
256 }
257
258 proofset->rhs = rhs;
259 proofset->nnz = nnz;
260
261 return SCIP_OKAY;
262}
263
264/** adds an aggregation row to the proofset */
265static
267 SCIP_PROOFSET* proofset, /**< proof set */
268 SCIP_SET* set, /**< global SCIP settings */
269 BMS_BLKMEM* blkmem, /**< block memory */
270 SCIP_AGGRROW* aggrrow /**< aggregation row to add */
271 )
272{
273 SCIP_Real* vals;
274 int* inds;
275 int nnz;
276 int i;
277
278 assert(proofset != NULL);
279 assert(set != NULL);
280
281 inds = SCIPaggrRowGetInds(aggrrow);
282 assert(inds != NULL);
283
284 nnz = SCIPaggrRowGetNNz(aggrrow);
285 assert(nnz > 0);
286
287 SCIP_CALL( SCIPsetAllocBufferArray(set, &vals, nnz) );
288
289 for( i = 0; i < nnz; i++ )
290 {
291 vals[i] = SCIPaggrRowGetProbvarValue(aggrrow, inds[i]);
292 }
293
294 SCIP_CALL( proofsetAddSparseData(proofset, blkmem, vals, inds, nnz, SCIPaggrRowGetRhs(aggrrow)) );
295
297
298 return SCIP_OKAY;
299}
300
301/** Removes a given variable @p var from position @p pos from the proofset and updates the right-hand side according
302 * to sign of the coefficient, i.e., rhs -= coef * bound, where bound = lb if coef >= 0 and bound = ub, otherwise.
303 *
304 * @note: The list of non-zero indices and coefficients will be updated by swapping the last non-zero index to @p pos.
305 */
306static
308 SCIP_PROOFSET* proofset,
309 SCIP_SET* set,
310 SCIP_VAR* var,
311 int pos,
312 SCIP_Bool* valid
313 )
314{
315 assert(proofset != NULL);
316 assert(var != NULL);
317 assert(pos >= 0 && pos < proofset->nnz);
318 assert(valid != NULL);
319
320 *valid = TRUE;
321
322 /* cancel with lower bound */
323 if( proofset->vals[pos] > 0.0 )
324 {
325 proofset->rhs -= proofset->vals[pos] * SCIPvarGetLbGlobal(var);
326 }
327 /* cancel with upper bound */
328 else
329 {
330 assert(proofset->vals[pos] < 0.0);
331 proofset->rhs -= proofset->vals[pos] * SCIPvarGetUbGlobal(var);
332 }
333
334 --proofset->nnz;
335
336 proofset->vals[pos] = proofset->vals[proofset->nnz];
337 proofset->inds[pos] = proofset->inds[proofset->nnz];
338 proofset->vals[proofset->nnz] = 0.0;
339 proofset->inds[proofset->nnz] = 0;
340
341 if( SCIPsetIsInfinity(set, proofset->rhs) )
342 *valid = FALSE;
343}
344
345/** creates and clears the proofset */
347 SCIP_CONFLICT* conflict, /**< conflict analysis data */
348 BMS_BLKMEM* blkmem /**< block memory of transformed problem */
349 )
350{
351 assert(conflict != NULL);
352 assert(blkmem != NULL);
353
354 SCIP_CALL( proofsetCreate(&conflict->proofset, blkmem) );
355
356 return SCIP_OKAY;
357}
358
359/** resizes proofsets array to be able to store at least num entries */
360static
362 SCIP_CONFLICT* conflict, /**< conflict analysis data */
363 SCIP_SET* set, /**< global SCIP settings */
364 int num /**< minimal number of slots in array */
365 )
366{
367 assert(conflict != NULL);
368 assert(set != NULL);
369
370 if( num > conflict->proofsetssize )
371 {
372 int newsize;
373
376 conflict->proofsetssize = newsize;
377 }
378 assert(num <= conflict->proofsetssize);
379
380 return SCIP_OKAY;
381}
382
383/** add a proofset to the list of all proofsets */
384static
386 SCIP_CONFLICT* conflict, /**< conflict analysis data */
387 SCIP_SET* set, /**< global SCIP settings */
388 SCIP_PROOFSET* proofset /**< proof set to add */
389 )
390{
391 assert(conflict != NULL);
392 assert(proofset != NULL);
393
394 /* insert proofset into the sorted proofsets array */
395 SCIP_CALL( conflictEnsureProofsetsMem(conflict, set, conflict->nproofsets + 1) );
396
397 conflict->proofsets[conflict->nproofsets] = proofset;
398 ++conflict->nproofsets;
399
400 return SCIP_OKAY;
401}
402
403/** tighten the bound of a singleton variable in a constraint
404 *
405 * if the bound is contradicting with a global bound we cannot tighten the bound directly.
406 * in this case we need to create and add a constraint of size one such that propagating this constraint will
407 * enforce the infeasibility.
408 */
409static
411 SCIP_CONFLICT* conflict, /**< conflict analysis data */
412 SCIP_SET* set, /**< global SCIP settings */
413 SCIP_STAT* stat, /**< dynamic SCIP statistics */
414 SCIP_TREE* tree, /**< tree data */
415 BMS_BLKMEM* blkmem, /**< block memory */
416 SCIP_PROB* origprob, /**< original problem */
417 SCIP_PROB* transprob, /**< transformed problem */
418 SCIP_REOPT* reopt, /**< reoptimization data */
419 SCIP_LP* lp, /**< LP data */
420 SCIP_BRANCHCAND* branchcand, /**< branching candidates */
421 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
422 SCIP_CLIQUETABLE* cliquetable, /**< clique table */
423 SCIP_VAR* var, /**< problem variable */
424 SCIP_Real val, /**< coefficient of the variable */
425 SCIP_Real rhs, /**< rhs of the constraint */
426 SCIP_CONFTYPE prooftype, /**< type of the proof */
427 int validdepth /**< depth where the bound change is valid */
428 )
429{
430 SCIP_Real newbound;
431 SCIP_Bool applyglobal;
432 SCIP_BOUNDTYPE boundtype;
433
434 assert(tree != NULL);
435 assert(validdepth >= 0);
436
437 applyglobal = (validdepth <= SCIPtreeGetEffectiveRootDepth(tree));
438
439 /* if variable and coefficient are integral the rhs can be rounded down */
441 newbound = SCIPsetFeasFloor(set, rhs)/val;
442 else
443 newbound = rhs/val;
444
445 boundtype = (val > 0.0 ? SCIP_BOUNDTYPE_UPPER : SCIP_BOUNDTYPE_LOWER);
446 SCIPvarAdjustBd(var, set, boundtype, &newbound);
447
448 /* skip numerical unstable bound changes */
449 if( applyglobal
450 && ((boundtype == SCIP_BOUNDTYPE_LOWER && SCIPsetIsLE(set, newbound, SCIPvarGetLbGlobal(var)))
451 || (boundtype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsGE(set, newbound, SCIPvarGetUbGlobal(var)))) )
452 {
453 return SCIP_OKAY;
454 }
455
456 /* the new bound contradicts a global bound, we can cutoff the root node immediately */
457 if( applyglobal
458 && ((boundtype == SCIP_BOUNDTYPE_LOWER && SCIPsetIsGT(set, newbound, SCIPvarGetUbGlobal(var)))
459 || (boundtype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsLT(set, newbound, SCIPvarGetLbGlobal(var)))) )
460 {
461 SCIPsetDebugMsg(set, "detected global infeasibility at var <%s>: locdom=[%g,%g] glbdom=[%g,%g] new %s bound=%g\n",
464 (boundtype == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper"), newbound);
465 SCIP_CALL( SCIPnodeCutoff(tree->path[0], set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
466 }
467 else
468 {
469 if( lp->strongbranching || !applyglobal )
470 {
471 SCIP_CONS* cons;
472 SCIP_Real conslhs;
473 SCIP_Real consrhs;
474 char name[SCIP_MAXSTRLEN];
475
476 SCIPsetDebugMsg(set, "add constraint <%s>[%c] %s %g to node #%lld in depth %d\n",
477 SCIPvarGetName(var), varGetChar(var), boundtype == SCIP_BOUNDTYPE_UPPER ? "<=" : ">=", newbound,
478 SCIPnodeGetNumber(tree->path[validdepth]), validdepth);
479
480 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "pc_fix_%s", SCIPvarGetName(var));
481
482 if( boundtype == SCIP_BOUNDTYPE_UPPER )
483 {
485 consrhs = newbound;
486 }
487 else
488 {
489 conslhs = newbound;
491 }
492
493 SCIP_CALL( SCIPcreateConsLinear(set->scip, &cons, name, 0, NULL, NULL, conslhs, consrhs,
495
496 SCIP_CALL( SCIPaddCoefLinear(set->scip, cons, var, 1.0) );
497
498 if( applyglobal ) /*lint !e774*/
499 {
500 SCIP_CALL( SCIPprobAddCons(transprob, set, stat, cons) );
501 }
502 else
503 {
504 SCIP_CALL( SCIPnodeAddCons(tree->path[validdepth], blkmem, set, stat, tree, cons) );
505 }
506
507 SCIP_CALL( SCIPconsRelease(&cons, blkmem, set) );
508 }
509 else
510 {
512
513 SCIPsetDebugMsg(set, "change global %s bound of <%s>[%c]: %g -> %g\n",
514 (boundtype == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper"),
517 newbound);
518
519 SCIP_CALL( SCIPnodeAddBoundchg(tree->path[0], blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, \
520 eventqueue, cliquetable, var, newbound, boundtype, FALSE) );
521
522 /* mark the node in the validdepth to be propagated again */
523 SCIPnodePropagateAgain(tree->path[0], set, stat, tree);
524 }
525 }
526
527 if( applyglobal )
528 ++conflict->nglbchgbds;
529 else
530 ++conflict->nlocchgbds;
531
533 {
534 ++conflict->dualproofsinfnnonzeros; /* we count a global bound reduction as size 1 */
535 ++conflict->ndualproofsinfsuccess;
536 ++conflict->ninflpsuccess;
537
538 if( applyglobal )
539 ++conflict->ndualproofsinfglobal;
540 else
541 ++conflict->ndualproofsinflocal;
542 }
543 else
544 {
545 ++conflict->dualproofsbndnnonzeros; /* we count a global bound reduction as size 1 */
546 ++conflict->ndualproofsbndsuccess;
547 ++conflict->nboundlpsuccess;
548
549 if( applyglobal )
550 ++conflict->ndualproofsbndglobal;
551 else
552 ++conflict->ndualproofsbndlocal;
553 }
554
555 return SCIP_OKAY;
556}
557
558/** calculates the minimal activity of a given set of bounds and coefficients */
559static
561 SCIP_SET* set, /**< global SCIP settings */
562 SCIP_PROB* transprob, /**< transformed problem data */
563 SCIP_Real* coefs, /**< coefficients in sparse representation */
564 int* inds, /**< non-zero indices */
565 int nnz, /**< number of non-zero indices */
566 SCIP_Real* curvarlbs, /**< current lower bounds of active problem variables (or NULL for global bounds) */
567 SCIP_Real* curvarubs /**< current upper bounds of active problem variables (or NULL for global bounds) */
568 )
569{
570 SCIP_VAR** vars;
571 SCIP_Real QUAD(minact);
572 int i;
573
574 assert(coefs != NULL);
575 assert(inds != NULL);
576
577 vars = SCIPprobGetVars(transprob);
578 assert(vars != NULL);
579
580 QUAD_ASSIGN(minact, 0.0);
581
582 for( i = 0; i < nnz; i++ )
583 {
584 SCIP_Real val;
585 SCIP_Real QUAD(delta);
586 int v = inds[i];
587
589
590 val = coefs[i];
591
592 if( val > 0.0 )
593 {
594 SCIP_Real bnd;
595
597
599
600 if( SCIPsetIsInfinity(set, -bnd) )
601 return -SCIPsetInfinity(set);
602
603 SCIPquadprecProdDD(delta, val, bnd);
604 }
605 else
606 {
607 SCIP_Real bnd;
608
610
612
614 return -SCIPsetInfinity(set);
615
616 SCIPquadprecProdDD(delta, val, bnd);
617 }
618
619 /* update minimal activity */
621 }
622
623 /* check whether the minmal activity is infinite */
625 return SCIPsetInfinity(set);
627 return -SCIPsetInfinity(set);
628
629 return QUAD_TO_DBL(minact);
630}
631
632/** calculates the minimal activity of a given set of bounds and coefficients */
633static
635 SCIP_SET* set, /**< global SCIP settings */
636 SCIP_PROB* transprob, /**< transformed problem data */
637 SCIP_Real* coefs, /**< coefficients in sparse representation */
638 int* inds, /**< non-zero indices */
639 int nnz, /**< number of non-zero indices */
640 SCIP_Real* curvarlbs, /**< current lower bounds of active problem variables (or NULL for global bounds) */
641 SCIP_Real* curvarubs /**< current upper bounds of active problem variables (or NULL for global bounds) */
642 )
643{
644 SCIP_VAR** vars;
645 SCIP_Real QUAD(maxact);
646 int i;
647
648 assert(coefs != NULL);
649 assert(inds != NULL);
650
651 vars = SCIPprobGetVars(transprob);
652 assert(vars != NULL);
653
654 QUAD_ASSIGN(maxact, 0.0);
655
656 for( i = 0; i < nnz; i++ )
657 {
658 SCIP_Real val;
659 SCIP_Real QUAD(delta);
660 int v = inds[i];
661
663
664 val = coefs[i];
665
666 if( val < 0.0 )
667 {
668 SCIP_Real bnd;
669
671
673
674 if( SCIPsetIsInfinity(set, -bnd) )
675 return SCIPsetInfinity(set);
676
677 SCIPquadprecProdDD(delta, val, bnd);
678 }
679 else
680 {
681 SCIP_Real bnd;
682
684
686
688 return SCIPsetInfinity(set);
689
690 SCIPquadprecProdDD(delta, val, bnd);
691 }
692
693 /* update maximal activity */
695 }
696
697 /* check whether the maximal activity got infinite */
699 return SCIPsetInfinity(set);
701 return -SCIPsetInfinity(set);
702
703 return QUAD_TO_DBL(maxact);
704}
705
706/** propagate a long proof */
707static
709 SCIP_CONFLICT* conflict, /**< conflict analysis data */
710 SCIP_SET* set, /**< global SCIP settings */
711 SCIP_STAT* stat, /**< dynamic SCIP statistics */
712 SCIP_REOPT* reopt, /**< reoptimization data */
713 SCIP_TREE* tree, /**< tree data */
714 BMS_BLKMEM* blkmem, /**< block memory */
715 SCIP_PROB* origprob, /**< original problem */
716 SCIP_PROB* transprob, /**< transformed problem */
717 SCIP_LP* lp, /**< LP data */
718 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
719 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
720 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
721 SCIP_Real* coefs, /**< coefficients in sparse representation */
722 int* inds, /**< non-zero indices */
723 int nnz, /**< number of non-zero indices */
724 SCIP_Real rhs, /**< right-hand side */
725 SCIP_CONFTYPE conflicttype, /**< type of the conflict */
726 int validdepth /**< depth where the proof is valid */
727 )
728{
729 SCIP_VAR** vars;
730 SCIP_Real minact;
731 int i;
732
733 assert(coefs != NULL);
734 assert(inds != NULL);
735 assert(nnz >= 0);
736
737 vars = SCIPprobGetVars(transprob);
738 minact = getMinActivity(set, transprob, coefs, inds, nnz, NULL, NULL);
739
740 /* we cannot find global tightenings */
742 return SCIP_OKAY;
743
744 for( i = 0; i < nnz; i++ )
745 {
746 SCIP_VAR* var;
747 SCIP_Real val;
748 SCIP_Real resminact;
749 SCIP_Real lb;
750 SCIP_Real ub;
751 int pos;
752
753 pos = inds[i];
754 val = coefs[i];
755 var = vars[pos];
758
759 assert(!SCIPsetIsZero(set, val));
760
762
763 /* we got a potential new upper bound */
764 if( val > 0.0 )
765 {
766 SCIP_Real newub;
767
768 resminact -= (val * lb);
769 newub = (rhs - resminact)/val;
770
772 continue;
773
774 /* we cannot tighten the upper bound */
775 if( SCIPsetIsGE(set, newub, ub) )
776 continue;
777
778 SCIP_CALL( tightenSingleVar(conflict, set, stat, tree, blkmem, origprob, transprob, reopt, lp, branchcand, \
779 eventqueue, cliquetable, var, val, rhs-resminact, conflicttype, validdepth) );
780 }
781 /* we got a potential new lower bound */
782 else
783 {
784 SCIP_Real newlb;
785
786 resminact -= (val * ub);
787 newlb = (rhs - resminact)/val;
788
790 continue;
791
792 /* we cannot tighten the lower bound */
793 if( SCIPsetIsLE(set, newlb, lb) )
794 continue;
795
796 SCIP_CALL( tightenSingleVar(conflict, set, stat, tree, blkmem, origprob, transprob, reopt, lp, branchcand, \
797 eventqueue, cliquetable, var, val, rhs-resminact, conflicttype, validdepth) );
798 }
799
800 /* the minimal activity should stay unchanged because we tightened the bound that doesn't contribute to the
801 * minimal activity
802 */
803 assert(SCIPsetIsEQ(set, minact, getMinActivity(set, transprob, coefs, inds, nnz, NULL, NULL)));
804 }
805
806 return SCIP_OKAY;
807}
808
809/** creates a proof constraint and tries to add it to the storage */
810static
812 SCIP_CONFLICT* conflict, /**< conflict analysis data */
813 SCIP_CONFLICTSTORE* conflictstore, /**< conflict pool data */
814 SCIP_PROOFSET* proofset, /**< proof set */
815 SCIP_SET* set, /**< global SCIP settings */
816 SCIP_STAT* stat, /**< dynamic SCIP statistics */
817 SCIP_PROB* origprob, /**< original problem */
818 SCIP_PROB* transprob, /**< transformed problem */
819 SCIP_TREE* tree, /**< tree data */
820 SCIP_REOPT* reopt, /**< reoptimization data */
821 SCIP_LP* lp, /**< LP data */
822 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
823 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
824 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
825 BMS_BLKMEM* blkmem /**< block memory */
826 )
827{
828 SCIP_CONS* cons;
830 SCIP_VAR** vars;
831 SCIP_Real* coefs;
832 int* inds;
833 SCIP_Real rhs;
834 SCIP_Real fillin;
835 SCIP_Real globalminactivity;
836 SCIP_Bool applyglobal;
837 SCIP_Bool toolong;
838 SCIP_Bool contonly;
839 SCIP_Bool hasrelaxvar;
840 SCIP_CONFTYPE conflicttype;
841 char name[SCIP_MAXSTRLEN];
842 int nnz;
843 int i;
844
845 assert(conflict != NULL);
846 assert(conflictstore != NULL);
847 assert(proofset != NULL);
848 assert(proofset->validdepth == 0 || proofset->validdepth < SCIPtreeGetFocusDepth(tree));
849
850 nnz = SCIPproofsetGetNVars(proofset);
851
852 if( nnz == 0 )
853 return SCIP_OKAY;
854
855 vars = SCIPprobGetVars(transprob);
856
857 rhs = proofsetGetRhs(proofset);
859
860 coefs = proofsetGetVals(proofset);
861 assert(coefs != NULL);
862
863 inds = proofsetGetInds(proofset);
864 assert(inds != NULL);
865
866 conflicttype = proofsetGetConftype(proofset);
867
869
870 if( applyglobal )
871 {
872 SCIP_Real globalmaxactivity = getMaxActivity(set, transprob, coefs, inds, nnz, NULL, NULL);
873
874 /* check whether the alternative proof is redundant */
876 return SCIP_OKAY;
877
878 /* check whether the constraint proves global infeasibility */
879 globalminactivity = getMinActivity(set, transprob, coefs, inds, nnz, NULL, NULL);
881 {
882 SCIPsetDebugMsg(set, "detect global infeasibility: minactivity=%g, rhs=%g\n", globalminactivity, rhs);
883
884 SCIP_CALL( SCIPnodeCutoff(tree->path[proofset->validdepth], set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
885
886 goto UPDATESTATISTICS;
887 }
888 }
889
890 if( set->conf_minmaxvars >= nnz )
891 toolong = FALSE;
892 else
893 {
894 SCIP_Real maxnnz;
895
896 if( transprob->startnconss < 100 )
897 maxnnz = 0.85 * transprob->nvars;
898 else
899 maxnnz = (SCIP_Real)transprob->nvars;
900
901 fillin = nnz;
902 if( conflicttype == SCIP_CONFTYPE_INFEASLP || conflicttype == SCIP_CONFTYPE_ALTINFPROOF )
903 {
905 fillin /= (SCIPconflictstoreGetNDualInfProofs(conflictstore) + 1.0);
906 toolong = (fillin > MIN(2.0 * stat->avgnnz, maxnnz));
907 }
908 else
909 {
910 assert(conflicttype == SCIP_CONFTYPE_BNDEXCEEDING || conflicttype == SCIP_CONFTYPE_ALTBNDPROOF);
911
913 fillin /= (SCIPconflictstoreGetNDualBndProofs(conflictstore) + 1.0);
914 toolong = (fillin > MIN(1.5 * stat->avgnnz, maxnnz));
915 }
916
917 toolong = (toolong && (nnz > set->conf_maxvarsfac * transprob->nvars));
918 }
919
920 /* don't store global dual proofs that are too long / have too many non-zeros */
921 if( toolong )
922 {
923 if( applyglobal )
924 {
925 SCIP_CALL( propagateLongProof(conflict, set, stat, reopt, tree, blkmem, origprob, transprob, lp, branchcand,
926 eventqueue, cliquetable, coefs, inds, nnz, rhs, conflicttype, proofset->validdepth) );
927 }
928 return SCIP_OKAY;
929 }
930
931 /* check if conflict contains variables that are invalid after a restart to label it appropriately */
933 contonly = TRUE;
934 for( i = 0; i < nnz && (!hasrelaxvar || contonly); ++i )
935 {
937
938 if( SCIPvarIsIntegral(vars[inds[i]]) )
939 contonly = FALSE;
940 }
941
942 if( !applyglobal && contonly )
943 return SCIP_OKAY;
944
945 if( conflicttype == SCIP_CONFTYPE_INFEASLP || conflicttype == SCIP_CONFTYPE_ALTINFPROOF )
946 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "dualproof_inf_%" SCIP_LONGINT_FORMAT, conflict->ndualproofsinfsuccess);
947 else if( conflicttype == SCIP_CONFTYPE_BNDEXCEEDING || conflicttype == SCIP_CONFTYPE_ALTBNDPROOF )
948 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "dualproof_bnd_%" SCIP_LONGINT_FORMAT, conflict->ndualproofsbndsuccess);
949 else
950 return SCIP_INVALIDCALL;
951
952 SCIP_CALL( SCIPcreateConsLinear(set->scip, &cons, name, 0, NULL, NULL, -SCIPsetInfinity(set), rhs,
954 FALSE, TRUE, TRUE, FALSE) );
955
956 for( i = 0; i < nnz; i++ )
957 {
958 int v = inds[i];
959 SCIP_CALL( SCIPaddCoefLinear(set->scip, cons, vars[v], coefs[i]) );
960 }
961
962 /* do not upgrade linear constraints of size 1 */
963 if( nnz > 1 )
964 {
965 upgdcons = NULL;
966 /* try to automatically convert a linear constraint into a more specific and more specialized constraint */
968 if( upgdcons != NULL )
969 {
970 SCIP_CALL( SCIPreleaseCons(set->scip, &cons) );
971 cons = upgdcons;
972
973 if( conflicttype == SCIP_CONFTYPE_INFEASLP )
974 conflicttype = SCIP_CONFTYPE_ALTINFPROOF;
975 else if( conflicttype == SCIP_CONFTYPE_BNDEXCEEDING )
976 conflicttype = SCIP_CONFTYPE_ALTBNDPROOF;
977 }
978 }
979
980 /* mark constraint to be a conflict */
982
983 /* add constraint to storage */
984 if( conflicttype == SCIP_CONFTYPE_INFEASLP || conflicttype == SCIP_CONFTYPE_ALTINFPROOF )
985 {
986 /* add dual proof to storage */
987 SCIP_CALL( SCIPconflictstoreAddDualraycons(conflictstore, cons, blkmem, set, stat, transprob, reopt, hasrelaxvar) );
988 }
989 else
990 {
991 SCIP_Real scale = 1.0;
992 SCIP_Bool updateside = FALSE;
993
994 /* In some cases the constraint could not be updated to a more special type. However, it is possible that
995 * constraint got scaled. Therefore, we need to be very careful when updating the lhs/rhs after the incumbent
996 * solution has improved.
997 */
998 if( conflicttype == SCIP_CONFTYPE_BNDEXCEEDING )
999 {
1000 SCIP_Real side;
1001
1002#ifndef NDEBUG
1003 SCIP_CONSHDLR* conshdlr = SCIPconsGetHdlr(cons);
1004
1005 assert(conshdlr != NULL);
1006 assert(strcmp(SCIPconshdlrGetName(conshdlr), "linear") == 0);
1007#endif
1008 side = SCIPgetLhsLinear(set->scip, cons);
1009
1010 if( !SCIPsetIsInfinity(set, -side) )
1011 {
1012 if( SCIPsetIsZero(set, side) )
1013 {
1014 scale = -1.0;
1015 }
1016 else
1017 {
1018 scale = proofsetGetRhs(proofset) / side;
1019 assert(SCIPsetIsNegative(set, scale));
1020 }
1021 }
1022 else
1023 {
1024 side = SCIPgetRhsLinear(set->scip, cons);
1025 assert(!SCIPsetIsInfinity(set, side));
1026
1027 if( SCIPsetIsZero(set, side) )
1028 {
1029 scale = 1.0;
1030 }
1031 else
1032 {
1033 scale = proofsetGetRhs(proofset) / side;
1034 assert(SCIPsetIsPositive(set, scale));
1035 }
1036 }
1037 updateside = TRUE;
1038 }
1039
1040 /* add dual proof to storage */
1041 SCIP_CALL( SCIPconflictstoreAddDualsolcons(conflictstore, cons, blkmem, set, stat, transprob, reopt, scale, updateside, hasrelaxvar) );
1042 }
1043
1044 if( applyglobal ) /*lint !e774*/
1045 {
1046 /* add the constraint to the global problem */
1047 SCIP_CALL( SCIPprobAddCons(transprob, set, stat, cons) );
1048 }
1049 else
1050 {
1051 SCIP_CALL( SCIPnodeAddCons(tree->path[proofset->validdepth], blkmem, set, stat, tree, cons) );
1052 }
1053
1054 SCIPsetDebugMsg(set, "added proof-constraint to node %p (#%lld) in depth %d (nproofconss %d)\n",
1055 (void*)tree->path[proofset->validdepth], SCIPnodeGetNumber(tree->path[proofset->validdepth]),
1056 proofset->validdepth,
1057 (conflicttype == SCIP_CONFTYPE_INFEASLP || conflicttype == SCIP_CONFTYPE_ALTINFPROOF)
1059
1060 /* release the constraint */
1061 SCIP_CALL( SCIPreleaseCons(set->scip, &cons) );
1062
1064 /* update statistics */
1065 if( conflicttype == SCIP_CONFTYPE_INFEASLP || conflicttype == SCIP_CONFTYPE_ALTINFPROOF )
1066 {
1067 conflict->dualproofsinfnnonzeros += nnz;
1068 if( applyglobal ) /*lint !e774*/
1069 ++conflict->ndualproofsinfglobal;
1070 else
1071 ++conflict->ndualproofsinflocal;
1072 ++conflict->ndualproofsinfsuccess;
1073 }
1074 else
1075 {
1076 assert(conflicttype == SCIP_CONFTYPE_BNDEXCEEDING || conflicttype == SCIP_CONFTYPE_ALTBNDPROOF);
1077 conflict->dualproofsbndnnonzeros += nnz;
1078 if( applyglobal ) /*lint !e774*/
1079 ++conflict->ndualproofsbndglobal;
1080 else
1081 ++conflict->ndualproofsbndlocal;
1082
1083 ++conflict->ndualproofsbndsuccess;
1084 }
1085 return SCIP_OKAY;
1086}
1087
1088/** create proof constraints out of proof sets */
1090 SCIP_CONFLICT* conflict, /**< conflict analysis data */
1091 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
1092 BMS_BLKMEM* blkmem, /**< block memory */
1093 SCIP_SET* set, /**< global SCIP settings */
1094 SCIP_STAT* stat, /**< dynamic problem statistics */
1095 SCIP_PROB* transprob, /**< transformed problem after presolve */
1096 SCIP_PROB* origprob, /**< original problem */
1097 SCIP_TREE* tree, /**< branch and bound tree */
1098 SCIP_REOPT* reopt, /**< reoptimization data structure */
1099 SCIP_LP* lp, /**< current LP data */
1100 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1101 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1102 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
1103 )
1104{
1105 assert(conflict != NULL);
1106
1108 {
1109 /* only one variable has a coefficient different to zero, we add this bound change instead of a constraint */
1110 if( SCIPproofsetGetNVars(conflict->proofset) == 1 )
1111 {
1112 SCIP_VAR** vars;
1113 SCIP_Real* coefs;
1114 int* inds;
1115 SCIP_Real rhs;
1116
1117 vars = SCIPprobGetVars(transprob);
1118
1119 coefs = proofsetGetVals(conflict->proofset);
1120 inds = proofsetGetInds(conflict->proofset);
1121 rhs = proofsetGetRhs(conflict->proofset);
1122
1123 SCIP_CALL( tightenSingleVar(conflict, set, stat, tree, blkmem, origprob, transprob, reopt, lp, \
1124 branchcand, eventqueue, cliquetable, vars[inds[0]], coefs[0], rhs, conflict->proofset->conflicttype,
1125 conflict->proofset->validdepth) );
1126 }
1127 else
1128 {
1129 SCIP_Bool skipinitialproof = FALSE;
1130
1131 /* prefer an infeasibility proof
1132 *
1133 * todo: check whether this is really what we want
1134 */
1135 if( set->conf_prefinfproof && proofsetGetConftype(conflict->proofset) == SCIP_CONFTYPE_BNDEXCEEDING )
1136 {
1137 int i;
1138
1139 for( i = 0; i < conflict->nproofsets; i++ )
1140 {
1142 {
1144 break;
1145 }
1146 }
1147 }
1148
1149 if( !skipinitialproof )
1150 {
1151 /* create and add the original proof */
1152 SCIP_CALL( createAndAddProofcons(conflict, conflictstore, conflict->proofset, set, stat, origprob, transprob, \
1153 tree, reopt, lp, branchcand, eventqueue, cliquetable, blkmem) );
1154 }
1155 }
1156
1157 /* clear the proof set anyway */
1158 proofsetClear(conflict->proofset);
1159 }
1160
1161 if( conflict->nproofsets > 0 )
1162 {
1163 int i;
1164
1165 for( i = 0; i < conflict->nproofsets; i++ )
1166 {
1167 assert(conflict->proofsets[i] != NULL);
1169
1170 /* only one variable has a coefficient different to zero, we add this bound change instead of a constraint */
1171 if( SCIPproofsetGetNVars(conflict->proofsets[i]) == 1 )
1172 {
1173 SCIP_VAR** vars;
1174 SCIP_Real* coefs;
1175 int* inds;
1176 SCIP_Real rhs;
1177
1178 vars = SCIPprobGetVars(transprob);
1179
1180 coefs = proofsetGetVals(conflict->proofsets[i]);
1181 inds = proofsetGetInds(conflict->proofsets[i]);
1182 rhs = proofsetGetRhs(conflict->proofsets[i]);
1183
1184 SCIP_CALL( tightenSingleVar(conflict, set, stat, tree, blkmem, origprob, transprob, reopt, lp,
1185 branchcand, eventqueue, cliquetable, vars[inds[0]], coefs[0], rhs,
1186 conflict->proofsets[i]->conflicttype, conflict->proofsets[i]->validdepth) );
1187 }
1188 else
1189 {
1190 /* create and add proof constraint */
1191 SCIP_CALL( createAndAddProofcons(conflict, conflictstore, conflict->proofsets[i], set, stat, origprob, \
1192 transprob, tree, reopt, lp, branchcand, eventqueue, cliquetable, blkmem) );
1193 }
1194 }
1195
1196 /* free all proofsets */
1197 for( i = 0; i < conflict->nproofsets; i++ )
1198 SCIPproofsetFree(&conflict->proofsets[i], blkmem);
1199
1200 conflict->nproofsets = 0;
1201 }
1202
1203 return SCIP_OKAY;
1204}
1205
1206
1207
1208#ifdef SCIP_DEBUG
1209/** print violation for debugging */
1210static
1212 SCIP_SET* set, /**< global SCIP settings */
1213 SCIP_Real minact, /**< min activity */
1214 SCIP_Real rhs, /**< right hand side */
1215 const char* infostr /**< additional info for this debug message, or NULL */
1216 )
1217{
1218 SCIPsetDebugMsg(set, "-> %sminact=%.15g rhs=%.15g violation=%.15g\n",infostr != NULL ? infostr : "" , minact, rhs, minact - rhs);
1219}
1220#else
1221#define debugPrintViolationInfo(...) /**/
1222#endif
1223
1224/** apply coefficient tightening */
1225static
1227 SCIP_SET* set, /**< global SCIP settings */
1228 SCIP_PROOFSET* proofset, /**< proof set */
1229 int* nchgcoefs, /**< pointer to store number of changed coefficients */
1230 SCIP_Bool* redundant /**< pointer to store whether the proof set is redundant */
1231 )
1232{
1233#ifdef SCIP_DEBUG
1234 SCIP_Real absmax = 0.0;
1235 SCIP_Real absmin = SCIPsetInfinity(set);
1236 int i;
1237
1238 for( i = 0; i < proofset->nnz; i++ )
1239 {
1240 absmax = MAX(absmax, REALABS(proofset->vals[i]));
1241 absmin = MIN(absmin, REALABS(proofset->vals[i]));
1242 }
1243#endif
1244
1245 (*redundant) = SCIPcutsTightenCoefficients(set->scip, FALSE, proofset->vals, &proofset->rhs, proofset->inds, &proofset->nnz, nchgcoefs);
1246
1247#ifdef SCIP_DEBUG
1248 {
1249 SCIP_Real newabsmax = 0.0;
1250 SCIP_Real newabsmin = SCIPsetInfinity(set);
1251
1252 for( i = 0; i < proofset->nnz; i++ )
1253 {
1254 newabsmax = MAX(newabsmax, REALABS(proofset->vals[i]));
1255 newabsmin = MIN(newabsmin, REALABS(proofset->vals[i]));
1256 }
1257
1258 SCIPsetDebugMsg(set, "coefficient tightening: [%.15g,%.15g] -> [%.15g,%.15g] (nnz: %d, nchg: %d rhs: %.15g)\n",
1259 absmin, absmax, newabsmin, newabsmax, SCIPproofsetGetNVars(proofset), *nchgcoefs, proofsetGetRhs(proofset));
1260 printf("coefficient tightening: [%.15g,%.15g] -> [%.15g,%.15g] (nnz: %d, nchg: %d rhs: %.15g)\n",
1261 absmin, absmax, newabsmin, newabsmax, SCIPproofsetGetNVars(proofset), *nchgcoefs, proofsetGetRhs(proofset));
1262 }
1263#endif
1264}
1265
1266/** try to generate alternative proofs by applying subadditive functions */
1267static
1269 SCIP_CONFLICT* conflict, /**< conflict analysis data */
1270 SCIP_SET* set, /**< global SCIP settings */
1271 SCIP_STAT* stat, /**< dynamic SCIP statistics */
1272 SCIP_PROB* transprob, /**< transformed problem */
1273 SCIP_TREE* tree, /**< tree data */
1274 BMS_BLKMEM* blkmem, /**< block memory */
1275 SCIP_AGGRROW* proofrow, /**< proof rows data */
1276 SCIP_Real* curvarlbs, /**< current lower bounds of active problem variables */
1277 SCIP_Real* curvarubs, /**< current upper bounds of active problem variables */
1278 SCIP_CONFTYPE conflicttype /**< type of the conflict */
1279 )
1280{
1281 SCIP_VAR** vars;
1283 SCIP_Real* cutcoefs;
1284 SCIP_Real cutefficacy;
1285 SCIP_Real cutrhs;
1286 SCIP_Real proofefficacy;
1287 SCIP_Real efficacynorm;
1288 SCIP_Bool islocal;
1289 SCIP_Bool cutsuccess;
1290 SCIP_Bool success;
1291 SCIP_Bool infdelta;
1292 int* cutinds;
1293 int* inds;
1294 int cutnnz;
1295 int nnz;
1296 int nvars;
1297 int i;
1298
1299 vars = SCIPprobGetVars(transprob);
1300 nvars = SCIPprobGetNVars(transprob);
1301
1304
1306
1307 if( infdelta )
1308 return SCIP_OKAY;
1309
1311
1314
1315 /* create reference solution */
1316 SCIP_CALL( SCIPcreateSol(set->scip, &refsol, NULL) );
1317
1318 /* initialize with average solution */
1319 for( i = 0; i < nvars; i++ )
1320 {
1322 }
1323
1324 /* set all variables that are part of the proof to its active local bound */
1325 for( i = 0; i < nnz; i++ )
1326 {
1327 SCIP_Real val = SCIPaggrRowGetProbvarValue(proofrow, inds[i]);
1328
1329 if( val > 0.0 )
1330 {
1331 SCIP_CALL( SCIPsolSetVal(refsol, set, stat, tree, vars[inds[i]], curvarubs[inds[i]]) );
1332 }
1333 else
1334 {
1335 SCIP_CALL( SCIPsolSetVal(refsol, set, stat, tree, vars[inds[i]], curvarlbs[inds[i]]) );
1336 }
1337 }
1338
1341
1342 cutnnz = 0;
1344
1345 /* apply flow cover */
1349
1350 /* apply MIR */
1353 &islocal, &cutsuccess) );
1354 success = (success || cutsuccess);
1355
1356 /* replace the current proof */
1358 {
1360 SCIP_Bool redundant;
1361 int nchgcoefs;
1362
1365
1367
1368 /* apply coefficient tightening */
1369 tightenCoefficients(set, alternativeproofset, &nchgcoefs, &redundant);
1370
1371 if( !redundant )
1372 {
1374 }
1375 else
1376 {
1378 }
1379 } /*lint !e438*/
1380
1383
1384 SCIP_CALL( SCIPfreeSol(set->scip, &refsol) );
1385
1386 return SCIP_OKAY;
1387}
1388
1389/** tighten a given infeasibility proof a^Tx <= b with minact > b w.r.t. local bounds
1390 *
1391 * 1) Apply cut generating functions
1392 * - c-MIR
1393 * - Flow-cover
1394 * - TODO: implement other subadditive functions
1395 * 2) Remove continuous variables contributing with its global bound
1396 * - TODO: implement a variant of non-zero-cancellation
1397 */
1398static
1400 SCIP_CONFLICT* conflict, /**< conflict analysis data */
1401 SCIP_SET* set, /**< global SCIP settings */
1402 SCIP_STAT* stat, /**< dynamic SCIP statistics */
1403 BMS_BLKMEM* blkmem, /**< block memory */
1404 SCIP_PROB* transprob, /**< transformed problem */
1405 SCIP_TREE* tree, /**< tree data */
1406 SCIP_AGGRROW* proofrow, /**< aggregated row representing the proof */
1407 int validdepth, /**< depth where the proof is valid */
1408 SCIP_Real* curvarlbs, /**< current lower bounds of active problem variables */
1409 SCIP_Real* curvarubs, /**< current upper bounds of active problem variables */
1410 SCIP_Bool initialproof /**< do we analyze the initial reason of infeasibility? */
1411 )
1412{
1413 SCIP_VAR** vars;
1414 SCIP_Real* vals;
1415 int* inds;
1416 SCIP_PROOFSET* proofset;
1417 SCIP_Bool valid;
1418 SCIP_Bool redundant;
1419 int nnz;
1420 int nchgcoefs;
1421 int nbinvars;
1422 int ncontvars;
1423 int nintvars;
1424 int i;
1425
1426 assert(conflict->proofset != NULL);
1427 assert(curvarlbs != NULL);
1428 assert(curvarubs != NULL);
1429
1430 vars = SCIPprobGetVars(transprob);
1431 nbinvars = 0;
1432 nintvars = 0;
1433 ncontvars = 0;
1434
1437
1438 /* count number of binary, integer, and continuous variables */
1439 for( i = 0; i < nnz; i++ )
1440 {
1441 assert(SCIPvarGetProbindex(vars[inds[i]]) == inds[i]);
1442
1443 if( SCIPvarIsBinary(vars[inds[i]]) )
1444 ++nbinvars;
1445 else if( SCIPvarIsIntegral(vars[inds[i]]) )
1446 ++nintvars;
1447 else
1448 ++ncontvars;
1449 }
1450
1451 SCIPsetDebugMsg(set, "start dual proof tightening:\n");
1452 SCIPsetDebugMsg(set, "-> tighten dual proof: nvars=%d (bin=%d, int=%d, cont=%d)\n",
1453 nnz, nbinvars, nintvars, ncontvars);
1455
1456 /* try to find an alternative proof of local infeasibility that is stronger */
1457 if( set->conf_sepaaltproofs )
1458 {
1459 SCIP_CALL( separateAlternativeProofs(conflict, set, stat, transprob, tree, blkmem, proofrow, curvarlbs, curvarubs,
1460 conflict->conflictset->conflicttype) );
1461 }
1462
1463 if( initialproof )
1464 proofset = conflict->proofset;
1465 else
1466 {
1467 SCIP_CALL( proofsetCreate(&proofset, blkmem) );
1468 }
1469
1470 /* start with a proofset containing all variables with a non-zero coefficient in the dual proof */
1471 SCIP_CALL( proofsetAddAggrrow(proofset, set, blkmem, proofrow) );
1472 proofset->conflicttype = conflict->conflictset->conflicttype;
1473 proofset->validdepth = validdepth;
1474
1475 /* get proof data */
1476 vals = proofsetGetVals(proofset);
1477 inds = proofsetGetInds(proofset);
1478 nnz = SCIPproofsetGetNVars(proofset);
1479
1480#ifndef NDEBUG
1481 for( i = 0; i < nnz; i++ )
1482 {
1483 int idx = inds[i];
1484 if( vals[i] > 0.0 )
1486 if( vals[i] < 0.0 )
1488 }
1489#endif
1490
1491 /* remove continuous variable contributing with their global bound
1492 *
1493 * todo: check whether we also want to do that for bound exceeding proofs, but then we cannot update the
1494 * conflict anymore
1495 */
1496 if( proofset->conflicttype == SCIP_CONFTYPE_INFEASLP )
1497 {
1498 /* remove all continuous variables that have equal global and local bounds (ub or lb depend on the sign)
1499 * from the proof
1500 */
1501
1502 for( i = 0; i < nnz && nnz > 1; )
1503 {
1504 SCIP_Real val;
1505 int idx = inds[i];
1506
1507 assert(vars[idx] != NULL);
1508
1509 val = vals[i];
1510 assert(!SCIPsetIsZero(set, val));
1511
1512 /* skip integral variables */
1514 {
1515 i++;
1516 continue;
1517 }
1518 else
1519 {
1520 SCIP_Real glbbd;
1521 SCIP_Real locbd;
1522
1523 /* get appropriate global and local bounds */
1524 glbbd = (val < 0.0 ? SCIPvarGetUbGlobal(vars[idx]) : SCIPvarGetLbGlobal(vars[idx]));
1525 locbd = (val < 0.0 ? curvarubs[idx] : curvarlbs[idx]);
1526
1527 if( !SCIPsetIsEQ(set, glbbd, locbd) )
1528 {
1529 i++;
1530 continue;
1531 }
1532
1533 SCIPsetDebugMsg(set, "-> remove continuous variable <%s>: glb=[%g,%g], loc=[%g,%g], val=%g\n",
1535 curvarlbs[idx], curvarubs[idx], val);
1536
1537 proofsetCancelVarWithBound(proofset, set, vars[idx], i, &valid);
1538 assert(valid); /* this should be always fulfilled at this place */
1539
1540 --nnz;
1541 }
1542 }
1543 }
1544
1545 /* apply coefficient tightening to initial proof */
1546 tightenCoefficients(set, proofset, &nchgcoefs, &redundant);
1547
1548 /* it can happen that the constraints is almost globally redundant w.r.t to the maximal activity,
1549 * e.g., due to numerics. in this case, we want to discard the proof
1550 */
1551 if( redundant )
1552 {
1553#ifndef NDEBUG
1554 SCIP_Real eps = MIN(0.01, 10.0*set->num_feastol);
1555 assert(proofset->rhs - getMaxActivity(set, transprob, proofset->vals, proofset->inds, proofset->nnz, NULL, NULL) < eps);
1556#endif
1557 if( initialproof )
1558 {
1559 proofsetClear(proofset);
1560 }
1561 else
1562 {
1563 SCIPproofsetFree(&proofset, blkmem);
1564 }
1565 }
1566 else
1567 {
1568 if( !initialproof )
1569 {
1570 SCIP_CALL( conflictInsertProofset(conflict, set, proofset) );
1571 }
1572
1573 if( nchgcoefs > 0 )
1574 {
1575 if( proofset->conflicttype == SCIP_CONFTYPE_INFEASLP )
1577 else if( proofset->conflicttype == SCIP_CONFTYPE_BNDEXCEEDING )
1579 }
1580 }
1581
1582 return SCIP_OKAY;
1583}
1584
1585/** perform conflict analysis based on a dual unbounded ray
1586 *
1587 * given an aggregation of rows lhs <= a^Tx such that lhs > maxactivity. if the constraint has size one we add a
1588 * bound change instead of the constraint.
1589 */
1591 SCIP_CONFLICT* conflict, /**< conflict analysis data */
1592 SCIP_SET* set, /**< global SCIP settings */
1593 SCIP_STAT* stat, /**< dynamic SCIP statistics */
1594 BMS_BLKMEM* blkmem, /**< block memory */
1595 SCIP_PROB* origprob, /**< original problem */
1596 SCIP_PROB* transprob, /**< transformed problem */
1597 SCIP_TREE* tree, /**< tree data */
1598 SCIP_REOPT* reopt, /**< reoptimization data */
1599 SCIP_LP* lp, /**< LP data */
1600 SCIP_AGGRROW* proofrow, /**< aggregated row representing the proof */
1601 int validdepth, /**< valid depth of the dual proof */
1602 SCIP_Real* curvarlbs, /**< current lower bounds of active problem variables */
1603 SCIP_Real* curvarubs, /**< current upper bounds of active problem variables */
1604 SCIP_Bool initialproof, /**< do we analyze the initial reason of infeasibility? */
1605 SCIP_Bool* globalinfeasible, /**< pointer to store whether global infeasibility could be proven */
1606 SCIP_Bool* success /**< pointer to store success result */
1607 )
1608{
1609 SCIP_Real rhs;
1610 SCIP_Real minact;
1611 SCIP_Bool infdelta;
1612 int nnz;
1613
1614 assert(set != NULL);
1615 assert(transprob != NULL);
1616 assert(validdepth >= 0);
1617 assert(validdepth == 0 || validdepth < SCIPtreeGetFocusDepth(tree));
1618
1619 /* get sparse data */
1622
1624 *success = FALSE;
1625
1626 /* get minimal activity w.r.t. local bounds */
1628
1629 if( infdelta )
1630 return SCIP_OKAY;
1631
1632 /* only run is the proof proves local infeasibility */
1633 if( SCIPsetIsFeasLE(set, minact, rhs) )
1634 return SCIP_OKAY;
1635
1636 /* if the farkas-proof is empty, the node and its sub tree can be cut off completely */
1637 if( nnz == 0 )
1638 {
1639 SCIPsetDebugMsg(set, " -> empty farkas-proof in depth %d cuts off sub tree at depth %d\n", SCIPtreeGetFocusDepth(tree), validdepth);
1640
1641 SCIP_CALL( SCIPnodeCutoff(tree->path[validdepth], set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
1642
1644 *success = TRUE;
1645
1646 ++conflict->ndualproofsinfsuccess;
1647
1648 return SCIP_OKAY;
1649 }
1650
1651 /* try to enforce the constraint based on a dual ray */
1652 SCIP_CALL( tightenDualproof(conflict, set, stat, blkmem, transprob, tree, proofrow, validdepth,
1654
1655 if( *globalinfeasible )
1656 {
1657 SCIPsetDebugMsg(set, "detect global: cutoff root node\n");
1658 SCIP_CALL( SCIPnodeCutoff(tree->path[0], set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
1659 *success = TRUE;
1660
1661 ++conflict->ndualproofsinfsuccess;
1662 }
1663
1664 return SCIP_OKAY;
1665}
internal methods for clocks and timing issues
#define BOUNDSWITCH
#define MAXFRAC
void SCIPproofsetFree(SCIP_PROOFSET **proofset, BMS_BLKMEM *blkmem)
static char varGetChar(SCIP_VAR *var)
static SCIP_RETCODE tightenSingleVar(SCIP_CONFLICT *conflict, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_PROB *origprob, SCIP_PROB *transprob, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_VAR *var, SCIP_Real val, SCIP_Real rhs, SCIP_CONFTYPE prooftype, int validdepth)
#define POSTPROCESS
static SCIP_RETCODE tightenDualproof(SCIP_CONFLICT *conflict, SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_PROB *transprob, SCIP_TREE *tree, SCIP_AGGRROW *proofrow, int validdepth, SCIP_Real *curvarlbs, SCIP_Real *curvarubs, SCIP_Bool initialproof)
static SCIP_RETCODE createAndAddProofcons(SCIP_CONFLICT *conflict, SCIP_CONFLICTSTORE *conflictstore, SCIP_PROOFSET *proofset, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *origprob, SCIP_PROB *transprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, BMS_BLKMEM *blkmem)
static SCIP_Real * proofsetGetVals(SCIP_PROOFSET *proofset)
#define ALLOWLOCAL
static SCIP_CONFTYPE proofsetGetConftype(SCIP_PROOFSET *proofset)
static SCIP_RETCODE conflictEnsureProofsetsMem(SCIP_CONFLICT *conflict, SCIP_SET *set, int num)
static SCIP_Real getMaxActivity(SCIP_SET *set, SCIP_PROB *transprob, SCIP_Real *coefs, int *inds, int nnz, SCIP_Real *curvarlbs, SCIP_Real *curvarubs)
static int * proofsetGetInds(SCIP_PROOFSET *proofset)
static SCIP_Real getMinActivity(SCIP_SET *set, SCIP_PROB *transprob, SCIP_Real *coefs, int *inds, int nnz, SCIP_Real *curvarlbs, SCIP_Real *curvarubs)
static SCIP_RETCODE propagateLongProof(SCIP_CONFLICT *conflict, SCIP_SET *set, SCIP_STAT *stat, SCIP_REOPT *reopt, SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_PROB *origprob, SCIP_PROB *transprob, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_Real *coefs, int *inds, int nnz, SCIP_Real rhs, SCIP_CONFTYPE conflicttype, int validdepth)
static SCIP_RETCODE separateAlternativeProofs(SCIP_CONFLICT *conflict, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_AGGRROW *proofrow, SCIP_Real *curvarlbs, SCIP_Real *curvarubs, SCIP_CONFTYPE conflicttype)
SCIP_RETCODE SCIPconflictInitProofset(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem)
static SCIP_RETCODE proofsetAddAggrrow(SCIP_PROOFSET *proofset, SCIP_SET *set, BMS_BLKMEM *blkmem, SCIP_AGGRROW *aggrrow)
#define USEVBDS
#define MINFRAC
#define debugPrintViolationInfo(...)
static void proofsetCancelVarWithBound(SCIP_PROOFSET *proofset, SCIP_SET *set, SCIP_VAR *var, int pos, SCIP_Bool *valid)
static void tightenCoefficients(SCIP_SET *set, SCIP_PROOFSET *proofset, int *nchgcoefs, SCIP_Bool *redundant)
static void proofsetClear(SCIP_PROOFSET *proofset)
static SCIP_RETCODE proofsetCreate(SCIP_PROOFSET **proofset, BMS_BLKMEM *blkmem)
static SCIP_Real proofsetGetRhs(SCIP_PROOFSET *proofset)
SCIP_RETCODE SCIPconflictAnalyzeDualProof(SCIP_CONFLICT *conflict, SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_PROB *origprob, SCIP_PROB *transprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_AGGRROW *proofrow, int validdepth, SCIP_Real *curvarlbs, SCIP_Real *curvarubs, SCIP_Bool initialproof, SCIP_Bool *globalinfeasible, SCIP_Bool *success)
SCIP_RETCODE SCIPconflictFlushProofset(SCIP_CONFLICT *conflict, SCIP_CONFLICTSTORE *conflictstore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable)
int SCIPproofsetGetNVars(SCIP_PROOFSET *proofset)
static SCIP_RETCODE proofsetAddSparseData(SCIP_PROOFSET *proofset, BMS_BLKMEM *blkmem, SCIP_Real *vals, int *inds, int nnz, SCIP_Real rhs)
static SCIP_RETCODE conflictInsertProofset(SCIP_CONFLICT *conflict, SCIP_SET *set, SCIP_PROOFSET *proofset)
internal methods for dual proof conflict analysis
SCIP_Real SCIPaggrRowGetMinActivity(SCIP_SET *set, SCIP_PROB *transprob, SCIP_AGGRROW *aggrrow, SCIP_Real *curvarlbs, SCIP_Real *curvarubs, SCIP_Bool *infdelta)
methods and datastructures for conflict analysis
SCIP_RETCODE SCIPconflictstoreAddDualraycons(SCIP_CONFLICTSTORE *conflictstore, SCIP_CONS *dualproof, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_REOPT *reopt, SCIP_Bool hasrelaxvar)
int SCIPconflictstoreGetNDualInfProofs(SCIP_CONFLICTSTORE *conflictstore)
SCIP_Real SCIPconflictstoreGetAvgNnzDualInfProofs(SCIP_CONFLICTSTORE *conflictstore)
int SCIPconflictstoreGetNDualBndProofs(SCIP_CONFLICTSTORE *conflictstore)
SCIP_Real SCIPconflictstoreGetAvgNnzDualBndProofs(SCIP_CONFLICTSTORE *conflictstore)
SCIP_RETCODE SCIPconflictstoreAddDualsolcons(SCIP_CONFLICTSTORE *conflictstore, SCIP_CONS *dualproof, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_REOPT *reopt, SCIP_Real scale, SCIP_Bool updateside, SCIP_Bool hasrelaxvar)
internal methods for storing conflicts
void SCIPconsMarkConflict(SCIP_CONS *cons)
Definition cons.c:7120
SCIP_RETCODE SCIPconsRelease(SCIP_CONS **cons, BMS_BLKMEM *blkmem, SCIP_SET *set)
Definition cons.c:6266
internal methods for constraints and constraint handlers
Constraint handler for linear constraints in their most general form, .
methods for the aggregation rows
#define SCIPquadprecProdDD(r, a, b)
Definition dbldblarith.h:58
#define QUAD_ASSIGN(a, constant)
Definition dbldblarith.h:51
#define QUAD(x)
Definition dbldblarith.h:47
#define SCIPquadprecSumQQ(r, a, b)
Definition dbldblarith.h:67
#define QUAD_TO_DBL(x)
Definition dbldblarith.h:49
#define NULL
Definition def.h:267
#define SCIP_MAXSTRLEN
Definition def.h:288
#define MIN(x, y)
Definition def.h:243
#define SCIP_ALLOC(x)
Definition def.h:385
#define SCIP_Real
Definition def.h:173
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define MAX(x, y)
Definition def.h:239
#define SCIP_LONGINT_FORMAT
Definition def.h:165
#define REALABS(x)
Definition def.h:197
#define SCIP_CALL(x)
Definition def.h:374
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPupgradeConsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_CONS **upgdcons)
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4197
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition cons.c:8234
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition scip_cons.c:1174
SCIP_RETCODE SCIPcutGenerationHeuristicCMIR(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, int maxtestdelta, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
Definition cuts.c:4218
SCIP_Bool SCIPcutsTightenCoefficients(SCIP *scip, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, int *nchgcoefs)
Definition cuts.c:1535
SCIP_Real SCIPaggrRowGetRhs(SCIP_AGGRROW *aggrrow)
Definition cuts.c:2589
int * SCIPaggrRowGetInds(SCIP_AGGRROW *aggrrow)
Definition cuts.c:2549
int SCIPaggrRowGetNNz(SCIP_AGGRROW *aggrrow)
Definition cuts.c:2559
static INLINE SCIP_Real SCIPaggrRowGetProbvarValue(SCIP_AGGRROW *aggrrow, int probindex)
Definition cuts.h:251
SCIP_RETCODE SCIPcalcFlowCover(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool allowlocal, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
Definition cuts.c:7428
SCIP_Real SCIPaggrRowCalcEfficacyNorm(SCIP *scip, SCIP_AGGRROW *aggrrow)
Definition cuts.c:2166
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition tree.c:7490
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition var.c:17599
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:18144
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17584
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition var.c:18088
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition var.c:17768
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17419
SCIP_Real SCIPvarGetAvgSol(SCIP_VAR *var)
Definition var.c:14062
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition var.c:17610
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:18134
SCIP_Bool SCIPvarIsRelaxationOnly(SCIP_VAR *var)
Definition var.c:17706
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition var.c:18078
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition misc.c:10877
return SCIP_OKAY
SCIPfreeSol(scip, &heurdata->sol))
SCIPcreateSol(scip, &heurdata->sol, heur))
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
SCIP_VAR * var
static SCIP_VAR ** vars
int nbinvars
int nintvars
internal methods for branching and inference history
internal methods for LP management
interface methods for specific LP solvers
#define BMSduplicateBlockMemoryArray(mem, ptr, source, num)
Definition memory.h:462
#define BMSfreeBlockMemory(mem, ptr)
Definition memory.h:465
#define BMSallocBlockMemory(mem, ptr)
Definition memory.h:451
#define BMSreallocMemoryArray(ptr, num)
Definition memory.h:127
#define BMSfreeBlockMemoryArrayNull(mem, ptr, num)
Definition memory.h:468
#define BMSreallocBlockMemoryArray(mem, ptr, oldnum, newnum)
Definition memory.h:458
struct BMS_BlkMem BMS_BLKMEM
Definition memory.h:437
real eps
methods commonly used for presolving
int SCIPprobGetNVars(SCIP_PROB *prob)
Definition prob.c:2393
SCIP_RETCODE SCIPprobAddCons(SCIP_PROB *prob, SCIP_SET *set, SCIP_STAT *stat, SCIP_CONS *cons)
Definition prob.c:1319
SCIP_VAR ** SCIPprobGetVars(SCIP_PROB *prob)
Definition prob.c:2438
internal methods for storing and manipulating the main problem
internal methods for propagators
public methods for conflict analysis handlers
public methods for managing constraints
public methods for LP management
public methods for message output
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for handling parameter settings
public methods for propagators
public methods for branch and bound tree
public methods for problem variables
public methods for conflict handler plugins and conflict analysis
public methods for constraint handler plugins and constraints
public methods for memory management
public methods for solutions
public methods for SCIP variables
SCIP_Bool SCIPsetIsGE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition set.c:6281
SCIP_Bool SCIPsetIsFeasLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition set.c:6629
SCIP_Bool SCIPsetIsPositive(SCIP_SET *set, SCIP_Real val)
Definition set.c:6310
SCIP_Bool SCIPsetIsLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition set.c:6245
SCIP_Real SCIPsetFeasFloor(SCIP_SET *set, SCIP_Real val)
Definition set.c:6752
SCIP_Bool SCIPsetIsEQ(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition set.c:6209
SCIP_Real SCIPsetInfinity(SCIP_SET *set)
Definition set.c:6052
SCIP_Bool SCIPsetIsLT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition set.c:6227
SCIP_Bool SCIPsetIsInfinity(SCIP_SET *set, SCIP_Real val)
Definition set.c:6187
SCIP_Bool SCIPsetIsGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition set.c:6263
SCIP_Bool SCIPsetIsIntegral(SCIP_SET *set, SCIP_Real val)
Definition set.c:6332
SCIP_Bool SCIPsetIsZero(SCIP_SET *set, SCIP_Real val)
Definition set.c:6299
int SCIPsetCalcMemGrowSize(SCIP_SET *set, int num)
Definition set.c:5752
SCIP_Bool SCIPsetIsNegative(SCIP_SET *set, SCIP_Real val)
Definition set.c:6321
internal methods for global SCIP settings
#define SCIPsetFreeBufferArray(set, ptr)
Definition set.h:1755
#define SCIPsetAllocBufferArray(set, ptr, num)
Definition set.h:1748
#define SCIPsetDebugMsg
Definition set.h:1784
SCIP_RETCODE SCIPsolSetVal(SCIP_SOL *sol, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_VAR *var, SCIP_Real val)
Definition sol.c:1077
internal methods for storing primal CIP solutions
SCIP_CONFTYPE conflicttype
SCIP_Longint ndualproofsbndglobal
SCIP_PROOFSET * proofset
SCIP_Longint ndualproofsinfsuccess
SCIP_PROOFSET ** proofsets
SCIP_Longint ndualproofsinflocal
SCIP_Longint nglbchgbds
SCIP_Longint dualproofsbndnnonzeros
SCIP_Longint nlocchgbds
SCIP_Longint ndualproofsinfglobal
SCIP_Longint ninflpsuccess
SCIP_Longint ndualproofsbndsuccess
SCIP_Longint dualproofsinfnnonzeros
SCIP_Longint nboundlpsuccess
SCIP_CONFLICTSET * conflictset
SCIP_Longint ndualproofsbndlocal
SCIP_Bool strongbranching
Definition struct_lp.h:377
int startnconss
Definition struct_prob.h:86
SCIP_Real * vals
SCIP_CONFTYPE conflicttype
SCIP_Real avgnnz
SCIP_NODE ** path
datastructures for conflict analysis
data structures for LP management
datastructures for storing and manipulating the main problem
datastructures for global SCIP settings
datastructures for problem statistics
data structures for branch and bound tree
datastructures for problem variables
SCIP_RETCODE SCIPnodeCutoff(SCIP_NODE *node, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_REOPT *reopt, SCIP_LP *lp, BMS_BLKMEM *blkmem)
Definition tree.c:1234
int SCIPtreeGetFocusDepth(SCIP_TREE *tree)
Definition tree.c:8375
void SCIPnodePropagateAgain(SCIP_NODE *node, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree)
Definition tree.c:1294
int SCIPtreeGetEffectiveRootDepth(SCIP_TREE *tree)
Definition tree.c:8489
SCIP_RETCODE SCIPnodeAddBoundchg(SCIP_NODE *node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_VAR *var, SCIP_Real newbound, SCIP_BOUNDTYPE boundtype, SCIP_Bool probingchange)
Definition tree.c:2133
SCIP_RETCODE SCIPnodeAddCons(SCIP_NODE *node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_CONS *cons)
Definition tree.c:1654
internal methods for branch and bound tree
@ SCIP_CONFTYPE_ALTINFPROOF
@ SCIP_CONFTYPE_BNDEXCEEDING
@ SCIP_CONFTYPE_ALTBNDPROOF
@ SCIP_CONFTYPE_INFEASLP
@ SCIP_CONFTYPE_UNKNOWN
enum SCIP_ConflictType SCIP_CONFTYPE
@ SCIP_BOUNDTYPE_UPPER
Definition type_lp.h:57
@ SCIP_BOUNDTYPE_LOWER
Definition type_lp.h:56
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition type_lp.h:59
@ SCIP_INVALIDCALL
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARTYPE_INTEGER
Definition type_var.h:63
@ SCIP_VARTYPE_CONTINUOUS
Definition type_var.h:71
@ SCIP_VARTYPE_IMPLINT
Definition type_var.h:64
@ SCIP_VARTYPE_BINARY
Definition type_var.h:62
enum SCIP_Vartype SCIP_VARTYPE
Definition type_var.h:73
void SCIPvarAdjustBd(SCIP_VAR *var, SCIP_SET *set, SCIP_BOUNDTYPE boundtype, SCIP_Real *bd)
Definition var.c:6551
internal methods for problem variables
methods for creating output for visualization tools (VBC, BAK)