Scippy

SCIP

Solving Constraint Integer Programs

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{
101 SCIP_VARTYPE vartype = SCIPvarGetType(var);
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
374 newsize = SCIPsetCalcMemGrowSize(set, num);
375 SCIP_ALLOC( BMSreallocMemoryArray(&conflict->proofsets, newsize) );
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 */
440 if( SCIPvarIsIntegral(var) && SCIPsetIsIntegral(set, val) )
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 {
484 conslhs = -SCIPsetInfinity(set);
485 consrhs = newbound;
486 }
487 else
488 {
489 conslhs = newbound;
490 consrhs = SCIPsetInfinity(set);
491 }
492
493 SCIP_CALL( SCIPcreateConsLinear(set->scip, &cons, name, 0, NULL, NULL, conslhs, consrhs,
494 FALSE, FALSE, FALSE, FALSE, TRUE, !applyglobal, FALSE, TRUE, TRUE, FALSE) );
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 {
511 assert(applyglobal);
512
513 SCIPsetDebugMsg(set, "change global %s bound of <%s>[%c]: %g -> %g\n",
514 (boundtype == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper"),
515 SCIPvarGetName(var), varGetChar(var),
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
532 if( prooftype == SCIP_CONFTYPE_INFEASLP || prooftype == SCIP_CONFTYPE_ALTINFPROOF )
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
588 assert(SCIPvarGetProbindex(vars[v]) == v);
589
590 val = coefs[i];
591
592 if( val > 0.0 )
593 {
594 SCIP_Real bnd;
595
596 assert(curvarlbs == NULL || !SCIPsetIsInfinity(set, -curvarlbs[v]));
597
598 bnd = (curvarlbs == NULL ? SCIPvarGetLbGlobal(vars[v]) : curvarlbs[v]);
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
609 assert(curvarubs == NULL || !SCIPsetIsInfinity(set, curvarubs[v]));
610
611 bnd = (curvarubs == NULL ? SCIPvarGetUbGlobal(vars[v]) : curvarubs[v]);
612
613 if( SCIPsetIsInfinity(set, bnd) )
614 return -SCIPsetInfinity(set);
615
616 SCIPquadprecProdDD(delta, val, bnd);
617 }
618
619 /* update minimal activity */
620 SCIPquadprecSumQQ(minact, minact, delta);
621 }
622
623 /* check whether the minmal activity is infinite */
624 if( SCIPsetIsInfinity(set, QUAD_TO_DBL(minact)) )
625 return SCIPsetInfinity(set);
626 if( SCIPsetIsInfinity(set, -QUAD_TO_DBL(minact)) )
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
662 assert(SCIPvarGetProbindex(vars[v]) == v);
663
664 val = coefs[i];
665
666 if( val < 0.0 )
667 {
668 SCIP_Real bnd;
669
670 assert(curvarlbs == NULL || !SCIPsetIsInfinity(set, -curvarlbs[v]));
671
672 bnd = (curvarlbs == NULL ? SCIPvarGetLbGlobal(vars[v]) : curvarlbs[v]);
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
683 assert(curvarubs == NULL || !SCIPsetIsInfinity(set, curvarubs[v]));
684
685 bnd = (curvarubs == NULL ? SCIPvarGetUbGlobal(vars[v]) : curvarubs[v]);
686
687 if( SCIPsetIsInfinity(set, bnd) )
688 return SCIPsetInfinity(set);
689
690 SCIPquadprecProdDD(delta, val, bnd);
691 }
692
693 /* update maximal activity */
694 SCIPquadprecSumQQ(maxact, maxact, delta);
695 }
696
697 /* check whether the maximal activity got infinite */
698 if( SCIPsetIsInfinity(set, QUAD_TO_DBL(maxact)) )
699 return SCIPsetInfinity(set);
700 if( SCIPsetIsInfinity(set, -QUAD_TO_DBL(maxact)) )
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 */
741 if( SCIPsetIsInfinity(set, -minact) )
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];
756 lb = SCIPvarGetLbGlobal(var);
757 ub = SCIPvarGetUbGlobal(var);
758
759 assert(!SCIPsetIsZero(set, val));
760
761 resminact = minact;
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
771 if( SCIPsetIsInfinity(set, newub) )
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
789 if( SCIPsetIsInfinity(set, -newlb) )
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;
829 SCIP_CONS* upgdcons;
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);
858 assert(!SCIPsetIsInfinity(set, rhs));
859
860 coefs = proofsetGetVals(proofset);
861 assert(coefs != NULL);
862
863 inds = proofsetGetInds(proofset);
864 assert(inds != NULL);
865
866 conflicttype = proofsetGetConftype(proofset);
867
868 applyglobal = (proofset->validdepth <= SCIPtreeGetEffectiveRootDepth(tree));
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 */
875 if( SCIPsetIsLE(set, globalmaxactivity, rhs) )
876 return SCIP_OKAY;
877
878 /* check whether the constraint proves global infeasibility */
879 globalminactivity = getMinActivity(set, transprob, coefs, inds, nnz, NULL, NULL);
880 if( SCIPsetIsGT(set, globalminactivity, rhs) )
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 {
904 fillin += SCIPconflictstoreGetNDualInfProofs(conflictstore) * SCIPconflictstoreGetAvgNnzDualInfProofs(conflictstore);
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
912 fillin += SCIPconflictstoreGetNDualBndProofs(conflictstore) * SCIPconflictstoreGetAvgNnzDualBndProofs(conflictstore);
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 */
932 hasrelaxvar = FALSE;
933 contonly = TRUE;
934 for( i = 0; i < nnz && (!hasrelaxvar || contonly); ++i )
935 {
936 hasrelaxvar |= SCIPvarIsRelaxationOnly(vars[inds[i]]);
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,
953 FALSE, FALSE, FALSE, FALSE, TRUE, !applyglobal,
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 */
967 SCIP_CALL( SCIPupgradeConsLinear(set->scip, cons, &upgdcons) );
968 if( upgdcons != NULL )
969 {
970 SCIP_CONSHDLR* conshdlr;
971
972 conshdlr = SCIPconsGetHdlr(upgdcons);
973 assert(conshdlr != NULL);
974
975 /* only upgrade constraint if it can report number of variables (needed by
976 * SCIPconflictstoreAddDualraycons() and SCIPconflictstoreAddDualsolcons())
977 */
978 if( conshdlr->consgetnvars == NULL )
979 {
980 SCIP_CALL( SCIPreleaseCons(set->scip, &upgdcons) );
981 }
982 else
983 {
984 SCIP_CALL( SCIPreleaseCons(set->scip, &cons) );
985 cons = upgdcons;
986
987 if( conflicttype == SCIP_CONFTYPE_INFEASLP )
988 conflicttype = SCIP_CONFTYPE_ALTINFPROOF;
989 else if( conflicttype == SCIP_CONFTYPE_BNDEXCEEDING )
990 conflicttype = SCIP_CONFTYPE_ALTBNDPROOF;
991 }
992 }
993 }
994
995 /* mark constraint to be a conflict */
997
998 /* add constraint to storage */
999 if( conflicttype == SCIP_CONFTYPE_INFEASLP || conflicttype == SCIP_CONFTYPE_ALTINFPROOF )
1000 {
1001 /* add dual proof to storage */
1002 SCIP_CALL( SCIPconflictstoreAddDualraycons(conflictstore, cons, blkmem, set, stat, transprob, reopt, hasrelaxvar) );
1003 }
1004 else
1005 {
1006 SCIP_Real scale = 1.0;
1007 SCIP_Bool updateside = FALSE;
1008
1009 /* In some cases the constraint could not be updated to a more special type. However, it is possible that
1010 * constraint got scaled. Therefore, we need to be very careful when updating the lhs/rhs after the incumbent
1011 * solution has improved.
1012 */
1013 if( conflicttype == SCIP_CONFTYPE_BNDEXCEEDING )
1014 {
1015 SCIP_Real side;
1016
1017#ifndef NDEBUG
1018 SCIP_CONSHDLR* conshdlr = SCIPconsGetHdlr(cons);
1019
1020 assert(conshdlr != NULL);
1021 assert(strcmp(SCIPconshdlrGetName(conshdlr), "linear") == 0);
1022#endif
1023 side = SCIPgetLhsLinear(set->scip, cons);
1024
1025 if( !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(SCIPsetIsNegative(set, scale));
1035 }
1036 }
1037 else
1038 {
1039 side = SCIPgetRhsLinear(set->scip, cons);
1040 assert(!SCIPsetIsInfinity(set, side));
1041
1042 if( SCIPsetIsZero(set, side) )
1043 {
1044 scale = 1.0;
1045 }
1046 else
1047 {
1048 scale = proofsetGetRhs(proofset) / side;
1049 assert(SCIPsetIsPositive(set, scale));
1050 }
1051 }
1052 updateside = TRUE;
1053 }
1054
1055 /* add dual proof to storage */
1056 SCIP_CALL( SCIPconflictstoreAddDualsolcons(conflictstore, cons, blkmem, set, stat, transprob, reopt, scale, updateside, hasrelaxvar) );
1057 }
1058
1059 if( applyglobal ) /*lint !e774*/
1060 {
1061 /* add the constraint to the global problem */
1062 SCIP_CALL( SCIPprobAddCons(transprob, set, stat, cons) );
1063 }
1064 else
1065 {
1066 SCIP_CALL( SCIPnodeAddCons(tree->path[proofset->validdepth], blkmem, set, stat, tree, cons) );
1067 }
1068
1069 SCIPsetDebugMsg(set, "added proof-constraint to node %p (#%lld) in depth %d (nproofconss %d)\n",
1070 (void*)tree->path[proofset->validdepth], SCIPnodeGetNumber(tree->path[proofset->validdepth]),
1071 proofset->validdepth,
1072 (conflicttype == SCIP_CONFTYPE_INFEASLP || conflicttype == SCIP_CONFTYPE_ALTINFPROOF)
1074
1075 /* release the constraint */
1076 SCIP_CALL( SCIPreleaseCons(set->scip, &cons) );
1077
1078 UPDATESTATISTICS:
1079 /* update statistics */
1080 if( conflicttype == SCIP_CONFTYPE_INFEASLP || conflicttype == SCIP_CONFTYPE_ALTINFPROOF )
1081 {
1082 conflict->dualproofsinfnnonzeros += nnz;
1083 if( applyglobal ) /*lint !e774*/
1084 ++conflict->ndualproofsinfglobal;
1085 else
1086 ++conflict->ndualproofsinflocal;
1087 ++conflict->ndualproofsinfsuccess;
1088 }
1089 else
1090 {
1091 assert(conflicttype == SCIP_CONFTYPE_BNDEXCEEDING || conflicttype == SCIP_CONFTYPE_ALTBNDPROOF);
1092 conflict->dualproofsbndnnonzeros += nnz;
1093 if( applyglobal ) /*lint !e774*/
1094 ++conflict->ndualproofsbndglobal;
1095 else
1096 ++conflict->ndualproofsbndlocal;
1097
1098 ++conflict->ndualproofsbndsuccess;
1099 }
1100 return SCIP_OKAY;
1101}
1102
1103/** create proof constraints out of proof sets */
1105 SCIP_CONFLICT* conflict, /**< conflict analysis data */
1106 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
1107 BMS_BLKMEM* blkmem, /**< block memory */
1108 SCIP_SET* set, /**< global SCIP settings */
1109 SCIP_STAT* stat, /**< dynamic problem statistics */
1110 SCIP_PROB* transprob, /**< transformed problem after presolve */
1111 SCIP_PROB* origprob, /**< original problem */
1112 SCIP_TREE* tree, /**< branch and bound tree */
1113 SCIP_REOPT* reopt, /**< reoptimization data structure */
1114 SCIP_LP* lp, /**< current LP data */
1115 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1116 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1117 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
1118 )
1119{
1120 assert(conflict != NULL);
1121
1123 {
1124 /* only one variable has a coefficient different to zero, we add this bound change instead of a constraint */
1125 if( SCIPproofsetGetNVars(conflict->proofset) == 1 )
1126 {
1127 SCIP_VAR** vars;
1128 SCIP_Real* coefs;
1129 int* inds;
1130 SCIP_Real rhs;
1131
1132 vars = SCIPprobGetVars(transprob);
1133
1134 coefs = proofsetGetVals(conflict->proofset);
1135 inds = proofsetGetInds(conflict->proofset);
1136 rhs = proofsetGetRhs(conflict->proofset);
1137
1138 SCIP_CALL( tightenSingleVar(conflict, set, stat, tree, blkmem, origprob, transprob, reopt, lp, \
1139 branchcand, eventqueue, cliquetable, vars[inds[0]], coefs[0], rhs, conflict->proofset->conflicttype,
1140 conflict->proofset->validdepth) );
1141 }
1142 else
1143 {
1144 SCIP_Bool skipinitialproof = FALSE;
1145
1146 /* prefer an infeasibility proof
1147 *
1148 * todo: check whether this is really what we want
1149 */
1150 if( set->conf_prefinfproof && proofsetGetConftype(conflict->proofset) == SCIP_CONFTYPE_BNDEXCEEDING )
1151 {
1152 int i;
1153
1154 for( i = 0; i < conflict->nproofsets; i++ )
1155 {
1157 {
1158 skipinitialproof = TRUE;
1159 break;
1160 }
1161 }
1162 }
1163
1164 if( !skipinitialproof )
1165 {
1166 /* create and add the original proof */
1167 SCIP_CALL( createAndAddProofcons(conflict, conflictstore, conflict->proofset, set, stat, origprob, transprob, \
1168 tree, reopt, lp, branchcand, eventqueue, cliquetable, blkmem) );
1169 }
1170 }
1171
1172 /* clear the proof set anyway */
1173 proofsetClear(conflict->proofset);
1174 }
1175
1176 if( conflict->nproofsets > 0 )
1177 {
1178 int i;
1179
1180 for( i = 0; i < conflict->nproofsets; i++ )
1181 {
1182 assert(conflict->proofsets[i] != NULL);
1183 assert(proofsetGetConftype(conflict->proofsets[i]) != SCIP_CONFTYPE_UNKNOWN);
1184
1185 /* only one variable has a coefficient different to zero, we add this bound change instead of a constraint */
1186 if( SCIPproofsetGetNVars(conflict->proofsets[i]) == 1 )
1187 {
1188 SCIP_VAR** vars;
1189 SCIP_Real* coefs;
1190 int* inds;
1191 SCIP_Real rhs;
1192
1193 vars = SCIPprobGetVars(transprob);
1194
1195 coefs = proofsetGetVals(conflict->proofsets[i]);
1196 inds = proofsetGetInds(conflict->proofsets[i]);
1197 rhs = proofsetGetRhs(conflict->proofsets[i]);
1198
1199 SCIP_CALL( tightenSingleVar(conflict, set, stat, tree, blkmem, origprob, transprob, reopt, lp,
1200 branchcand, eventqueue, cliquetable, vars[inds[0]], coefs[0], rhs,
1201 conflict->proofsets[i]->conflicttype, conflict->proofsets[i]->validdepth) );
1202 }
1203 else
1204 {
1205 /* create and add proof constraint */
1206 SCIP_CALL( createAndAddProofcons(conflict, conflictstore, conflict->proofsets[i], set, stat, origprob, \
1207 transprob, tree, reopt, lp, branchcand, eventqueue, cliquetable, blkmem) );
1208 }
1209 }
1210
1211 /* free all proofsets */
1212 for( i = 0; i < conflict->nproofsets; i++ )
1213 SCIPproofsetFree(&conflict->proofsets[i], blkmem);
1214
1215 conflict->nproofsets = 0;
1216 }
1217
1218 return SCIP_OKAY;
1219}
1220
1221
1222
1223#ifdef SCIP_DEBUG
1224/** print violation for debugging */
1225static
1227 SCIP_SET* set, /**< global SCIP settings */
1228 SCIP_Real minact, /**< min activity */
1229 SCIP_Real rhs, /**< right hand side */
1230 const char* infostr /**< additional info for this debug message, or NULL */
1231 )
1232{
1233 SCIPsetDebugMsg(set, "-> %sminact=%.15g rhs=%.15g violation=%.15g\n",infostr != NULL ? infostr : "" , minact, rhs, minact - rhs);
1234}
1235#else
1236#define debugPrintViolationInfo(...) /**/
1237#endif
1238
1239/** apply coefficient tightening */
1240static
1242 SCIP_SET* set, /**< global SCIP settings */
1243 SCIP_PROOFSET* proofset, /**< proof set */
1244 int* nchgcoefs, /**< pointer to store number of changed coefficients */
1245 SCIP_Bool* redundant /**< pointer to store whether the proof set is redundant */
1246 )
1247{
1248#ifdef SCIP_DEBUG
1249 SCIP_Real absmax = 0.0;
1250 SCIP_Real absmin = SCIPsetInfinity(set);
1251 int i;
1252
1253 for( i = 0; i < proofset->nnz; i++ )
1254 {
1255 absmax = MAX(absmax, REALABS(proofset->vals[i]));
1256 absmin = MIN(absmin, REALABS(proofset->vals[i]));
1257 }
1258#endif
1259
1260 (*redundant) = SCIPcutsTightenCoefficients(set->scip, FALSE, proofset->vals, &proofset->rhs, proofset->inds, &proofset->nnz, nchgcoefs);
1261
1262#ifdef SCIP_DEBUG
1263 {
1264 SCIP_Real newabsmax = 0.0;
1265 SCIP_Real newabsmin = SCIPsetInfinity(set);
1266
1267 for( i = 0; i < proofset->nnz; i++ )
1268 {
1269 newabsmax = MAX(newabsmax, REALABS(proofset->vals[i]));
1270 newabsmin = MIN(newabsmin, REALABS(proofset->vals[i]));
1271 }
1272
1273 SCIPsetDebugMsg(set, "coefficient tightening: [%.15g,%.15g] -> [%.15g,%.15g] (nnz: %d, nchg: %d rhs: %.15g)\n",
1274 absmin, absmax, newabsmin, newabsmax, SCIPproofsetGetNVars(proofset), *nchgcoefs, proofsetGetRhs(proofset));
1275 printf("coefficient tightening: [%.15g,%.15g] -> [%.15g,%.15g] (nnz: %d, nchg: %d rhs: %.15g)\n",
1276 absmin, absmax, newabsmin, newabsmax, SCIPproofsetGetNVars(proofset), *nchgcoefs, proofsetGetRhs(proofset));
1277 }
1278#endif
1279}
1280
1281/** try to generate alternative proofs by applying subadditive functions */
1282static
1284 SCIP_CONFLICT* conflict, /**< conflict analysis data */
1285 SCIP_SET* set, /**< global SCIP settings */
1286 SCIP_STAT* stat, /**< dynamic SCIP statistics */
1287 SCIP_PROB* transprob, /**< transformed problem */
1288 SCIP_TREE* tree, /**< tree data */
1289 BMS_BLKMEM* blkmem, /**< block memory */
1290 SCIP_AGGRROW* proofrow, /**< proof rows data */
1291 SCIP_Real* curvarlbs, /**< current lower bounds of active problem variables */
1292 SCIP_Real* curvarubs, /**< current upper bounds of active problem variables */
1293 SCIP_CONFTYPE conflicttype /**< type of the conflict */
1294 )
1295{
1296 SCIP_VAR** vars;
1297 SCIP_SOL* refsol;
1298 SCIP_Real* cutcoefs;
1299 SCIP_Real cutefficacy;
1300 SCIP_Real cutrhs;
1301 SCIP_Real proofefficacy;
1302 SCIP_Real efficacynorm;
1303 SCIP_Bool islocal;
1304 SCIP_Bool cutsuccess;
1305 SCIP_Bool success;
1306 SCIP_Bool infdelta;
1307 int* cutinds;
1308 int* inds;
1309 int cutnnz;
1310 int nnz;
1311 int nvars;
1312 int i;
1313
1314 vars = SCIPprobGetVars(transprob);
1315 nvars = SCIPprobGetNVars(transprob);
1316
1317 inds = SCIPaggrRowGetInds(proofrow);
1318 nnz = SCIPaggrRowGetNNz(proofrow);
1319
1320 proofefficacy = SCIPaggrRowGetMinActivity(set, transprob, proofrow, curvarlbs, curvarubs, &infdelta);
1321
1322 if( infdelta )
1323 return SCIP_OKAY;
1324
1325 proofefficacy -= SCIPaggrRowGetRhs(proofrow);
1326
1327 efficacynorm = SCIPaggrRowCalcEfficacyNorm(set->scip, proofrow);
1328 proofefficacy /= MAX(1e-6, efficacynorm);
1329
1330 /* create reference solution */
1331 SCIP_CALL( SCIPcreateSol(set->scip, &refsol, NULL) );
1332
1333 /* initialize with average solution */
1334 for( i = 0; i < nvars; i++ )
1335 {
1336 SCIP_CALL( SCIPsolSetVal(refsol, set, stat, tree, vars[i], SCIPvarGetAvgSol(vars[i])) );
1337 }
1338
1339 /* set all variables that are part of the proof to its active local bound */
1340 for( i = 0; i < nnz; i++ )
1341 {
1342 SCIP_Real val = SCIPaggrRowGetProbvarValue(proofrow, inds[i]);
1343
1344 if( val > 0.0 )
1345 {
1346 SCIP_CALL( SCIPsolSetVal(refsol, set, stat, tree, vars[inds[i]], curvarubs[inds[i]]) );
1347 }
1348 else
1349 {
1350 SCIP_CALL( SCIPsolSetVal(refsol, set, stat, tree, vars[inds[i]], curvarlbs[inds[i]]) );
1351 }
1352 }
1353
1354 SCIP_CALL( SCIPsetAllocBufferArray(set, &cutcoefs, nvars) );
1355 SCIP_CALL( SCIPsetAllocBufferArray(set, &cutinds, nvars) );
1356
1357 cutnnz = 0;
1358 cutefficacy = -SCIPsetInfinity(set);
1359
1360 /* apply flow cover */
1361 SCIP_CALL( SCIPcalcFlowCover(set->scip, refsol, POSTPROCESS, BOUNDSWITCH, ALLOWLOCAL, proofrow, \
1362 cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy, NULL, &islocal, &cutsuccess) );
1363 success = cutsuccess;
1364
1365 /* apply MIR */
1367 NULL, NULL, MINFRAC, MAXFRAC, proofrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy, NULL, \
1368 &islocal, &cutsuccess) );
1369 success = (success || cutsuccess);
1370
1371 /* replace the current proof */
1372 if( success && !islocal && SCIPsetIsPositive(set, cutefficacy) && cutefficacy * nnz > proofefficacy * cutnnz )
1373 {
1374 SCIP_PROOFSET* alternativeproofset;
1375 SCIP_Bool redundant;
1376 int nchgcoefs;
1377
1378 SCIP_CALL( proofsetCreate(&alternativeproofset, blkmem) );
1380
1381 SCIP_CALL( proofsetAddSparseData(alternativeproofset, blkmem, cutcoefs, cutinds, cutnnz, cutrhs) );
1382
1383 /* apply coefficient tightening */
1384 tightenCoefficients(set, alternativeproofset, &nchgcoefs, &redundant);
1385
1386 if( !redundant )
1387 {
1388 SCIP_CALL( conflictInsertProofset(conflict, set, alternativeproofset) );
1389 }
1390 else
1391 {
1392 SCIPproofsetFree(&alternativeproofset, blkmem);
1393 }
1394 } /*lint !e438*/
1395
1396 SCIPsetFreeBufferArray(set, &cutinds);
1397 SCIPsetFreeBufferArray(set, &cutcoefs);
1398
1399 SCIP_CALL( SCIPfreeSol(set->scip, &refsol) );
1400
1401 return SCIP_OKAY;
1402}
1403
1404/** tighten a given infeasibility proof a^Tx <= b with minact > b w.r.t. local bounds
1405 *
1406 * 1) Apply cut generating functions
1407 * - c-MIR
1408 * - Flow-cover
1409 * - TODO: implement other subadditive functions
1410 * 2) Remove continuous variables contributing with its global bound
1411 * - TODO: implement a variant of non-zero-cancellation
1412 */
1413static
1415 SCIP_CONFLICT* conflict, /**< conflict analysis data */
1416 SCIP_SET* set, /**< global SCIP settings */
1417 SCIP_STAT* stat, /**< dynamic SCIP statistics */
1418 BMS_BLKMEM* blkmem, /**< block memory */
1419 SCIP_PROB* transprob, /**< transformed problem */
1420 SCIP_TREE* tree, /**< tree data */
1421 SCIP_AGGRROW* proofrow, /**< aggregated row representing the proof */
1422 int validdepth, /**< depth where the proof is valid */
1423 SCIP_Real* curvarlbs, /**< current lower bounds of active problem variables */
1424 SCIP_Real* curvarubs, /**< current upper bounds of active problem variables */
1425 SCIP_Bool initialproof /**< do we analyze the initial reason of infeasibility? */
1426 )
1427{
1428 SCIP_VAR** vars;
1429 SCIP_Real* vals;
1430 int* inds;
1431 SCIP_PROOFSET* proofset;
1432 SCIP_Bool valid;
1433 SCIP_Bool redundant;
1434 int nnz;
1435 int nchgcoefs;
1436 int nbinvars;
1437 int ncontvars;
1438 int nintvars;
1439 int i;
1440
1441 assert(conflict->proofset != NULL);
1442 assert(curvarlbs != NULL);
1443 assert(curvarubs != NULL);
1444
1445 vars = SCIPprobGetVars(transprob);
1446 nbinvars = 0;
1447 nintvars = 0;
1448 ncontvars = 0;
1449
1450 inds = SCIPaggrRowGetInds(proofrow);
1451 nnz = SCIPaggrRowGetNNz(proofrow);
1452
1453 /* count number of binary, integer, and continuous variables */
1454 for( i = 0; i < nnz; i++ )
1455 {
1456 assert(SCIPvarGetProbindex(vars[inds[i]]) == inds[i]);
1457
1458 if( SCIPvarIsBinary(vars[inds[i]]) )
1459 ++nbinvars;
1460 else if( SCIPvarIsIntegral(vars[inds[i]]) )
1461 ++nintvars;
1462 else
1463 ++ncontvars;
1464 }
1465
1466 SCIPsetDebugMsg(set, "start dual proof tightening:\n");
1467 SCIPsetDebugMsg(set, "-> tighten dual proof: nvars=%d (bin=%d, int=%d, cont=%d)\n",
1468 nnz, nbinvars, nintvars, ncontvars);
1469 debugPrintViolationInfo(set, SCIPaggrRowGetMinActivity(set, transprob, proofrow, curvarlbs, curvarubs, NULL), SCIPaggrRowGetRhs(proofrow), NULL);
1470
1471 /* try to find an alternative proof of local infeasibility that is stronger */
1472 if( set->conf_sepaaltproofs )
1473 {
1474 SCIP_CALL( separateAlternativeProofs(conflict, set, stat, transprob, tree, blkmem, proofrow, curvarlbs, curvarubs,
1475 conflict->conflictset->conflicttype) );
1476 }
1477
1478 if( initialproof )
1479 proofset = conflict->proofset;
1480 else
1481 {
1482 SCIP_CALL( proofsetCreate(&proofset, blkmem) );
1483 }
1484
1485 /* start with a proofset containing all variables with a non-zero coefficient in the dual proof */
1486 SCIP_CALL( proofsetAddAggrrow(proofset, set, blkmem, proofrow) );
1487 proofset->conflicttype = conflict->conflictset->conflicttype;
1488 proofset->validdepth = validdepth;
1489
1490 /* get proof data */
1491 vals = proofsetGetVals(proofset);
1492 inds = proofsetGetInds(proofset);
1493 nnz = SCIPproofsetGetNVars(proofset);
1494
1495#ifndef NDEBUG
1496 for( i = 0; i < nnz; i++ )
1497 {
1498 int idx = inds[i];
1499 if( vals[i] > 0.0 )
1500 assert(!SCIPsetIsInfinity(set, -curvarlbs[idx]));
1501 if( vals[i] < 0.0 )
1502 assert(!SCIPsetIsInfinity(set, curvarubs[idx]));
1503 }
1504#endif
1505
1506 /* remove continuous variable contributing with their global bound
1507 *
1508 * todo: check whether we also want to do that for bound exceeding proofs, but then we cannot update the
1509 * conflict anymore
1510 */
1511 if( proofset->conflicttype == SCIP_CONFTYPE_INFEASLP )
1512 {
1513 /* remove all continuous variables that have equal global and local bounds (ub or lb depend on the sign)
1514 * from the proof
1515 */
1516
1517 for( i = 0; i < nnz && nnz > 1; )
1518 {
1519 SCIP_Real val;
1520 int idx = inds[i];
1521
1522 assert(vars[idx] != NULL);
1523
1524 val = vals[i];
1525 assert(!SCIPsetIsZero(set, val));
1526
1527 /* skip integral variables */
1529 {
1530 i++;
1531 continue;
1532 }
1533 else
1534 {
1535 SCIP_Real glbbd;
1536 SCIP_Real locbd;
1537
1538 /* get appropriate global and local bounds */
1539 glbbd = (val < 0.0 ? SCIPvarGetUbGlobal(vars[idx]) : SCIPvarGetLbGlobal(vars[idx]));
1540 locbd = (val < 0.0 ? curvarubs[idx] : curvarlbs[idx]);
1541
1542 if( !SCIPsetIsEQ(set, glbbd, locbd) )
1543 {
1544 i++;
1545 continue;
1546 }
1547
1548 SCIPsetDebugMsg(set, "-> remove continuous variable <%s>: glb=[%g,%g], loc=[%g,%g], val=%g\n",
1549 SCIPvarGetName(vars[idx]), SCIPvarGetLbGlobal(vars[idx]), SCIPvarGetUbGlobal(vars[idx]),
1550 curvarlbs[idx], curvarubs[idx], val);
1551
1552 proofsetCancelVarWithBound(proofset, set, vars[idx], i, &valid);
1553 assert(valid); /* this should be always fulfilled at this place */
1554
1555 --nnz;
1556 }
1557 }
1558 }
1559
1560 /* apply coefficient tightening to initial proof */
1561 tightenCoefficients(set, proofset, &nchgcoefs, &redundant);
1562
1563 /* it can happen that the constraints is almost globally redundant w.r.t to the maximal activity,
1564 * e.g., due to numerics. in this case, we want to discard the proof
1565 */
1566 if( redundant )
1567 {
1568#ifndef NDEBUG
1569 SCIP_Real eps = MIN(0.01, 10.0*set->num_feastol);
1570 assert(proofset->rhs - getMaxActivity(set, transprob, proofset->vals, proofset->inds, proofset->nnz, NULL, NULL) < eps);
1571#endif
1572 if( initialproof )
1573 {
1574 proofsetClear(proofset);
1575 }
1576 else
1577 {
1578 SCIPproofsetFree(&proofset, blkmem);
1579 }
1580 }
1581 else
1582 {
1583 if( !initialproof )
1584 {
1585 SCIP_CALL( conflictInsertProofset(conflict, set, proofset) );
1586 }
1587
1588 if( nchgcoefs > 0 )
1589 {
1590 if( proofset->conflicttype == SCIP_CONFTYPE_INFEASLP )
1592 else if( proofset->conflicttype == SCIP_CONFTYPE_BNDEXCEEDING )
1594 }
1595 }
1596
1597 return SCIP_OKAY;
1598}
1599
1600/** perform conflict analysis based on a dual unbounded ray
1601 *
1602 * given an aggregation of rows lhs <= a^Tx such that lhs > maxactivity. if the constraint has size one we add a
1603 * bound change instead of the constraint.
1604 */
1606 SCIP_CONFLICT* conflict, /**< conflict analysis data */
1607 SCIP_SET* set, /**< global SCIP settings */
1608 SCIP_STAT* stat, /**< dynamic SCIP statistics */
1609 BMS_BLKMEM* blkmem, /**< block memory */
1610 SCIP_PROB* origprob, /**< original problem */
1611 SCIP_PROB* transprob, /**< transformed problem */
1612 SCIP_TREE* tree, /**< tree data */
1613 SCIP_REOPT* reopt, /**< reoptimization data */
1614 SCIP_LP* lp, /**< LP data */
1615 SCIP_AGGRROW* proofrow, /**< aggregated row representing the proof */
1616 int validdepth, /**< valid depth of the dual proof */
1617 SCIP_Real* curvarlbs, /**< current lower bounds of active problem variables */
1618 SCIP_Real* curvarubs, /**< current upper bounds of active problem variables */
1619 SCIP_Bool initialproof, /**< do we analyze the initial reason of infeasibility? */
1620 SCIP_Bool* globalinfeasible, /**< pointer to store whether global infeasibility could be proven */
1621 SCIP_Bool* success /**< pointer to store success result */
1622 )
1623{
1624 SCIP_Real rhs;
1625 SCIP_Real minact;
1626 SCIP_Bool infdelta;
1627 int nnz;
1628
1629 assert(set != NULL);
1630 assert(transprob != NULL);
1631 assert(validdepth >= 0);
1632 assert(validdepth == 0 || validdepth < SCIPtreeGetFocusDepth(tree));
1633
1634 /* get sparse data */
1635 nnz = SCIPaggrRowGetNNz(proofrow);
1636 rhs = SCIPaggrRowGetRhs(proofrow);
1637
1638 *globalinfeasible = FALSE;
1639 *success = FALSE;
1640
1641 /* get minimal activity w.r.t. local bounds */
1642 minact = SCIPaggrRowGetMinActivity(set, transprob, proofrow, curvarlbs, curvarubs, &infdelta);
1643
1644 if( infdelta )
1645 return SCIP_OKAY;
1646
1647 /* only run is the proof proves local infeasibility */
1648 if( SCIPsetIsFeasLE(set, minact, rhs) )
1649 return SCIP_OKAY;
1650
1651 /* if the farkas-proof is empty, the node and its sub tree can be cut off completely */
1652 if( nnz == 0 )
1653 {
1654 SCIPsetDebugMsg(set, " -> empty farkas-proof in depth %d cuts off sub tree at depth %d\n", SCIPtreeGetFocusDepth(tree), validdepth);
1655
1656 SCIP_CALL( SCIPnodeCutoff(tree->path[validdepth], set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
1657
1658 *globalinfeasible = TRUE;
1659 *success = TRUE;
1660
1661 ++conflict->ndualproofsinfsuccess;
1662
1663 return SCIP_OKAY;
1664 }
1665
1666 /* try to enforce the constraint based on a dual ray */
1667 SCIP_CALL( tightenDualproof(conflict, set, stat, blkmem, transprob, tree, proofrow, validdepth,
1668 curvarlbs, curvarubs, initialproof) );
1669
1670 if( *globalinfeasible )
1671 {
1672 SCIPsetDebugMsg(set, "detect global: cutoff root node\n");
1673 SCIP_CALL( SCIPnodeCutoff(tree->path[0], set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
1674 *success = TRUE;
1675
1676 ++conflict->ndualproofsinfsuccess;
1677 }
1678
1679 return SCIP_OKAY;
1680}
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 SCIP_Bool
Definition: def.h:91
#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:4212
SCIP_Bool SCIPcutsTightenCoefficients(SCIP *scip, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, int *nchgcoefs)
Definition: cuts.c:1527
SCIP_Real SCIPaggrRowGetRhs(SCIP_AGGRROW *aggrrow)
Definition: cuts.c:2581
int * SCIPaggrRowGetInds(SCIP_AGGRROW *aggrrow)
Definition: cuts.c:2541
int SCIPaggrRowGetNNz(SCIP_AGGRROW *aggrrow)
Definition: cuts.c:2551
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:7417
SCIP_Real SCIPaggrRowCalcEfficacyNorm(SCIP *scip, SCIP_AGGRROW *aggrrow)
Definition: cuts.c:2158
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7493
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:184
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:841
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
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:6293
SCIP_Bool SCIPsetIsFeasLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6641
SCIP_Bool SCIPsetIsPositive(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6322
SCIP_Bool SCIPsetIsLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6257
SCIP_Real SCIPsetFeasFloor(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6764
SCIP_Bool SCIPsetIsEQ(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6221
SCIP_Real SCIPsetInfinity(SCIP_SET *set)
Definition: set.c:6064
SCIP_Bool SCIPsetIsLT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6239
SCIP_Bool SCIPsetIsInfinity(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6199
SCIP_Bool SCIPsetIsGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6275
SCIP_Bool SCIPsetIsIntegral(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6344
SCIP_Bool SCIPsetIsZero(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6311
int SCIPsetCalcMemGrowSize(SCIP_SET *set, int num)
Definition: set.c:5764
SCIP_Bool SCIPsetIsNegative(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6333
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
Definition: struct_stat.h:129
SCIP_NODE ** path
Definition: struct_tree.h:188
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
Definition: heur_padm.c:135
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:8377
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:8491
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:2097
SCIP_RETCODE SCIPnodeAddCons(SCIP_NODE *node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_CONS *cons)
Definition: tree.c:1618
internal methods for branch and bound tree
@ SCIP_CONFTYPE_ALTINFPROOF
Definition: type_conflict.h:63
@ SCIP_CONFTYPE_BNDEXCEEDING
Definition: type_conflict.h:62
@ SCIP_CONFTYPE_ALTBNDPROOF
Definition: type_conflict.h:64
@ SCIP_CONFTYPE_INFEASLP
Definition: type_conflict.h:61
@ SCIP_CONFTYPE_UNKNOWN
Definition: type_conflict.h:59
enum SCIP_ConflictType SCIP_CONFTYPE
Definition: type_conflict.h:66
@ 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_OKAY
Definition: type_retcode.h:42
@ SCIP_INVALIDCALL
Definition: type_retcode.h:51
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ 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)