-
Notifications
You must be signed in to change notification settings - Fork 76
/
Copy pathCHANGELOG
9921 lines (8254 loc) · 616 KB
/
CHANGELOG
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
@page RN10 Release notes for SCIP 10
@section RN1000 SCIP 10.0.0
***************************
Features
--------
- added new fields in history to store ancestral pseudo cost updates, used in the pseudo costs branching rule to compute discounted pseudo costs.
- copy variable data pointer if no copy routine was supplied.
- added more techniques to handle reflection symmetries, in particular, for orbitopes with column reflections and matrices whose rows and columns can be permuted by a symmetry
- Dejavu can be used to compute symmetries; the source code is shipped with SCIP and incorporates sassy.
- implemented symmetry detection callbacks for cons_disjunction and cons_superindicator
- detailed information about applied symmetry handling techniques can be printed to the terminal
- added a new separator sepa_multilinear to generate flower cuts from AND constraints nonlinear product expressions.
- added functionality to deal with hypergraphs by means of efficient access to vertices, edges and intersections edges.
- added support for (transposed) network matrix detection in pub_network.h
- added a new presolver presol_implint which detects implied integral variables by detecting (transposed) network submatrices in the problem. For now, this plugin is disabled by default.
- added new plugin type for finding irreducible infeasible subsystems (IIS). Users can now include their own IIS algorithms. Basic addition and deletion based algorithm implemented in iisfinder_greedy.
- added a new data structure SCIP_DATATREE that holds serializable data and a method to export to a JSON file
- added ability to collect statistics from tables in a SCIP_DATATREE and write out as JSON file;
dialog write statistics now writes a JSON file if name of file to write ends with .json
- improve memory usage by introducing different constraint handlers for full orbitopes and packing/partitioning orbitopes
- the linking master variables for each Benders' decomposition subproblem are now stored. These can be accessed for the
generation of cut and setting up the subproblems.
- adds objective types for Benders' decomposition; the choice is to sum the subproblems objectives (classical
approach) or to use the maximum of the subproblems objectives
- added decomposition kernel search (DKS) heuristic (disabled by default). This heuristic implements a kernel search framework and can be used
both as a construction heuristic as well as an improvement heuristic. In addition, existing decomposition information can be utilized by this heuristic.
- symmetry detection does not treat implicit integer variables separately anymore, but computes symmetries based on the variable type inferred from variable bounds and implied integrality
- when solving a SCIP problem with additional decomposition information (for example, when reading a DEC file) and enabling decomposition/applybenders,
the problem is now solved in a Benders' decomposition relaxator; instead of decomposing the original SCIP instance, the relaxator builds the decomposed problem in
sub-SCIPs and solves it via default Benders' Decomposition; a solution to the original (undecomposed) problem is now made available by the relaxator;
the SCIP shell dialog "display statistics" now also prints the statistics from solving the Benders' decomposition in the relaxator
Performance improvements
------------------------
- reimplemented SCIPvarGetActiveRepresentatives() by using dense arrays to avoid repeated resorting.
Examples and applications
-------------------------
- Add PBSolver application to solve pseudoboolean instances in OPB and WBO format while complying with PB competition rules
- Coloring: new parameter branching/coloring/strategy to choose the least/most fractional variable for branching
Interface changes
-----------------
### Deprecations
- The variable type \ref SCIP_VARTYPE_IMPLINT is deprecated in favor of a new enum \ref SCIP_IMPLINTTYPE that indicates if a
variable is implied integral, independent of the variable type.
The problem variable arrays is still sorted as:
```
(0) | binary | integer | implied integral | continuous | (nvars),
```
where the implied integral subsection is now subdivided into 3 parts (left to right):
```
| binary implied integral | integer implied integral | continuous implied integral |
```
SCIP 10 still supports using SCIP_VARTYPE_IMPLINT for backward compatibility, see SCIPcreateVar() and SCIPchgVarType() for more details.
SCIP 11 will remove SCIP_VARTYPE_IMPLINT.
### New and changed callbacks
- added a new callback TABLE_COLLECT for the table plugin that collects the data for the specific statistics table in a SCIP_DATATREE object
- for a table plugin, only one of the callbacks TABLE_COLLECT or TABLE_OUTPUT needs to be implemented, but implementing both is preferred;
if TABLE_OUTPUT is omitted, then SCIP tries to print a table from the data given by TABLE_COLLECT
- the event SCIP_EVENTTYPE_TYPECHANGED is no longer generated if a variable becomes implied integral
- new event SCIP_EVENTTYPE_IMPLTYPECHANGED is generated if a variable is declared implied integral, this event is included in the set SCIP_EVENTTYPE_VARCHANGED
- the callback SCIP_DECL_EXPRINTEGRALITY, which returns the integrality of an expression, had its fourth argument change from SCIP_Bool* to SCIP_IMPLINTTYPE*, to represent implied integrality in nonlinear expressions, that is an implied integral type of an auxiliary variable if the expression were assigned to it
- new event SCIP_EVENTTYPE_DUALBOUNDIMPROVED is generated whenever the global dual bound is improved
- new event mask SCIP_EVENTTYPE_GAPUPDATED for catching updates in primal or dual bound
- added new sorting functions SCIPsortRealPtrPtr(), ...
### Deleted and changed API methods
- SCIPgetProbvarLinearSum: remove parameter mergemultiples, which is now automatically true with the new implementation of SCIPvarGetActiveRepresentatives.
- SCIPcreateRow*(), SCIPaddVarToRow(), SCIPaddVarsToRow(), SCIPaddVarsToRowSameCoef() can now only be called in the solving stage,
because otherwise the LP is not yet available and the row data is invalid.
- intvar removed from arguments for SCIPcreateConsPseudobooleanWithConss(), SCIPcreateConsPseudoboolean(), and SCIPcreateConsBasicPseudoboolean() due to dysfunctionality of non-linear objective reformulation with pseudoboolean constraint
- ndelconss added to arguments for SCIPcleanupConssLinear() and SCIPcleanupConssKnapsack() to directly delete empty redundant constraints before creating problem matrix
- copyiisfinders added to arguments for SCIPcopyPlugins() (16th position)
- SCIPcreateConsOrbitope() deleted two arguments and changed position of another argument
- deprecated SCIPsubversion(), will be removed
- SCIPvarCalcDistributionParameters(): argument impltype added (5th position)
- SCIPpermuteProb(): argument permuteimplvars has been replaced by new arguments permutebinimplvars, permuteintimplvars, and permutecontimplvars
- SCIPgetLPBranchCands(): implied integral variables with integrality constraints are included in nlpcands stored in lpcands at the back
- SCIPgetNLPBranchCands(): implied integral variables with integrality constraints are included
- SCIPgetSolVarsData(): argument nimplvars has been replaced by new arguments nbinimplvars, nintimplvars, and ncontimplvars
- SCIPexprSetIntegrality(): set argument generalized from SCIP_Bool integral to SCIP_IMPLINTTYPE integrality (4th position)
- Temporarily for SCIP 10 only: Creating a variable SCIPcreateVar() with type SCIP_VARTYPE_IMPLINT creates a variable of type SCIP_VARTYPE_CONTINUOUS and implied integral type SCIP_IMPLINTTYPE_WEAK instead
- Temporarily for SCIP 10 only: SCIPchgVarType() converts a call with type SCIP_VARTYPE_IMPLINT into a call of SCIPchgVarImplType() with type SCIP_IMPLINTTYPE_WEAK
- SCIPapplyBendersDecomposition has been removed. This was originally used to apply Benders' decomposition from a
supplied decomposition structure. The application of Benders' decomposition now occurs in benders_relax.
### New API functions
- SCIPhistoryUpdateAncPseudocost(), SCIPvarUpdateAncPseudocost() for updating the ancestral pseudo cost fields in variable history
- SCIPhistoryGetAncPseudocost(), SCIPhistoryGetAncPseudocostCount(), SCIPhistoryIsAncPseudocostEmpty(), SCIPgetVarAncPseudocostVal(),
SCIPvarGetAncPseudocost() for retrieving the values related to ancestral pseudo cost fields in variable history
- SCIPgetAvgDPseudocostScore(), SCIPgetVarDPseudocostScore() for computing the discounted pseudo cost scores using ancestral pseudo costs
- SCIPboundchgGetLPSolVal() for accessing the LP solution value in the branching data of the bound change
- SCIPclearSymgraph() and SCIPcopySymgraphAsSubgraph() to clear and copy as symmetry detection graph, respectively
- SCIPincludeSepaMultilinear() to include the new multilinear cut separator
- SCIPhypergraphCreate(), SCIPhypergraphClear(), SCIPhypergraphFree(), SCIPhypergraphAddVertex(), SCIPhypergraphAddEdge(), SCIPhypergraphIsValid() and SCIPhypergraphComputeVerticesEdges() for building and deleting hypergraphs, SCIPhypergraphComputeOverlaps(), SCIPhypergraphOverlapFind(), SCIPhypergraphIntersectEdges(), SCIPhypergraphComputeOverlapsEdges(), SCIPhypergraphComputeVerticesOverlaps(), SCIPhypergraphOverlapsDisjoint() to deal with pair-wise intersections of hyperedges, SCIPhypergraphIterInit(), SCIPhypergraphIterClear(), SCIPhypergraphIterStart(), SCIPhypergraphIterValid(), SCIPhypergraphIterNext(), SCIPhypergraphIterBase(), SCIPhypergraphIterAdjacent(), SCIPhypergraphIterMinVertex(), SCIPhypergraphIterOverlap() for iterating over adjacent edges, SCIPhypergraphHasVertexEdges() SCIPhypergraphHasOverlaps(), SCIPhypergraphHasOverlapsEdges(), SCIPhypergraphHasVertexOverlaps(), SCIPhypergraphGetNVertices(), SCIPhypergraphGetNEdges(), SCIPhypergraphBlkmem(), SCIPhypergraphGetNOverlaps(), SCIPhypergraphVertexData(), SCIPhypergraphEdgeData(), SCIPhypergraphEdgeSize(), SCIPhypergraphEdgeVertices(), SCIPhypergraphVertexEdgesFirst(), SCIPhypergraphVertexEdgesBeyond(), SCIPhypergraphVertexEdgesGetAtIndex(), SCIPhypergraphOverlapData(), SCIPhypergraphOverlapSize(), SCIPhypergraphOverlapVertices() SCIPhypergraphEdgesOverlapsFirst(), SCIPhypergraphEdgesOverlapsBeyond(), SCIPhypergraphEdgesOverlapsGetAtIndex(), SCIPhypergraphOverlapsEdgesFirst(), SCIPhypergraphOverlapsEdgesBeyond(), SCIPhypergraphOverlapsEdgesGetAtIndex(), SCIPhypergraphVertexOverlapsFirst(), SCIPhypergraphVertexOverlapsBeyond() and SCIPhypergraphVertexOverlapsGetAtIndex() to query information about vertices, edges and overlaps as well as their incidences.
- SCIPdebugClearSol() for clearing the debug solution
- Renamed XML functions to avoid name clash with libxml2 by adding "SCIP": SCIPxmlProcess(), SCIPxmlNewNode(), SCIPxmlNewAttr(), SCIPxmlAddAttr(), SCIPxmlAppendChild(), SCIPxmlFreeNode(), SCIPxmlShowNode(), SCIPxmlGetAttrval(), SCIPxmlFirstNode(), SCIPxmlNextNode(), SCIPxmlFindNode(), SCIPxmlFindNodeMaxdepth(), SCIPxmlNextSibl(), SCIPxmlPrevSibl(), SCIPxmlFirstChild(), SCIPxmlLastChild(), SCIPxmlGetName(), SCIPxmlGetLine(), SCIPxmlGetData(), SCIPxmlFindPcdata().
- SCIPincludePresolImplint() to include the new implied integral presolver
- SCIPnetmatdecCreate() and SCIPnetmatdecFree() for creating and deleting a network matrix decomposition. SCIPnetmatdecTryAddCol() and SCIPnetmatdecTryAddRow() are used to add columns and rows of the matrix to the decomposition. SCIPnetmatdecContainsRow() and SCIPnetmatdecContainsColumn() check if the decomposition contains the given row or columns. SCIPnetmatdecRemoveComponent() can remove connected components from the decomposition. SCIPnetmatdecCreateDiGraph() can be used to expose the underlying digraph. SCIPnetmatdecIsMinimal() and SCIPnetmatdecVerifyCycle() check if certain invariants of the decomposition are satisfied and are used in tests.
- SCIPfreeReaderdataCor(), SCIPfreeReaderdataTim() and SCIPfreeReaderdataSto() for freeing the data for the COR, TIM and
STO readers respectively. These readers are all used when reading an SMPS instance.
- SCIPdialogIsHidden(), SCIPdialogSetHidden() to determine whether a dialog should be hidden in help list
- added SCIPincludeIISfinder(), SCIPincludeIISfinderBasic(), SCIPsetIISfinderCopy(), SCIPsetIISfinderFree(), SCIPgenerateIIS(), SCIPfindIISfinder(), SCIPgetIISfinders(), SCIPgetNIISfinders(), SCIPsetIISfinderPriority(), SCIPgetIIS()
- added SCIPiisfinderGetName(), SCIPiisfinderGetData(), SCIPiisfinderGetDesc(), SCIPiisfinderGetPriority(), SCIPiisfinderSetData(), SCIPiisfinderGetTime(), SCIPiisfinderInfoMessage(), SCIPiisGetTime(), SCIPiisIsSubscipInfeasible(), SCIPiisIsSubscipIrreducible(), SCIPiisGetNNodes(), SCIPiisSetSubscipInfeasible(), SCIPiisSetSubscipIrreducible(), SCIPiisAddNNodes(), SCIPiisGetRandnumgen(), SCIPiisGetSubscip()
- functions to create, modify, and free SCIP_DATATREE objects and to print as JSON or table (see pub_datatree.h and scip_datatree.h)
- SCIPcollect*Statistics() for every SCIPprint*Statistics() in scip_solvingstats.h
- SCIPprintStatisticsJson() to output a JSON string of the table statistics data
- SCIPstatusName() to get a string representation of SCIP_STATUS
- SCIPbendersGetSubproblemMasterVars(), SCIPbendersGetNSubproblemMasterVars(), SCIPbendersGetSubproblemMasterVarsData()
are available to get the linking master variables for each subproblem and details about the number of binary and integer.
- SCIPsetBendersObjectiveType() for setting the objective type for the aggregation of the Benders' decompostion
subproblems
- SCIPbendersGetObjectiveType() for returning the objective type for the aggregation of the Benders' decomposition
subproblems
- SCIPbenderGetMasterAuxiliaryVar() returns the master auxiliary variable
- added SCIPcreateVarImpl() and SCIPcreateObjVarImpl(), which behave identically to SCIPcreateVar() and SCIPcreateObjVar(), respectively, but have an additional argument for the new implied integral type flag (8th position)
- added SCIPchgVarImplType(), SCIPvarGetImplType(), SCIPvarIsImpliedIntegral() to control and query implied integrality
- added SCIPvarIsNonimpliedIntegral() to query if a variable is integral but not implied integral
- added SCIPgetNOrigBinImplVars(), SCIPgetNOrigIntImplVars(), SCIPgetNOrigContImplVars() to query the number of implied integral variables of each type in original problem; note that SCIPgetNOrigBinVars(), SCIPgetNOrigIntVars(), and SCIPgetNOrigContVars() no longer include the implied integral variables in their counts
- added SCIPgetNBinImplVars(), SCIPgetNIntImplVars(), SCIPgetNContImplVars() to query the number of implied integral variables of each type in current problem; note that SCIPgetNBinVars(), SCIPgetNIntVars(), and SCIPgetNContVars() no longer include the implied integral variables in their counts
- added SCIPcolIsImpliedIntegral()
- added SCIPvarsCountTypes() to determine the variable type count distribution for an array of variables
- added SCIPeventGetOldImplType() and SCIPeventGetNewImplType() to query the new event SCIP_EVENTTYPE_IMPLTYPECHANGED
- added SCIPexprGetIntegrality(), which in addition to the existing function SCIPexprIsIntegral() provides information about the presence of weakly implied integral variables
- added SCIPincludeRelaxBenders(), which is used to include the Benders' decomposition relaxator.
- added SCIPgetMasterProblemRelaxBenders() for retrieving the master problem SCIP instance from the Benders' decomposition relaxator.
### Changes in preprocessor macros
- removed `#define` of `strcasecmp` and `strncasecmp` (in case of Windows builds) in scip/def.h;
use SCIPstr(n)casecmp() (scip/pub_misc.h) instead
- SCIPincludeConshdlrOrbitopePP(), SCIPcreateConsOrbitopePP(), SCIPcreateConsBasicOrbitopePP(), SCIPincludeConshdlrOrbitopeFull(), SCIPcreateConsOrbitopeFull(), SCIPcreateConsBasicOrbitopeFull()
- SCIP_VERSION_SUB and SCIP_SUBVERSION are deprecated
- removed SCIP_VARTYPE_IMPLINT_CHAR
### Command line interface
- help <command> now allows to display information on specific command.
- allow to hide certain commands in the help list
- add the (hidden) command "exit" to exit SCIP.
- Add iis option to create an infeasible subsystem
- Add write/iis option to write out the infeasible subsystem to file
- Add display/iis option to write out the infeasible subsystem to console
### Interfaces to external software
### Changed parameters
- heuristics/scheduler/heurtimelimit removed to avoid indeterministic behavior of scheduler heuristic, uses main time limit instead
- removed parameters "constraints/orbitope/checkpporbitope", "constraints/orbitope/sepafullorbitope", "constraints/orbitope/forceconscopy", which became superfluous
- removed reading/gmsreader/signpower
- removed benders/default/numthreads, multi-threading support for Benders' decomposition has been temporarily disabled.
- restricted range of parameter propagating/symmetry/sstleadervartype to [1,7]; its new default value is 6
### New parameters
- branching/pscost/discountfactor, branching/relpscost/discountfactor as the discount factor for ancestral pseudo costs in pscost and relpscost branching rules
- branching/discountedpscost to enable/disable recording ancestral pseudo costs
- new parameter "propagating/symmetry/handlesignedorbitopes" to control whether special symmetry handling techniques for orbitopes whose columns can be (partially) reflected shall be applied
- new parameter "propagating/symmetry/usesimplesgncomp" to control whether symmetry components all of whose variables are simultaneously reflected by a symmetry shall be handled by a special inequality
- new parameter "propagating/symmetry/dispsyminfo" to control whether information about which symmetry handling methods are applied are printed
- new parameter "presolving/implint/convertintegers" to control whether implied integrality should also be detected for enforced integral variables
- new parameter "presolving/implint/columnrowratio" indicates the ratio of rows/columns where the row-wise network matrix detection algorithm is used instead of the column-wise network matrix detection algorithm
- new parameter "presolving/implint/numericslimit" determines the limit for absolute integral coefficients beyond which the corresponding rows and variables are excluded from implied integrality detection
- iis/minimal, iis/nodes, iis/removedbounds, iis/removeunusedvars, iis/silent, iis/stopafterone, iis/time, iis/greedy/additive, iis/greedy/conservative, iis/greedy/delafteradd, iis/greedy/dynamicreordering, iis/greedy/maxbatchsize, iis/greedy/maxrelbatchsize, iis/greedy/nodelimperiter, iis/greedy/priority, iis/greedy/timelimperiter
- new parameters "constraints/orbitope_full/forceconscopy" and "constraints/orbitope_pp/forceconscopy" to control whether non-model constraints of type full orbitope and packing/partitioning orbitope are copied to sub-SCIPs, respectively
- new parameter "write/implintlevel" to control if integrality constraints should be written for implied integral variables (regarded by cip, mps, lp, rlp, pip, fzn, and gms writers)
- new parameter "presolving/milp/enablecliquemerging" to enable clique merging in PaPILO
- new parameter "presolving/milp/maxedgesparallel" defines the maximal amount of edges in the parallel clique merging graph
- new parameter "presolving/milp/maxedgessequential" defines the maximal amount of edges in the sequential clique merging graph
- new parameter "presolving/milp/maxcliquesize" defines the maximal size of cliques considered for clique merging
- new parameter "presolving/milp/maxgreedycalls" defines the maximal number of greedy max clique calls in a single thread
- reading/opbreader/maxintsize to define the maximal intsize above which an OPB instance is rejected
- new parameters "heuristics/dks/maxbucks", "heuristics/dks/kernelsizefactor", "heuristics/dks/addUseConss",
"heuristics/dks/linkbucksize", "heuristics/dks/translbkernel", "heuristics/dks/lesslockskernel", "heuristics/dks/usetransprob",
"heuristics/dks/buckmaxgap", "heuristics/dks/maxlinkscore", "heuristics/dks/maxbuckfrac", "heuristics/dks/maxnodes",
"heuristics/dks/usetwolevel", "heuristics/dks/usedecomp", "heuristics/dks/usebestsol", "heuristics/dks/redcostsort", "heuristics/dks/primalonly",
"heuristics/dks/redcostlogsort", "heuristics/dks/objcutoff", and "heuristics/dks/runbinprobsonly" to control heuristic decomposition kernel search
- new parameters "relaxing/benders/continueorig" and "relaxing/benders/nodelimit" for controlling the behaviour of the
Benders' decomposition relaxator. The "continueorig" parameter indicates whether the original problem should continue
solving after the completion of the Benders' decomposition algorithm if the problem is not solved to optimality. The
"nodelimit" parameter allows the user to provide a node limit for the Benders' decomposition master problem (by
default the limits from the original SCIP instance are copied to the master problem).
### Data structures
- added structs SCIP_IISFINDER, SCIP_IISFINDERDATA, SCIP_IIS
- added struct SCIP_DATATREE to model generic serializable data; new enum SCIP_DATATREE_VALUETYPE
Deleted files
-------------
Testing
-------
Build system
------------
- changed the default for TPI to tny
### Makefile
- revised SANITIZE options: removed SANITIZE=full, added SANITIZE=thread, SANITIZE=address, and SANITIZE=memory to enable
thread, address, and memory sanitizers, respectively, in addition to undefined behavior sanitizer;
changed default to SANITIZE=false
- added build flag MPFR (default: false) to link with the multiprecision floating-point library, needed when SoPlex is also
built with MPFR=true for precision boosting in rational solving mode
- the symlink $(LIBDIR)/include/papilo should now point to the `src` subdirectory of a PaPILO repository or the headers directory
of a PaPILO installation without TBB; pointing to the directory of a PaPILO repository still works, but is deprecated
- removed option to link TBB library, as this is not used by default when PaPILO has not been built via cmake
(use USRCXXFLAGS=-DPAPILO_TBB USRLDFLAGS=-ltbb to enable TBB for PaPILO)
### Cmake
- increased minimal required cmake version to 3.11
- removed automatic download and build of Bliss during cmake configuration when -DSYM=(s)bliss;
please build and install from https://github.com/scipopt/bliss before and specify -DBLISS_DIR
- replaced `SANITIZE_XYZ=(on|off)` options by `SANITIZE=(on|off|thread|address|memory)`;
undefined behavior sanitizer is always enabled if not `SANITIZE=off` (the default)
- scip-config.cmake now defines a variable SCIP_COMPILE_FLAGS, which could be used to compile code that builds against SCIP via cmake;
currently, this only passes on the sanitizer flags that were used to build libscip
Fixed bugs
----------
- fixed bug related to unreleased data for the Benders' decomposition framework. When reading an SMPS file and applying
Benders' decomposition, data is created that was not correctly released. Also, data within the Benders' decomposition
framework was not appropriately reset. The data is now released/reset as expected.
- To fix a bug where duplicate cuts from different constraint handlers were not recognized, SCIPrealHash() was changed
to be stable around shortly representable numbers, and a numerical tolerance for comparing cutting plane efficacy for the aggregation
separator is introduced.
- accept fractional continuous implied integral variables in heuristic completesol
Miscellaneous
-------------
- We now use sassy as shipped with dejavu.
- add objective offset instead of objective offset variable in cip reader
- the solchecker tool is extended for rational values
- updated ampl/mp to v4.0.0
- removed 4th number in SCIP version; new format is major.minor.patch
Known bugs
----------
@page RN9 Release notes for SCIP 9
@section RN930 SCIP 9.3.0
*************************
Features
--------
- simplify expressions of nonlinear constraints in MPS and LP writing to increase chance that they are recognized as quadratic
Performance improvements
------------------------
- extended SOC detection to simple bilinear constraints, e.g., x*y >= 1
Examples and applications
-------------------------
Interface changes
-----------------
### New and changed callbacks
### New API functions
- SCIPdisplaySymmetryGenerators() and SCIPdialogExecDisplaySymmetry() to display generators of symmetry group
### Command line interface
### Interfaces to external software
### Changed parameters
### New parameters
### Data structures
Fixed bugs
----------
Miscellaneous
-------------
- updated description of paramater misc/usesymmetry
@section RN923 SCIP 9.2.3
*************************
Fixed bugs
----------
Build system
------------
### Cmake
### Makefile
Miscellaneous
-------------
@section RN922 SCIP 9.2.2
*************************
Fixed bugs
----------
- fixed definition of slack variables of >= constraints and ranged rows in LP interface to Gurobi
- free memory leaking singleton arrays for ignored variables in SCIPapplyHeurDualval()
- use epsilon tolerance for bound implications of dual substitutions in dualPresolve() of cons_linear
- fixed timeouts due to race conditions when using TPI=omp
- fixed issues with indexing of concurrent solvers when a solver finishes (because SCIP is too fast) before others have been created when using TPI=tny
- respect fixing if variable is declared binary in bounds section of mps file
- fixed reading mps files with short row and column names and some fixed-form mps files with spaces in row names
- force local bounds to adjusted value when fixing variable
- adds missing NULL check for Benders' subproblems in feasalt cut
- apply objective scale to pseudoboolean non-linear terms
- impose pseudoboolean cost bound without intermediate casting
- flatten aggregation graph before finishing presolve to accelerate evaluating an empty solution
- respect fixed resultants in binvarGetActiveProbindex() of branch_relpscost
- drop fixed resultants when copying pseudoboolean constraint
- correct matrix entry when resolving aggregated variables in checkSystemGF2() of cons_xor
- corrected symmetry detection graph of cons_and, cons_or, cons_xor, and cons_indicator
- correct redundancy filter in consdataCreateRedundant() of cons_bounddisjunction
- replaced unreliable comparison of node pointers by node numbers in prop_genvbounds
- allocate memory for all integral variables in applyCliqueFixings() of heur_clique
- fix conflict resolution for one particular case in cons_indicator
- make interface to nauty thread safe
- use relative epsilon tolerance to check Farkas row in SCIPlpGetDualfarkas() to avoid invalid cutoff
- fixed bug with SOS2 constraints of size that avoided a correct enforcing
Build system
------------
### Cmake
- allow to set HIGHS_DIR via -D flag as well
- reenable building and testing of SCFLP example
- fixed that compiler flags for sanitizers were not used for compiling objects of SCIP library
- prioritize local includes for unittests, examples, and applications to link the intended SCIP version
- fix detection of Gurobi 11 and 12 libs on Linux
### Makefile
- fix use of SANITIZE=full for debug builds with GCC on Linux: removed -fsanitize=leak because it cannot be used together with -fsanitize=address
- fix that make install SHARED=true missed to install libscipbase
@section RN921 SCIP 9.2.1
*************************
Fixed bugs
----------
- apply same feasibility definition in PaPILO as in SCIP to avoid numerical inconsistencies
- check variable cancellation in SCIPvarAddVlb() and SCIPvarAddVub() to avert wrong infeasibility
- SCIPfreeReoptSolve() now also clears partial solutions
- fixed bug in calculation of "fractionality score" for spatial branching candidates in cons_nonlinear
- fixed bug with installing symmetry dialog in sub-SCIPs
- added copy callbacks for presolvers dualagg and redvub, branching rules lookahead and cloud, primal heuristics dualval and repair, propagator nlobbt, and separators gauge and convexproj
- respect maximal separation rounds setting by running remaining delayed separators in last round
- replace terms consistently in applyFixings() of cons_linear to handle infinite aggregations
Build system
------------
### Cmake
- fix SCIP Optimization Suite build with -DSYM=(s)bliss and bliss being downloaded and built during configuration by cmake
- fix use of a bliss cmake installation (from https://github.com/scipopt/bliss) specified via BLISS_DIR if -DSYM=(s)bliss
### Makefile
- the check/solchecker build can now use also GMP installations by Homebrew on macOS/arm64
Miscellaneous
-------------
- the output precision for writing CIP/OPB files has been increased at several places for nonlinear constraints
- the solchecker tool now also supports SCIP solutions without unknown or infinite values
- generate an error if the same linear constraint is used by several indicator constraints
@section RN920 SCIP 9.2.0
*************************
Features
--------
- added check for absolute and relative gap limits at end of synchronization in concurrent solving mode, in order to terminate earlier;
note that if the concurrent solve is stopped due to a gap limit, the "winner" solver will have an interrupted solution status and
its primal and dual bounds may not be the best possible ones (use SCIPgetConcurrentPrimalbound() and SCIPgetConcurrentDualbound() instead)
- parse pseudoboolean constraint from CIP format (and add linear-"and"-reformulation)
Performance improvements
------------------------
- reoptimization now also stores propagations from propagators if reoptimization/saveconsprop is enabled;
the parameter will be renamed to reoptimization/saveprop in a next major release
- imposed stricter limits on the size of disconnected components which may be solved separately during presolve
- use individual slack variables also for constraints indicated by a common binary variable to use tighter formulation by default
- when computing symmetries using Nauty, iteration limits are now available to terminate Nauty early
Fixed bugs
----------
- Benders' decomposition subproblems that are always infeasible are correctly handled and the complete problem is declared infeasible
- skip linear constraint propagation if the residual activity bound cancels the side precision
- correct bound tracking to make the evaluation of primal-dual-integrals work
- skip aggregations on fixed variables in milp presolver to avoid errors for earlier versions of PaPILO
- use indices of negation counterparts and accept fixings when ordering and-resultants of pseudoboolean constraints
- update locks on model variables before removing pseudoboolean constraints in presolve
- reformulate soft pseudoboolean constraints with linear constraints if the indicator decomposition is disabled
- add workaround for recent HiGHS versions resetting the model status when changing the presolve option after a solve
- avoid hashmap key error in removal of doubletons and singletons in dual presolve of setppc constraints by updating constraints and corresponding hashmaps after each multi-aggregation
Interface changes
-----------------
### New API functions
- added SCIPtpiIsAvailable() to check whether a working task processing interface is available (TPI != none)
- added SCIPtpiGetLibraryName() and SCIPtpiGetLibraryDesc()
- SCIPdelCons() can now also be called in SCIP_STAGE_TRANSFORMED
- added SCIPstrcasecmp() and SCIPstrncasecmp() for case-insensitive string comparison
- added SCIPbendersSubproblemsAreInfeasible() to return if at least one subproblem has been identified as being
infeasible prior to performing any variable fixing
### New parameters
- presolving/milp/abortfacexhaustive to control the abort threshold for exhaustive presolving in PAPILO
- presolving/milp/abortfacmedium to control the abort threshold for medium presolving in PAPILO
- presolving/milp/abortfacfast to control the abort threshold for fast presolving in PAPILO
- constraints/components/maxcompweight to determine the maximum weight for a disconnected component that is solved during presolve
- constraints/components/contfactor counts the contributing factor of a single continuous variables with respect to the weight limit specified by constraints/components/maxcompweight
- constraints/indicator/usesameslackvar to decide whether the same slack variable should be used for indicators constraints with common binary variable
- propagating/symmetry/nautymaxncells and propagating/symmetry/nautymaxnnodes to set iteration limits in Nauty (only available if build with SYM=nauty or SYM=snauty)
### Changed parameters
- presolving/milp/threads is now only available if PaPILO is built with TBB
- changed default of numerics/recomputefac to 1e+6 to aim at relative epsilon precision
Build system
------------
### Cmake
- attempted to fix detection of CPLEX library on macOS and Windows systems
Testing
-------
- added parameter FILTER for tests/Makefile to run only tests with a specific pattern (ctest with -R FILTER)
Miscellaneous
-------------
- adjusted Gurobi interface for Gurobi 12
- reordered events: BESTSOLFOUND/NODE_FEASIBLE are now processed before the nodes are cut off and before NODE_DELETE events are processed
- removed `#define` of `getcwd` (in case of Windows builds) in scip/def.h
- the `#define` of `strcasecmp` and `strncasecmp` (in case of Windows builds) in scip/def.h will be removed with SCIP 10;
use `SCIPstr(n)casecmp()` (scip/pub_misc.h) instead
@section RN911 SCIP 9.1.1
*************************
Fixed bugs
----------
- fix bug in separator aggregation that caused incorrect terminations when for an integral objective the objective limit was set to a fractional value
- fix bug in memory management of doublelex matrices where indices were set beyond array bounds
- store relevance flags in consdataTightenCoefs() of cons_linear.c to avoid dropping variables unintentionally due to numerical changes
- fix possible segmentation fault when resetting local and global bounds of original variables after abnormal termination
- compare coefficient scales to detect parallelism to avoid integral relaxations in detectRedundantConstraints() of cons_linear.c
- remove coefficient information from linear constraint hashes in order to compare keys with tolerances
- fixed NULL pointer dereference in SCIPtpiGetNumThreads() of TinyCThread interface if called before SCIPtpiInit(); now returns 0 in this case
- calling SCIPsolveConcurrent() when SCIP was compiled without a TPI now results in a plugin-not-found error
- fixed LPI status functions of lpi_cpx if the barrier is called
- check cuts for redundancy after scaling in cutTightenCoefs() and cutTightenCoefsQuad() of cuts.c
- maintain definition of artificial integral variables in xor constraints to avoid invalidation of conflict constraints
- free childless nodes only after the deactivation of the old focus path in treeSwitchPath() of tree.c
- only normalize rows for column norm evaluations in shift-and-propagate heuristic to avoid unscaled violations
- expression handler for absolute value computes now also a cut when one of the bounds is infinite as long as the sign of the argument is known
- check for more data to be freed before modifying nonlinear constraints in SCIPaddExprNonlinear()
- allow for terms with zero coefficients when checking sum in SCIPexprCheckQuadratic()
- do not abort writing of constraints to lp/pip files (and forget to free buffer memory) when encountering unsupported nonlinear constraint
- fixed that strings with names and descriptions of the LPI's were not null-terminated
- fixed decision on when to enforce nonlinear constraints on relaxation solutions if integer variables are present
- fixed reading of very long lines (>78000 characters) in FlatZinc reader
- fixed write of strings with at least 1024 characters when compiling with MSVS 2015 (14.0) or later (still an issue with earlier MSVS, which will not be fixed)
- keep epsilon coefficients in applyFixings() of cons_linear.c until multiples are merged to avoid loss of relevant contributions
- fixed that some variable type changes were not accounted correctly in presolve of linear constraints
- fix constraint sorting in setpp-orbitope upgrade in symmetry code
- fixed that SCIPnodeGetConsProps() also counted bound changes from propagators
- use original and-constraints of an untransformed pseudoboolean constraint when copying original problems to avert segmentation faults
- sort and-constraints of a pseudoboolean constraint with respect to the resultant problem indices to avoid shuffled copies
- treat pseudoboolean constraints as nonlinear constraints in OPB reader to prevent duplication mistakes
Examples and applications
-------------------------
- in example Binpacking implement Farkas pricing for packings because branching can actually lead to infeasible restricted master LPs
Testing
-------
- allow unknown parameters to let tests pass if only optional dependencies are missing
Build system
------------
### Cmake
- fixed compilation and linking with HiGHS; to use HiGHS, cmake now requires to specify the directory containing the `highs-config.cmake` file via `-DHIGHS_DIR`
- extended identification of Ipopt library on Windows to also look for ipopt.dll.lib, as this is used since Ipopt 3.13.0 (2019)
@section RN910 SCIP 9.1.0
*************************
Features
--------
- added constraint handler that checks and enforces bounds on original variables which have been fixed or aggregated in the transformed problem
- allow for implicit integer variables in xor constraints
- implemented symmetry detection callbacks for pseudoboolean constraints
- added option to consider enforcement of nonlinear constraints (including spatial branching) before integrality has been enforced
Fixed bugs
----------
- make sure that, in dual proof analysis, upgraded constraints can report their number of variables
- check knapsack constraints as linear constraints to avoid violations based on implicit integrality
- make sure that symmetry detection callbacks report success
- make arithmetics in cuts.c more robust to avoid invalid scg cuts due to numerical rounding sensitivity
- allow to copy pseudoboolean constraints even if no AND constraints are present in order to avoid a warning
- set value for variable that is introduced to reformulate nonlinear objective function when reading .nl files with initial solution
- fixed that multi-aggregations from PaPILO were accepted without ensuring that their bounds hold
Examples and applications
-------------------------
- TSP: removed `gzstream.h/hpp` and parse gzipped files differently
Interface changes
-----------------
### New callbacks
- SCIP_DECL_NLHDLRENFO takes additional parameter branchcandonly to indicate whether only branching candidates should be registered,
without looking for cuts or boundchanges
### New API functions
- new function SCIPgetExprActivityNonlinear() to get activity of nonlinear constraint
- new function SCIPincludeConshdlrFixedvar() to include new constraint handler that checks bounds on fixed original variables
### New parameters
- limits/primal to terminate the solve as soon as the primal bound is at least as good as this value, same as limits/objectivestop (deprecated)
- limits/dual to terminate the solve as soon as the dual bound is at least as good as this value
- presolving/milp/internalmaxrounds to control the maximal rounds for each call of the milp presolver (PaPILO)
- constraints/fixedvar/* to control the new constraint handler that checks bounds on fixed original variables
- constraints/nonlinear/branching/mixfractional to specify minimal average pseudo cost count for discrete variables
at which to start considering spatial branching before branching on fractional integer variables
(default infinity means that integrality is always enforced before nonlinear constraints)
- constraints/nonlinear/branching/fracweight to specify weight of fractionality of integer variables in spatial branching
### New data structures
- enum SCIP_Status has been extended by SCIP_STATUS_PRIMALLIMIT and SCIP_STATUS_DUALLIMIT to indicate termination at limits/primal and limits/dual respectively
Build system
------------
- new option SYM=dejavu to choose Dejavu for computing symmetries
- changed the default symmetry computation package from sassy+bliss to sassy+nauty
- bliss source is no longer included in the source tree, but can be linked as external library (https://github.com/ds4dm/Bliss)
- cmake now automatically downloads and installs the latest release version of SoPlex from GitHub if it is not found directly
Miscellaneous
-------------
- updated nauty to version 2.8.8
@section RN901 SCIP 9.0.1
*************************
Fixed bugs
----------
- fixed bug in detection of double lex matrices due to wrong memory allocation
- fixed bug where parameter `limits/objectivestop` was copied to subscips in plugins which have different objectives
- in count mode respect empty solution when problem is solved in presolving
- fixed that SCIP may have tried to pass a negative random seed to an LP solver
- fixed bug where conflict analysis in strong branching tried to analyze an unsuccessful LP solve
- enable parameter limits/restarts by allowing to reach the restart limit in restartAllowed()
- handle normalizing linear constraints in presolving with more caution to avoid numerical difficulties for integer variables with large coefficients
- use quad precision to calculate residual activity bounds to reduce numerical errors for large variable bounds in cons_linear.c
- in SCIPsolveProbingLP() when objective has been changed do not return cutoff due to exceeding the cutoff bound
- set probing LP to be a relaxation only when objective has not been changed
- declare contradicting infinities in getMinActivity() and getMaxActivity() as non-tight
- reject farkas solution with large values to bound magnification of errors in SCIPgetFarkasProof()
- if all variables are fixed, apply relative feasibility tolerance to avoid invalid infeasibility in applyFixings() of cons_linear.c
- delete empty redundant knapsack and linear constraints after cleanup in SCIPmatrixCreate()
- cleanup first constraints in SCIPcleanupConssVarbound(), SCIPcleanupConssSetppc(), and SCIPcleanupConssLogicor()
- symmetry handling methods have not been added immediately after computing symmetries, which has been fixed
- delay checking node limits after presolving to correctly continue up to the exceeding main node
- simplified the objective sense assumption for the subproblems in the Lagromory separator
- update effective root depth iteratively to avoid trapping it at a single child node
- fixed that dualsparsify presolver did not always check do-not-multiaggregate variable flag
- fixed bug in computing elements of orbits in orbital reduction
Miscellaneous
-------------
- redefine isrelax to istight in cons_linear.c
Build system
------------
### Cmake
- A file cmake.log containing the changed options is written to the cmake build directory.
- removed replacement of the settings of RelWithDebInfo
- add compile option -ffp-contract=off or /fp:precise to enhance reproducibility across different systems
### Makefile
- add flags -ffp-contract=off and /fp:precise to enhance reproducibility across different systems
Interface changes
-----------------
### New parameters
- added parameter "propagating/symmetry/symtiming" to determine when symmetries are computed and handled
### Changed parameters
- Disabled "propagating/symmetry/addconsstiming" since it is not used anymore.
- Disabled "propagating/symmetry/ofsymcomptiming" since it is not used anymore.
@section RN900 SCIP 9.0.0
*************************
Features
--------
- added simplification of abs(x)^n to x^n when n is even (simplify rule POW12)
- in expression simplification, added possibility to expand power of sum with exponents larger than 2 (simplify rule POW7)
- in expression simplification, added possibility to expand products with sums as factor when there are more than two factors (simplify rule SP12b)
- in expression simplification, added possibility to allow expanding power of products with fractional exponent (simplify rule POW5a)
- can now build with Lapack (used for solving nonlinear problems) explicitly; if IPOPT is used, then Lapack is accessed through it;
an interface to Lapack is available in lapack_calls.h
- added support for logical constraints in binary variables and basic logical operators (and, or, not, equal) to AMPL .nl reader
- indicator constraints now use the same slack variable for the linear constraints if binary variables are used multiple times
for indicator constraints
- new diving heuristic indicatordiving that focuses on indicator variables which control semicontinuous variables
- updated statistics on NLP relaxation; information on convexity of NLP has been added
- added new bandit method (EXP.3-IX) that is the new default of the ALNS heuristic
- added dialog to display recognized permutation symmetries ("display symmetry")
- The symmetry detection code has been completely restructured. Instead of completely encoding symmetry information in
prop_symmetry.c, there is a new callback for constraint handlers, which returns symmetry relevant information by
encoding a constraint as a node and edge colored graph. This way, also custom constraint handlers can provide
symmetry information.
- added special presolving step for logicor and set covering/packing for constraints with two variables and one independent variable
- increased the depth field of the tree structure from 16 to 30 bits and the max depth of the search tree from 65534 to 1073741822
- added new cut selector plugin called cutsel_ensemble. Performs a superset of hybrid cutsel. Implements new filtering methods and scoring options.
- added new branching rule based on Gomory mixed-integer cuts
- added new branching score to the reliability pseudo-cost branching rule
- added new cut selector plugin called cutsel_dynamic. Performs a superset of hybrid cutsel. Implements new filtering methods and scoring options.
- added monoidal strengthening to intersection cut generation of nlhdlr_quadratic
- extended heuristic dps to run after processing the node and to use strict limits for the reoptimization step
- extended obbt propagator to handle variables of the linear constraints corresponding to indicator constraints
- added new heuristic heur_scheduler that models the selection of LNS and diving heuristics as a multi-armed bandit problem
- added nonlinear handler for signomial expressions: adds cuts based on a difference of convex functions representation
- Delayed separators are now called if no other cuts have been found. Previously, such separators were only called near stalling or when the separation rounds limit was reached.
- added a new separator sepa_lagromory to generate Lagromory cuts in a relax-and-cut framework, i.e., GMI cuts generated
at different bases that are explored in the process of solving the Lagrangian dual problem at a node. This separator
is OFF by default.
- when parsing nonlinear constraints from CIP files, the * after the number in a term is now optional if followed by a variable,
i.e., instead of 3*<x>*<y>, now also 3<x>*<y> can be read, but 3<x><y> is not supported;
this allows to read some CIP files that were written with SCIP < 8
- when running bliss, we now limit the number of actually created generators and not the ones considered by bliss
Performance improvements
------------------------
- Variable conflict-based addition of Schreier-Sims cuts for symmetry handling in prop_symmetry.c does no longer use
an expensive explicit conflict graph construction.
- Only run propagation of indicator constraints if relevant variables have changed.
- Propagation of indicator constraints propagates maximal activity of linear constraint to upper bound of slack variable.
- Added initialization of LP relaxation for SOC constraints.
- Avoided some numerical issues when separating SOC constraints.
- If differentation of convex expression fails in convex nlhdlr, then a perturbed point is tried.
- Use sassy/bliss as default symmetry computation package.
- No longer linearize indicator constraints in undercover heuristic by default.
- Deactivate pre-root heuristic zeroobj in undercover heuristic.
- Added new branching score tiebreaker for reliability pseudo-cost branching rule
- Try nearest bound if zero solution value is out of bounds in heuristic trivial.
Interface changes
-----------------
### New and changed callbacks
- Added solution linearization callback for nonlinear handlers.
The nonlinear handler may use this callback to add tight cuts that use the given solution as reference point to the cutpool.
The callback is called if option constraints/nonlinear/linearizeheursol is enabled.
- The callback for copying problem data SCIP_DECL_PROBCOPY() now has a parameter "original" indicating whether the original
or transformed problem should be copied. Similarly, SCIPprobCopy() in prob.h/c has such a parameter.
- Added CONSGETPERMSYMGRAPH and CONSGETSIGNEDPERMSYMGRAPH callback for constraint handlers, which provides symmetry information about constraints to SCIP.
### Deleted and changed API methods
- SCIPtpiInitLock(), SCIPtpiDestroyLock(), SCIPtpiInitCondition(), SCIPtpiDestroyCondition() now take a double
pointer to SCIP_LOCK/SCIP_CONDITION, respectively.
- Renamed SCIPtpiSumbitJob() to SCIPtpiSubmitJob().
- SCIPcreateConsIndicatorLinCons(), SCIPcreateConsIndicatorGenericLinCons() do not allow binvar to be NULL anymore
- Replaced SCIPnlrowSetCurvature() by SCIPsetNlRowCurvature().
- SCIPsnprintf() now returns the required string length in case reallocation is necessary.
- SCIPcomputeCoverUndercover() receives three more arguments which nonlinearities to cover
- removed definition of SQRT
- SCIPincludeObjConshdlr(), SCIPincludeConshdlr(), SCIPconshdlrCreate() receive two more arguments for the
conshdlr callbacks CONSGETPERMSYMGRAPH and CONSGETSIGNEDPERMSYMGRAPH
- removed SYM_VARTYPE, SYM_OPTYPE, SYM_CONSTTYPE, SYM_RHSTYPE, SYM_MATRIXDATA
- new parameter issigned for SCIPcomputeOrbitsSym()
- new parameter symtype for SCIPcomputeComponentsSym()
- new parameter symtype and permvardomaincenter for SCIPlexicographicReductionAddPermutation()
- replaced parameters matrixdata and exprdata of SYMcomputeSymmetryGenerators() by graph
### New API functions
- new functions for interfacing with Lapack: SCIPlapackIsAvailable(), SCIPlapackIsAvailable(), SCIPlapackComputeEigenvalues(), and SCIPlapackSolveLinearEquations
These functions should be used instead of SCIPisIpoptAvailableIpopt(), SCIPcallLapackDsyevIpopt(), and
SCIPsolveLinearEquationsIpopt() in the context of computing eigenvalues or solving linear equations.
If IPOPT is available, the calls will be passed on to Ipopt's interface to Lapack.
- SCIPmultiplyBySumExprSum(), SCIPpowerExprSum()
- SCIPsetParam()
- SCIPgetPrimalDualIntegral() returns the primal dual integral stored in the statistics
- new functions SCIPcreateConsIndicatorLinConsPure() and SCIPcreateConsIndicatorGenericLinConsPure() that
create indicator constraints from a linear constraint without a slack variable
- SCIPgetNLPNlRowsStat() to retrieve counts on linear, convex, and nonconvex rows in NLP
- SCIPnlhdlrSetSollinearize(), SCIPnlhdlrHasSollinearize()
- SCIPbendersGetNLPParam()
- new API functions SCIPlexicographicReductionGetStatistics(), SCIPlexicographicReductionPrintStatistics(),
SCIPlexicographicReductionPropagate(), SCIPlexicographicReductionAddPermutation(), SCIPlexicographicReductionReset(),
SCIPlexicographicReductionFree(), SCIPincludeLexicographicReduction(), for lexicographic reduction.
- new API functions SCIPorbitopalReductionGetStatistics(), SCIPorbitopalReductionPrintStatistics(),
SCIPorbitopalReductionPropagate(), SCIPorbitopalReductionAddOrbitope(), SCIPorbitopalReductionReset(),
SCIPorbitopalReductionFree(), SCIPincludeOrbitopalReduction(), SCIPorbitopalReductionGetDefaultColumnOrdering(),
for orbitopal fixing.
- new API functions SCIPorbitalReductionGetStatistics(), SCIPorbitalReductionPrintStatistics(),
SCIPorbitalReductionPropagate(), SCIPorbitalReductionAddComponent(), SCIPorbitalReductionReset(),
SCIPorbitalReductionFree(), SCIPincludeOrbitalReduction(), for orbital fixing.
- new API functions SCIPgetShadowTreeEventHandlerExecutionTime(), SCIPshadowTreeGetShadowNodeFromNodeNumber(),
SCIPshadowTreeGetShadowNode(), SCIPgetShadowTree(), SCIPactivateShadowTree(), SCIPincludeEventHdlrShadowTree(),
for managing a copy of the branch-and-bound tree for symmetry handling purposes.
- SCIPdotWriteOpening(), SCIPdotWriteNode(), SCIPdotWriteArc(), SCIPdotWriteClosing()
- SCIPincludeCutselEnsemble(), SCIPselectCutsEnsemble() to include cutsel_ensemble or use the selection algorithm
- SCIPincludeBranchruleGomory() includes new gomory cut based branching rule
- SCIPgetVarAvgGMIScore(), SCIPincVarGMISumScore(), SCIPgetVarLastGMIScore(), SCIPsetVarLastGMIScore() set historical values used by SCIP's default branching rule
- SCIPincludeNlhdlrSignomial() includes the signomial nonlinear handler
- SCIPgetExprMonomialData() returns a monomial representation of a product expression
- SCIPestimateRoot() computes estimators for roots with exponent in [0,1]
- SCIPincludeCutselDynamic(), SCIPselectCutsDynamic() to include cutsel_dynamic or use the selection algorithm
- SCIPincludeSepaLagromory() to include the new Lagromory separator
- SCIPconsCompCheck() to compare two constraints based on their check priority
- SCIPgetConsPermsymGraph() and SCIPgetConsSignedPermsymGraph() to access the (signed) permutation symmetry detection graph of a constraint
- SCIPsetConshdlrGetPermsymGraph() and SCIPsetConshdlrGetSignedPermsymGraph() to set the (signed) permutation symmetry detection graph of a constraint
- SCIPconshdlrSupportsPermsymDetection() and SCIPconshdlrSupportsSignedPermsymDetection() to access whether a conshdlr supports detection of (signed) permutation symmetries
- new API functions for creating and manipulating a symmetry detection graph: SCIPcreateSymgraph(), SCIPfreeSymgraph(), SCIPcopySymgraph(), SCIPextendPermsymDetectionGraphLinear(),
SCIPaddSymgraphVarAggregation(), SCIPaddSymgraphOpnode(), SCIPaddSymgraphValnode(), SCIPaddSymgraphConsnode(), SCIPgetSymgraphVarnodeidx(), SCIPgetSymgraphNegatedVarnodeidx(),
SCIPupdateSymgraphLhs(), SCIPupdateSymgraphRhs(), SCIPfixSymgraphVarnode(), SCIPaddSymgraphEdge(), SCIPcomputeSymgraphColors(), SCIPgetSymgraphSymtype(), SCIPgetSymgraphVars(),
SCIPgetSymgraphNVars(), SCIPgetSymgraphNConsnodes(), SCIPgetSymgraphNNodes(), SCIPgetSymgraphNEdges(), SCIPgetSymgraphEdgeFirst(), SCIPgetSymgraphEdgeSecond(),
SCIPgetSymgraphVarnodeColor(), SCIPgetSymgraphNodeType(), SCIPgetSymgraphNodeColor(), SCIPisSymgraphEdgeColored(), SCIPgetSymgraphEdgeColor(), SCIPgetSymgraphNVarcolors(),
SCIPhasGraphUniqueEdgetype(), SCIPallocateSymgraphConsnodeperm(), SCIPcreateSymgraphConsnodeperm(), SCIPgetSymgraphConsnodeperm(), SCIPfreeSymgraphConsnodeperm(),
SCIPgetSymActiveVariables(), SCIPfreeSymDataExpr(), SCIPgetSymExprdataNConstants(), SCIPgetSymExprdataConstants(), SCIPgetCoefSymData(),
SCIPcreateSymOpNodeType(), SCIPgetSymOpNodeType()
- SCIPexprhdlrSetGetSymdata(), SCIPexprhdlrHasGetSymData(), SCIPgetSymDataExpr(), SCIPcallExprGetSymData() to access symmetry data of expressions
- SYMcheckGraphsAreIdentical() to check whether two symmetry detection graphs are identical
- new functions SYMbuildSassyGraph(), SYMbuildSassyGraphCheck()
- new type SYM_GRAPH
- new definitions SCIP_DECL_CONSGETPERMSYMGRAPH, SCIP_DECL_EXPRGETSYMDATA
- new member SYM_NODETYPE_CONS in SYM_NODETYPE enum
- new members SYM_CONSOPTYPE_SUM, SYM_CONSOPTYPE_SLACK, SYM_CONSOPTYPE_COEF, SYM_CONSOPTYPE_RHS, SYM_CONSOPTYPE_LAST in SYM_CONSOPTYPE enum
- new defintion SCIP_DECL_EXPRGETSYMDATA
- new function SCIPdetectSingleOrDoubleLexMatrices()
### Command line interface
- Added optional parameter -i when calling SCIP in AMPL-mode (-AMPL parameter).
If -i is specified, a SCIP shell is started where normally SCIPsolve() would be called.
### Interfaces to external software
- added interface to nauty/traces for symmetry computation
- added interface to sassy, a preprocessor for symmetry computation
- The directory src/sassy contains the source code of sassy.
- Added interface to Lapack (used for solving nonlinear problems).
- The AMPL interface now supports parameters specified in AMPL command scripts via option scip_options.
The value of scip_options is expected to be a sequence of parameter names and values, separated by a space, e.g.,
`option scip_options 'limits/time 10 display/verblevel 1';`.
String values should not be quoted and spaces in string values are not supported.
- sassy can be used now as preprocessor for nauty/traces
- The solution status codes written to AMPL solution files now match those from https://mp.ampl.com/details.html#_CPPv4N2mp3sol6StatusE.
### Changed parameters
- change default value of parameter separating/filtercutpoolrel to FALSE
- Shrunk range of parameter "propagating/symmetry/sstleaderrule" from [0,3] to [0,2], removed "MAXCONFLICTS"-option.
- Removed reading/gmsreader/freeints. A default upper bound of +inf is now assumed for integer variables in GAMS (which is the case since GAMS 23.1).
- Disabled "propagating/symmetry/symfixnonbinaryvars" since it is not used in the new symmetry code.
- Replaced "propagating/symmetry/onlybinarysymmetry" with "propagating/symmetry/enforcecomputesymmetry" and set to FALSE by default.
- Disabled "propagating/symmetry/performpresolving" since running orbital reduction during presolving is not effective.
- Repurposed "propagating/symmetry/usedynamicprop" since it now also applies to lexicographic reduction.
- Changed default value of parameter "propagating/symmetry/addsymresacks" from FALSE to TRUE.
### New parameters
- separating/maxcutsgenfactor and separating/maxcutsrootgenfactor as factors (w.r.t. separating/maxcuts and
separating/maxcutsroot) for limits on the number of cuts generated (which used to be constants '2')
- expr/pow/expandmaxexponent to specify limit on exponent when to expand power of sum
- expr/pow/distribfracexponent to enable expanding power of products with fractional exponents
- expr/product/expandalways to enable expanding any product with sums as factor (that is, also when more than two factors)
- nlhdlr/convex/maxperturb to specify maximal perturbation of non-differential reference points
- benders/default/nlpiterlimit to adjust iteration limit for NLP solver for Benders' decomposition NLP subproblems
- limits/objectivestop to interrupt the solve as soon as a primal solution is found
that is at least as good as the given value
- heuristics/undercover/{coverand,coverind,covernl} to control which nonlinearities to consider (by default only "and" and nonlinear constraints)
- cutselection/ensemble/* all parameters for new ensemble cut selector
- cutselection/dynamic/* all parameters for new dynamic cut selector
- branching/relpscost/gmiavgeffweight specifies the weight in the relpscost branching score of the normalized efficacy of all generated GMI cuts (for a variable)
branching/relpscost/gmilasteffweight specifies the weight in the elpscost branching score of the normalized efficacy of the last generated GMI cut (for a variable)
- nlhdlr/quadratic/usemonoidal to enable monoidal strengthening when separating quadratics with intersection cuts
- nlhdlr/quadratic/trackmore to collect more statistics for monoidal strengthening when separating quadratics with intersection cuts
- nlhdlr/quadratic/useminrep to use the minimal representation to compute cut coefficients when separating quadratics with intersection cuts
- nlhdlr/quadratic/sparsifycuts to enable sparsification of intersection cuts for quadratics
- heuristics/dps/reoptlimits to set strict limits for the reoptimization step in dps
- heuristics/dps/timing to run dps after processing the node
- heuristics/scheduler/* all parameters for new scheduler heuristic
- nlhdlr/signomial/enabled, nlhdlr/signomial/maxnundervars, nlhdlr/signomial/mincutscale: parameters for the signomial nonlinear handler
- separating/lagromory/freq to denote the frequency for calling Lagromory separator
- separating/lagromory/away to denote the minimal integrality violation of a basis variable to try separation
- separating/lagromory/dynamiccuts to denote whether the generated cuts be removed from LP if they are no longer tight
- separating/lagromory/maxroundsroot to denote the maximal number of separation rounds in the root node
- separating/lagromory/maxrounds to denote the maximal number of separation rounds in a non-root node
- separating/lagromory/nmaxcutsperlproot to denote, in the root node, the maximal number of Lagromory cuts that can be
separated per explored basis of the Lagrangian dual
- separating/lagromory/nmaxcutsperlp to denote, in a non-root node, the maximal number of Lagromory cuts that can be
separated per explored basis of the Lagrangian dual
- separating/lagromory/perroundnmaxlpiters to denote the maximal number of separating LP iterations that are allowed per
separation round
- separating/lagromory/dualdegeneracyratethreshold to denote the minimum dual degeneracy rate for the separator execution
- separating/lagromory/varconsratiothreshold to denote the minimum variable-constraint ratio on the optimal face for the
separator execution
- many other advanced parameters for the Lagromory separator, which are also mentioned under separating/lagromory/*
### Data structures
- new data structure SYM_GRAPH to encode symmetry information from a constraint
- new data structure SYM_EXPRDATA to encode symmetry information from expressions
- replaced enum SYM_SYMTYPE by a complete new one; removed SYM_RHSSENSE, added SYM_NODETYPE and SYM_CONSOPTYPE
Deleted files
-------------
- deleted the now unused files: tpi_none.h, tpi_openmp.h, tpi_tnycthrd.h, type_tpi_none.h, type_tpi_openmp.h, type_tpi_tnycthrd.h
Unit tests
----------
- new unittests for nlhdlr_quadratic that test monoidal strengthening and the use of the minimal representation to compute cut coefficients
- unittests for nlhdlr_signomial
Testing
-------
- changed `set lim obj` to `set lim objective` in ctest since `obj` is no longer unambiguous
Build system
------------
### Cmake
- New flag -DLAPACK=on for linking with Lapack (must be available in the system)
- added flag option "SYM=sbliss" for using sassy/bliss as a graph automorphism package
- use SYM=sbliss by default, since sassy and bliss are now shipped with SCIP.
- added flag option "SYM=snauty" for using sassy/nauty as a graph automorphism package
### Makefile
- added flag option "nauty" for SYM variable to specify which graph automorphism package should be used
- added flag option "sbliss" (sassy/bliss) for SYM variable to specify which graph automorphism package should be used
- added flag option "snauty" (sassy/nauty) for SYM variable to specify which graph automorphism package should be used
- use SYM=sbliss by default, since sassy and bliss are now shipped with SCIP
- New flag LAPACK for linking with Lapack (must be available in the system)
- A file scip/config.h is created in the build directory ($(OBJDIR)/include) now.
Defining NO_CONFIG_HEADER is no longer necessary and has no effect anymore.
Fixed bugs
----------
- Number of runs in which separation is enabled will now be correct as per "separating/maxruns" parameter. Earlier,
separation was enabled for "maxruns + 1" number of runs, i.e., separation was enabled even when "maxruns = 0" was set.
- add safeguard for number of selected cuts
- use double double precision for delta in activity updates of cons_linear.c
- sort constraints in checkSolOrig() to keep the logic of constraint handlers intact
- fixed make install when SHARED=no and make uninstall
- check absolute coefficients relative to extremal average to avoid invalid unifications in normalizeCons()
- enforce and check symmetry-based constraints to take their locks (in dual reductions) into account
- flush changes at the end of SCIPlpiSetBase() in lpi_grb.c to apply the newly set basis correctly
Miscellaneous
-------------
- The TPI has been changed to become mostly independent from the actual parallel interface during compile time.
For this, the locks and conditions are now pointers to abstract structs.
- fixed that scip/def.h, the header for C preprocessor definition (`#define`'s), included headers for some SCIP type and function definitions
(scip/type_retcode.h, scip/type_message.h, scip/pub_message.h)
@page RN8 Release notes for SCIP 8
@section RN810 SCIP 8.1.0
*************************
Fixed bugs
----------
- fixed that scaling of rows in Gurobi interface (SCIPlpiScaleRow()) changed infinite sides to large finite ones (1e20) when scale factor is negative
- check whether objective limit is truly reached in SCIPlpiIsStable()
- if an objective limit is set and Mosek claims that it is exceeded, check that this is indeed the case in SCIPlpiIsStable()
- the .mps file reader was extended to additionally accept .mps files with the objective sense section on one line
- ensure that delayed cutpool separation does not happen if enough cuts have been found already
- fixed that a Gurobi or Mosek interface (LPI) could not be freed from a thread different than the one it was created in, which lead to problems when, e.g., using the concurrent optimizer
- in cons_varbound if both variables are fixed, instead of propagating the constraint check the feasibility of the constraint since propagating can lead to unnecessary numerical troubles
- fixed memory leak in branching rule "distribution"
- fixed that undercover did not enforce that sufficiently many variables in an and-constraints were fixed to have it linearized in the generated sub-scip
- fixed two bugs in cons_varbound: avoid adding variable bounds if vbdcoef is infinite and unlock/lock variables if lhs/rhs/vbdcoef are changed
- globalize constraint changes before bound changes during the effective root shift in treeSwitchPath() to correctly update variable locks by avoiding global bounds with outstanding bound change events when deleting constraints
- fixed error when attempting to copy SCIP with activated pricers
- remove integrality check for implicit integral variables in cons_integral.c, updated the definition for variable type implicit integer to be more explicit that these variables can take fractional values, and updated FAQ entry
- updated and, or, and pseudoboolean constraint handlers to better handle fractional implicit integer variables in enforcement
- avoid invalid strong Chvatal-Gomory cuts by ceiling with tolerance in the calculation of parameter k and flooring slack coefficients with standard epsilon tolerance as well as quad precision
- add missing row links to columns in SCIPflushRowExtensions() required to maintain correct row norms
- restrict separator intobj to solutions for which there can be no better feasible integral objective values to avoid cutting them off
- delay removal of clique lists from SCIPvarRemoveCliquesImplicsVbs() into cliqueCleanup() to avoid segmentation faults by incomplete cleanups after variable conversions
- reject sub-solutions with invalid objectives in SCIPtranslateSubSols() due to contradicting infinite contributions
- correct column index in getMinMaxActivityResiduals() to make presolver dualinfer work
- copy quiet flag from main scip's message handler to the one of solverscip in concurrent optimization
- avoid bound tightening cycles towards huge redundancy bounds in fullDualPresolve() to avert fatal numerical trouble in representing vertices of linear relaxations with unbounded domains
- fix problem where debug solution did not work if branching constraints are present
- update index of dominating variable on coefficient deletion in dualPresolving() of constraint handler logicor
- pass on flags from a redundant to the implying varbound constraint in preprocessConstraintPairs() to avoid suboptimal fixings by model relaxations
- apply reductions of dualinfer only if a dual solution exists (primal is bounded)
- before presolving is finished check solutions before retransforming them including tiny values to keep check flags consistent
- disable heuristics before and during presolving in benders decomposition to avoid messing up the objective structure in the solution store by dropping auxiliary variables in the required retransformations
- correct local flag of singleton conflict constraints in tightenSingleVar() against invalid bound globalization
- respect unboundedness in the computation of activity bounds in conflict.c to avoid invalid huge bounds due to small coefficients on unbounded variables
- ensure positive sides of a linear constraint when recognizing a set partition in rangedRowSimplify() to account for redundancy issues
- relax numerical conditions for variable aggregations to avert invalid variable fixings
- fixed harmless read of uninitialized data when creating parameters
- fix call of SCIPnlpiOraclePrintProblem in nlpi_worhp
Performance improvements
------------------------
- Use sassy/bliss as default symmetry computation package.
Interface changes
-----------------
### Interfaces to external software
- added interface to nauty/traces for symmetry computation
- added interface to sassy, a preprocessor for symmetry computation
- The directory src/sassy contains the source code of sassy.
Build system
------------
### Cmake