-
Notifications
You must be signed in to change notification settings - Fork 4
/
Copy pathCHANGELOG
1146 lines (934 loc) · 56.7 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 RN40 Release notes for GCG 4.0
@section RN400 GCG 4.0.0
*************************
New features:
-------------
- introduced a new GCG struct that is used as main object when interacting with GCG, similar to the SCIP struct
- Solver plugin for HiGHS. Allows user to select HiGHS as a # problem solver.
- new # solver ('gcg') that calls GCG to solve (structured) # problems
- new (JSON formatted) decomposition file format ('jdec') supporting nested/recursive decompositions
- generic approach to handle cuts and branching constraints in the master problem with no couterpart in the original problem
- created a # variable type for variables not corresponding to any original variable, inferred by extended master constraints
- automatic mastervariable synchronization across the entire search tree through history-tracking
- component bound branching rule
- New # callback plugin type. This plugin type provides two callback methods for interacting with the GCG pricer.
The pre-# and post-# callback methods is called immediately before and after, respectively, new variables
are generated in the REDCOST and FARKAS # methods.
- New heuristic Integer programming column generation (IPColGen). The heuristic is a destroy-and-repair large
neighbourhood search heuristic. Given a partial solution, the repair procedure generates new columns using a modified
# problem objective.
New/modified/removed structures, defines, and classes:
---------------------------
- added struct 'GCG'
- removed struct 'PARTIALDECOMP_WRAPPER'
- added struct 'PARTIALDECOMP_C' used by the C interface
- added struct 'GCG_INFERRED#VARDATA'
- added struct 'GCG_#MODIFICATION'
- added enum 'GCG_EXTENDEDMASTERCONSTYPE'
- added struct 'GCG_EXTENDEDMASTERCONS'
- added struct 'GCG_EXTENDEDMASTERCONSDATA'
- added struct 'GCG_VARHISTORY'
- added struct 'GCG_VARHISTORYBUFFER'
- added type 'GCG_VARTYPE_INFERRED#'
- added a 'MASTER' prefix to the master diving type declarations
New/modified/removed API functions:
---------------------------
- public GCG functions use the new GCG data structure
- added functions 'GCGcreate', 'GCGfree', 'GCGgetOrigprob', 'GCGgetMasterprob', 'GCGgetBendersMasterprob', 'GCGgetDwMasterprob', 'GCGmasterGetGcg', 'GCGorigGetGcg'
- removed 'GCGgetPartialdecToWrite'
- 'GCGconshdlrDecompAddBasicPartialdec' returns now SCIP_RETCODE and sets a pointer to the created decomposition
- public C functions working with (partial) decompositions use now 'PARTIALDECOMP_C' pointers instead of the id of the decomposition
- added function 'GCGconshdlrDecompPartialdecAggregationInformationCalculated'
- added function 'GCGconshdlrDecompPartialdecCalcAggregationInformation'
- added function 'GCGconshdlrDecompPartialdecGetNEquivalenceClasses'
- added function 'GCGconshdlrDecompPartialdecGetReprBlockForEqClass'
- added function 'GCGconshdlrDecompPartialdecGetBlocksForEqClass'
- added function 'GCGconshdlrDecompPartialdecGetNBlocksForEqClass'
- added function 'GCGconshdlrDecompPartialdecGetRepVarMap'
- added function 'GCGconshdlrDecompPartialdecGetOrigVarForBlock'
- added function 'GCGconshdlrDecompPartialdecGetNVarsForBlock'
- added function 'PARTIALDECOMP::getReprBlockForEqClass'
- added function 'PARTIALDECOMP::getScore' without arguments
- added function 'PARTIALDECOMP::isAssignedToPresolvedProb'
- added function 'PARTIALDECOMP::buildDecChainString' returning a std::string object
- renamed functions 'PARTIALDECOMP::get*Vec' to 'PARTIALDECOMP::get*' and removed old ones with the same name that returned a reference to the 'data()' object of the vector
- renamed function 'PARTIALDECOMP::getBlocksForRep' to 'PARTIALDECOMP::getBlocksForEqClass'
- renamed function 'PARTIALDECOMP::getNReps' to 'PARTIALDECOMP::getNEquivalenceClasses'
- renamed function 'PARTIALDECOMP::getRepForBlock' to 'PARTIALDECOMP::getEqClassForBlock'
- added function 'GCGgetColpool'
- added function 'GCGcolpoolPropagateGlobalBounds'
- modified function 'GCGtransformMastersolToOrigsol'
- added 'GCGpricerAddColResult', 'GCGpricerGetMaxNThreads', 'GCGpricestoreGetNColsTotal'
- changed 'GCGpricestoreCreate', 'GCGpricestoreAddCol', 'GCGpricestoreGetCols', 'GCGpricestoreGetNCols'
- removed 'GCGpricestoreRemoveInefficaciousCols', 'GCGpricestoreGetTime'
- changed 'GCGcolpoolAddCol', 'GCGcolpoolPrice'
- added 'GCGhashGetKeyCol', 'GCGhashKeyEqCol', 'GCGhashKeyValCol'
- added function 'GCGcreateInferred#Var'
- added function 'GCGvarIsInferred#'
- added function 'GCG#modificationCreate'
- added function 'GCGextendedmasterconsCreateFromCons'
- added function 'GCGextendedmasterconsCreateFromRow'
- added function 'GCGextendedmasterconsFree'
- added function 'GCGrelaxBranchNewCol'
- added function 'GCGrelaxBranchGetExtendedMasterCons'
- added function 'GCGrelaxBranchGetAllActiveExtendedMasterConss'
- added callback 'GCG_DECL_BRANCHNEWCOL' to 'GCG_BRANCHRULE'
- added callback 'GCG_DECL_BRANCHGETEXTENDEDMASTERCONS' to 'GCG_BRANCHRULE'
- added parameter 'GCG_DECL_BRANCHNEWCOL ((*branchnewcol));' to 'GCGrelaxIncludeBranchrule'
- added parameter 'GCG_DECL_BRANCHGETEXTENDEDMASTERCONS((*branchgetextendedmastercons))' to 'GCGrelaxIncludeBranchrule'
- moved function 'SCIPincludeSepaMaster' to 'SCIPincludeSepaOriginal'
- moved function 'GCGsepaGetOrigcuts' to 'GCGsepaGetOriginalSepaOrigcuts'
- moved function 'GCGsepaGetNCuts' to 'GCGsepaGetNOriginalSepaCuts'
- moved function 'GCGsepaGetMastercuts' to 'GCGsepaGetOriginalSepaMastercuts'
- moved function 'GCGsepaAddMastercuts' to 'GCGsepaAddOriginalSepaCuts'
- moved function 'GCGsepaOrigcutExists' to 'GCGsepaOriginalSepaOrigcutExists'
Command line interface
-----------------------
- Renamed output log column 'mcuts' to 'ocuts'
Code cleanup:
-------------
- the explore dialog accesses (partial) decompositions now directly using pointers instead of their ids
- symmetry information stored for a decomposition is now used by the relaxator without creating intermediate varmaps
- moved file 'sepa_master.c' to 'sepa_original.c'
- moved file 'sepa_master.h' to 'sepa_original.h'
- moved references of 'sepa_master' to 'sepa_original'
New/changed parameters:
-----------------------
- renamed parameter '#/masterpricer/threads' to '#/masterpricer/nthreads' (default value: 1)
- moved parameter 'sepa/master/enable' to 'sepa/original/enable'
- moved parameter 'sepa/master/paramsetting' to 'sepa/original/paramsetting'
- mdded parameter 'branching/compbnd/useMDMH'
- added parameter 'branching/compbnd/useMRMH'
- added parameter '#solver/cliquer/skipchecksnodelimit'
- added parameter '#solver/cliquer/maxcliqueconsperc'
- added parameter '#solver/cliquer/maxnodes'
- added parameter '#solver/cliquer/objcoefdistr'
- added parameter '#solver/cliquer/usemultiplicity'
- added parameter '#solver/cliquer/lincutoff/enable'
- added parameter '#solver/cliquer/lincutoff/slope'
- added parameter '#solver/cliquer/lincutoff/intercept'
- changed and renamed parameter '#solver/cliquer/density' to '#solver/cliquer/maxdensity': now used as upper bound
Bug fixes
---------
- Cliquer # problem solver: fixed handling of fixed variables, fixed check of linked variables, fixed # problem compatibility check
Miscellaneous
-------------
- enable OpenMP by default
- increased minimal cmake version to 3.11
- GCG is now licensed under the Apache 2.0 License, see http://www.apache.org/licenses/LICENSE-2.0
@page RN37 Release notes for GCG 3.7
@section RN372 GCG 3.7.2
*************************
Bug fixes
---------
- store pending global bound changes only once (for the same variable) and update older ones
- prohibits subproblem merging during CONSCHECK calls in Benders' decomposition
- fix bug in symmetry detection that could lead to wrong results
@section RN371 GCG 3.7.1
*************************
Bug fixes
---------
- fix segfaults caused by graph partitioning detectors
- remove unused parameters 'detection/detectors/h*gpartition/minblocks' and 'detection/detectors/h*gpartition/maxblocks'
- fix assignSmallestComponentsButOneConssAdjacency()
- fix clock issue and segfault caused by dec_mst
- fix segfault caused by dec_stairheur
- fix parameters 'detection/detectors/stairheur/minblocks' and 'detection/detectors/stairheur/maxblocks'
- fix postprocessing of staircase decompositions (dec_postprocess)
@section RN370 GCG 3.7.0
*************************
New features:
-------------
- nauty support (symmetry detection)
New/modified/removed API functions:
---------------------------
- add 'GCGgetNautyName'
New/changed parameters:
-----------------------
- renamed parameter 'relaxing/gcg/aggregation' to 'relaxing/gcg/aggregation/enabled'
- renamed and moved parameter 'relaxing/gcg/bliss/enabled' to 'relaxing/gcg/aggregation/usesymmetrylib'
- moved parameter 'relaxing/gcg/bliss/searchnodelimit' to 'relaxing/gcg/aggregation/searchnodelimit'
- moved parameter 'relaxing/gcg/bliss/generatorlimit' to 'relaxing/gcg/aggregation/generatorlimit'
- changed default value of 'relaxing/gcg/aggregation/generatorlimit' to 100
- moved parameter 'detection/aggregation/limitnconssperblock' to 'relaxing/gcg/aggregation/limitnconssperblock'
- moved parameter 'detection/aggregation/limitnvarsperblock' to 'relaxing/gcg/aggregation/limitnvarsperblock'
Miscellaneous
-------------
- moved files related to symmetry detection to src/symmetry/
- renamed 'pub_bliss.h' to 'pub_automorphism.h'
@page RN36 Release notes for GCG 3.6
@section RN363 GCG 3.6.3
*************************
Bug fixes
---------
- Fixed missing include of <algorithm> in some files.
@section RN362 GCG 3.6.2
*************************
Build system
------------
- CMake configuration does not fail if value of 'SYM' is not supported
@section RN361 GCG 3.6.1
*************************
Bug fixes
---------
- fix (global) bound propagation bugs
- remove columns from colpool that violate global bounds
- tree synchronization: fix segfault
- fix 'gcg_check' CMake target
- fix calculation of dual objective value and improve numerical stability
- fix calculation of reduced costs of columns (in presence of very small dual values)
- knapsack # solver reports optimality of solution if capacity is zero
- prevent cliquer # solver from creating columns that violate varbounds
New/modified/removed API functions:
---------------------------
- added function 'GCGgetColpool'
- added function 'GCGcolpoolPropagateGlobalBounds'
@section RN360 GCG 3.6.0
*************************
New features:
-------------
- MSVC support
Bug fixes
---------
- fix separation of cutting planes in the master problem
- handle new variable bounds properly when synchronizing the B&B trees
- store pending bound changes as soon as the master problem is transformed
- fix handling of static master vars with negative lower bounds
New/changed parameters:
-----------------------
- New parameter 'detection/scores/selected' to select the score that should be used to sort the decompositions
- Removed parameter 'detection/score/scoretype'
- Moved parameter 'detection/score/strong_detection/dualvalrandommethod' to 'detection/scores/strong/dualvalrandommethod'
- Moved parameter 'detection/score/strong_detection/coeffactororigvsrandom' to 'detection/scores/strong/coeffactororigvsrandom'
- Moved parameter 'detection/score/strong_detection/timelimit' to 'detection/scores/strong/timelimit'
Renamed API functions:
---------------------------
- Replaced prefix 'DEC' with 'GCG'
Renamed structures and defines:
---------------------------
- Replaced prefix 'DEC' with 'GCG'
New/modified API functions:
---------------------------
- New functions: 'GCGconshdlrDecompGetNConsClassifiers', 'GCGconshdlrDecompGetNVarClassifiers', 'GCGconshdlrDecompGetConsClassifiers', 'GCGconshdlrDecompGetVarClassifiers'
- Add parameter 'GCG_CONSCLASSIFIER* consclassifier' to 'GCG_DECL_CONSCLASSIFY'
- Add paramater 'GCG_VARCLASSIFIER* varclassifier' to 'GCG_DECL_VARCLASSIFY'
- Added function 'GCGgetCurrentScoreShortname'
- Added function 'GCGgetCurrentScore'
- Added function 'GCGincludeScore'
- Added function 'GCGfindScore'
- Added function 'GCGgetScores'
- Added function 'GCGgetNScores'
- Added function 'GCGscoreGetData'
- Added function 'GCGscoreSetData'
- Added function 'GCGscoreGetName'
- Added function 'GCGscoreGetShortname'
- Added function 'GCGscoreGetDesc'
- Added function 'GCGincludeScoreBender'
- Added function 'GCGincludeScoreBorder'
- Added function 'GCGincludeScoreClassic'
- Added function 'GCGincludeScoreFawh'
- Added function 'GCGincludeScoreForswh'
- Added function 'GCGincludeScoreMaxwhite'
- Added function 'GCGincludeScoreSpfawh'
- Added function 'GCGincludeScoreSpfwh'
- Added function 'GCGincludeScoreStrongDecomp'
- Added function 'GCGconsClassifierSetData'
- Added function 'GCGconsClassifierGetPriority'
- Added function 'GCGconsClassifierIsEnabled'
- Added function 'GCGconsClassifierGetDesc'
- Added function 'GCGvarClassifierSetData'
- Added function 'GCGvarClassifierGetPriority'
- Added function 'GCGvarClassifierIsEnabled'
- Added function 'GCGvarClassifierGetDesc'
Deleted API functions:
----------------------
- Deleted function 'GCGconshdlrDecompGetScoretype'
- Deleted function 'GCGconshdlrDecompCalcBendersScore'
- Deleted function 'GCGconshdlrDecompCalcBorderAreaScore'
- Deleted function 'GCGconshdlrDecompCalcClassicScore'
- Deleted function 'GCGconshdlrDecompCalcMaxForeseeingWhiteAggScore'
- Deleted function 'GCGconshdlrDecompCalcMaxForseeingWhiteScore'
- Deleted function 'GCGconshdlrDecompCalcMaxWhiteScore'
- Deleted function 'GCGconshdlrDecompCalcSetPartForseeingWhiteScore'
- Deleted function 'GCGconshdlrDecompCalcSetPartForWhiteAggScore'
- Deleted function 'GCGconshdlrDecompCalcStrongDecompositionScore'
Command line interface
-----------------------
- Added 'display' command for constraint classifiers
- Added 'display' command for variable classifiers
- Added 'display' command for scores
Code cleanup:
-------------
- Refactored scores
- Moved source files to src/gcg
- Moved src/test to test
@page RN35 Release notes for GCG 3.5
@section RN355 GCG 3.5.5
*************************
Bug fixes
---------
- fix handling of varbound updates if relaxator has not been called yet
@section RN354 GCG 3.5.4
*************************
Bug fixes
---------
- fix handling of file paths in multiple dialog functions
- Visualization Suite: fix error in parser
- fix multiple segmentation faults
- fix parameter 'branching/orig/userandom'
@section RN353 GCG 3.5.3
*************************
Bug fixes
---------
- fix Makefile build: create necessary directories before the dependencies are built
@section RN352 GCG 3.5.2
*************************
Bug fixes
---------
- fix errors in symmetry detection
- fix segmentation faults
- add missing headers to CMake file
@section RN351 GCG 3.5.1
*************************
Bug fixes
---------
- fix compile with new bliss version (0.77)
- fix Makefiles recompile if STATISTICS flag was changed
- fix minor bugs in the cmpres.awk script, updating it to the SCIP version
- fix memory allocation of name and description of constraint and variable classifiers
- fix handling of variables added after the problem was transformed
Build system
------------
- Bliss is enabled by default and the version provided by SCIP is compiled (CMake and Makefile)
@section RN350 GCG 3.5.0
*************************
New features:
-------------
- New website documentation
- Added several strong branching based branching candidate selection heuristics: strong branching with column generation, strong branching without column generation, hybrid strong/pseudocost branching, reliability branching, hierarchical strong branching, hybrid hierarchical strong/pseudocost branching, hierarchical reliability branching (primarily for original variable branching and Ryan-Foster branching).
- New detector neighborhoodmaster: calculating cons-cons adjacency (if not already done), sorting according size of neighborhood. Searching two consecutive constraints with largest size difference (according neighborhood size) in sorted constraints. All constraints having a larger neighborhood than the second one are assigned to the master.
- On reading an incomplete decomposition, the program will not necessarily assign all open elements to the master problem but detect the rest of the structure.
- Use the user's default application to open pdf files
New/changed parameters:
-----------------------
- New parameters 'branching/orig/usestrong' and 'branching/ryanfoster/usestrong' to enable strong branching for original variable branching and Ryan-Foster branching
- New parameters 'branching/bpstrong/...' to alter strong branching behavior
- New parameter 'detection/enabled' for easier en-/disabling of the detection
- New Parameter 'detection/postprocess' enables the postprocessing of decompositions
- Removed paramaters 'detection/detectors/<name>/legacymode'
- Removed parameter 'detection/conssadjcalculated'
- Removed parameter 'detection/legacymode/onlylegacymode'
- Removed parameter 'detection/legacymode/enabled'
- Removed parameter 'detection/legacymode/stairlinkingheur'
- Removed parameter 'visual/report/showtype'
- Removed parameter 'constraints/decomp/createbasicdecomp'
- Removed parameters 'detection/detectors/<name>/origenabled'
- Moved parameters 'detection/consclassifier/<name>/enabled' to 'detection/classification/consclassifier/<name>/enabled'
- Removed parameters 'detection/consclassifier/<name>/origenabled'
- Moved parameters 'detection/varclassifier/<name>/enabled' to 'detection/classification/varclassifier/<name>/enabled'
- Removed parameters 'detection/varclassifier/<name>/origenabled'
- Moved parameter 'detection/allowclassifierduplicates/enabled' to 'detection/classification/allowduplicates'
- Moved parameter 'detection/maxnclassesfornblockcandidates' to 'detection/blocknrcandidates/maxnclasses'
- Moved parameter 'detection/addblocknr' to 'set/detection/blocknrcandidates/addblocknr'
- Moved parameter 'detection/maxnclassesperclassifier' to 'detection/classification/maxnclassesperpartition'
- Moved parameter 'detection/maxnclassesperclassifierforlargeprobs' to 'detection/classification/maxnclassesperpartitionforlargeprobs'
- Moved parameter 'detection/strong_detection/dualvalrandommethod' to 'detection/score/strong_detection/dualvalrandommethod'
- Moved parameter 'detection/strong_detection/coeffactororigvsrandom' to 'detection/score/strong_detection/coeffactororigvsrandom'
- Moved parameter 'detection/scoretype' to 'detection/score/scoretype'
New/changed menu commands:
-----------------------
- Removed 'toolbox' feature from 'explore' menu
- Removed command 'toolbox'
- Removed command 'write/miplib2017features'
- Removed command 'write/miplib2017plotsanddecs'
- Removed command 'write/miplib2017shortbasefeatures'
- Removed command 'write/miplib2017featurefilepath'
- Removed command 'write/miplib2017matrixfilepath'
- Removed command 'write/miplib2017decompfilepath'
- Removed command 'write alloriginaldecompositions'
- Removed command 'write allpresolveddecompositions'
- Renamed command 'write reportdecompositions' to 'write report'
- Renamed command 'write selecteddecompositions' to 'write selected'
Visualization and testing:
--------------------------
- check/compareversions.sh runs tests on several git versions, summarizes performace results
Code cleanup:
-------------
- Cleaned up 'explore' menu
- Refactored detection loop
- Removed legacymode, including detectors 'connected', 'staircase', 'random', 'cutpacking', 'colors', 'mcl'
- Renamed class Seeed to PARTIALDECOMP
- Renamed class Seeedpool to DETPROBDATA
- Renamed SEEED_WRAPPER to PARTIALDECOMP_WRAPPER
- Renamed {Index,Cons,Var}Classifier to {Index,Cons,Var}Partition
- Refactored dialog handler
- Moved GCG version define to 'def.h', moved 'GCGprintVersion' to 'gcg_general.h/c'
New/modified API functions:
---------------------------
- New functions: 'GCGtransformProb', 'GCGpresolve', 'GCGdetect', 'GCGsolve'
- Renamed 'GCGgetGap' to 'GCGgetVarGap' and 'GCGsetGap' to 'GCGsetVarGap'
- New functions: 'GCGgetDualbound', 'GCGgetPrimalbound', 'GCGgetGap'
Bug fixes
---------
- Fixed function 'ObjPricerGcg::computeCurrentDegeneracy'
- Relaxator: Do not construct and flush the LP if it is already constructed
@page RN30 Release notes for GCG 3.0
@section RN305 GCG 3.0.5
*************************
Bug fixes
---------
- Skip structure detection if the original problem is already solved after presolving.
@section RN304 GCG 3.0.4
*************************
Bug fixes
---------
- Fix segmentation fault.
- Fix commands 'transform' and 'presolve': Check SCIP_STAGE before calling SCIPdialogExecTransform() and SCIPdialogExecPresolve().
@section RN303 GCG 3.0.3
*************************
Bug fixes
---------
- Fix several segmentation faults.
- Skip Farkas # only if at least one solution of the original problem was successfully added to the master variable space.
- Interrupt the # loop if SCIP reports that the solving process should be stopped.
- Disable the column pool in probing mode.
- 'write matrix' and 'write transmatrix' set PDF as file format in the created gnuplot file.
@section RN302 GCG 3.0.2
*************************
Bug fixes
---------
- Fix segmentation fault due to missing relaxsol event handler in BENDERS and ORIGINAL mode.
- Fix cmake module FindBLISS to handle GMP dependency correctly.
- Fix branching on directly transferred master variables in generic branching.
- Fix in pricer_gcg when calculating stabilized dual objective value.
- Fix a parameter bug concerning heuristic #.
- Fix: sort # solvers before initialization of # controller.
- Handle fixed master variables correctly when transforming values of original variables into values of master variables.
- Transfer solutions to the master problem only if it is not solved already.
@section RN301 GCG 3.0.1
*************************
Command line interface
-----------------------
- 'write matrix' and 'write transmatrix' for writing a gnuplot file showing the (original and presolved) coefficient matrix
New/changed parameters
-----------------------
- new parameter "relaxing/gcg/mipdiscretization" indicates whether to use discretization with continuous variables (only has an effect if "relaxing/gcg/discretization" is enabled)
Performance improvements
-------------------------
- Improved performance of creating Gnuplot matrix visualizations
- Corrected transfer from feasible master solutions to the original problem
- Improved performnace of calculating foreseeing decomposition scores
Code cleanup
------------
- Clean up scaling code in Gnuplot reader
Bug fixes
---------
- Fix segmentation faults in aggressive detection
- Fix toolbox method for assigning variables per regular expression
- Fix issue with setting variables as linking variables in decomposition toolbox
- Call hmetis only if at matrix should be decomposed into at least two blocks
- Fix issues with hmetis in aggressive detection
- Deal with empty or duplicate constraint names
- Fix an assertion in detection concerning a non-existent hashmap
- Fix memory error in relaxator concerning a filename string that was not freed
- Fix bug in reader_dec for original problem
- Handle double stored external branching candidates correctly in ZI rounding heuristic
- Fix issue with non-violated cuts in separation storage
- Fix NULL pointer error in two 'if' clauses in seeed pool
- Fix memory leak in event_relaxsol
- Use correct method to free event handler data in event_relaxsol.
- Fix parallelization in # loop by allowing only one job per # problem at a time
- Add a missing Makefile dependency
@section RN300 GCG 3.0.0
*************************
Features
--------
- new roundwise modular structure detection scheme:
- detectors can implement three optional methods:
- propagateSeeed : given a partial decomposition d the detector returns a set of decompositions that are a refinement of d
- finsishSeeed: given a partial decomposition d the detector returns a set of decompositions that are a refinement of d and complete
- postprocessSeeed: given a complete decomposition d the detector returns a set of complete decompositions
- there is a current pool of partial decompositions (i.e. some conss and vars are open, initilized by empty decomposition (all vars and conss are open) or user decomposition )
- in every detection round the refinement method of each active detector is called on each current partial detection and returns a (possibly empty) set of decompositions (possibly still partial but strictly more refined); afterwards the finishing method of each detector is called on each partial decomposition
- after last round the postprocessing method of the corresponding detectors is called on each complete decomposition
- duplicates of partial and complete are identified
- constraint and variable classification according to several criteria reveals more problem structure, and in particular yield candidates for the number of blocks, that are used by graph partitioning detectors
- detection process can run parallelized (in presence of multiple partial decompositions)
- structure information concerning the original problem can be used when searching structure in the transformed problem, e.g. by "detect presolve detect"
- more user interaction (see point "Command line interface" below for more information):
- by command "explore" and inspecting found decompositions,
- give partial decompositions,
- directly modify found partial decompositions
- new visualization methods for decompositions ('visualize' command in 'explore' submenu, family tree (experimental feature: finished decompositions can be seen as leaves in a forest, partial decompositions as inner nodes, ancestor descendant pairs are connected by edge ) )
- new scores to evaluate found decompositions
- solve the problem with one single block if no decomposition is available ('SCIP mode')
- extended isomorph detector by the possibility to identify blocks which are identical
w.r.t. signs (but not necessarily values) of coefficients.
- extended backtracking mechanism in diving heuristics:
single backtracking in addition to limited discrepancy search in master variable diving;
added branching on another variable and limited disc. search to original variable diving
- added menu item "write reportdecompositions" that creates a report of all decompositions in form of a .tex file
- Benders' decomposition mode has been added. The Benders' decomposition mode is activated by setting
"relaxing/gcg/mode" to 1. When using the Benders' decomposition mode, the decompositions found by the detectors are
used as the master and subproblems.
- Original mode has been added. The original mode allows the user to solve the original problem directly without any
decomposition being performed. The original mode is selected by setting "relaxing/gcg/mode" to 2.
- new # scheme:
- the # loop is now managed by a new class, the '# controller'
- # is now done by performing '# jobs', which hold a # problem, a solver to be applied and some parameters (such as whether the solver is to be applied heuristically)
- # jobs are organized in a priority queue, which is maintained by the # controller
- the latter now also decides over premature abortion of the # loop
- own data structure for # problems which also holds solving statistics and results
- extension of heuristic #, which can now be performed in multiple rounds; in particular, the MIP and the CPLEX # solver can now be applied multiple times per # loop, with increasing node, solution limits or decreasing gap limts.
- new possibility to sort # problems: reliability sorting based only on the last few # rounds
- possibility to solve # problems 'chunk'-wise, i.e. to only regard a certain subset of # problems in a pricer call
- add price store similar to SCIP's sepa store for better column management
- interface change in # solvers:
- solvers now pass their columns directly to the # storage rather than returning an array
- GCG_DECL_SOLVERSOLVE and GCG_DECL_SOLVERSOLVEHEUR callbacks now also take the master SCIP instance as an input
- new callback GCG_DECL_SOLVERUPDATE, called by the pricer when constraint, bound or objective function changes occur on a # problem; also fixes a bug in the CPLEX # solver
- new return type GCG_#STATUS which replaces SCIP_STATUS in the # solvers
- add additional # and variable statistics
- add hybridization of dual variable smoothing with an ascent method
- restructure column pool similar to SCIP's cut pool
- parametrize # solver priorities
- added parameter heuristics/restmaster/pbheur to use restricted master heuristic as price-and-branch heuristic
- imitate SCIP's separation procedure in the basis separator by storing the number separation rounds in probing per node
- artificial variables can now be added in the first Farkas # iteration to make the restricted master problem
feasible (including various options on setting the big M objective coefficients of these variables)
- new # solver that solves independent set problems heuristically using the cliquer library
- enable discretization when original problem is a mixed integer program; continuous variables are convexified
- solve original LP relaxation in the root node to get a first dual bound and to run some heuristics in the original problem
Performance improvements
-------------------------
- structure detection (default) is now applicable to MIPs with much larger dimensions (150.000 x 500000)
Data structures
----------------
- new internal data structure to handle partial decompositions; see class_seeed.h for more details
- new internal data structure to handle detection loops for different formulations (at the moment original and transformed formulation); see class_seeedpool.h for more information
- new internal data structure to handle constraint classification, each constraint classification is a partition of the constraints according a given criteria, used constraint classifiers:
- number of nonzero entries
- constraint type according to SCIP constraint handlers
- constraint type according to MIPLIB2010 constraint classifiaction
- constraint name: identity for names with removed digits
- constraint name: levenshtein distance graph, for names according to nodes in the same connected component
- new internal data structure to handle variable classification, each variable classifier is a partition of the variables according to some criteria
- SCIP variable type
- objective coefficient
- objective sign
Deleted and modified API functions
-----------------------------------
- detector callback DETECTSTRUCTURE is only called in optional legacy mode (legacy mode is detection of version 2.1.4 and completely indepedent from new detecion loop), detectors written by the user should be useable if their parameter detection/detectors/*/legacymode is set to TRUE
New API functions
-----------------
- detector callback PROPAGATESEEED, called during detection loop to refine partial decompositions, given a partial decomposition d the detector returns a set of decompositions that are a refinement of d
- detector callback FINISHSEEED, called during detection loop to finish partial decompositions, given a partial decomposition d the detector returns a set of complete decompositions that are a refinement of d
- detector callback POSTPROCESSSEEED, called after detection loop, to postprocess found finished decompositions, given a complete decomposition this method returns a set of complete decompositions
Command line interface
-----------------------
- "explore" submenu to inspect and modify new decompositions
- "explore inspect" get information about decomposition on different detail levels
- "explore visualize" experimental feature, opens a gnuplot generated pdf visualization of specified decomposition, see /visual/pdfreader parametr
- "explore modify" modify known (partial) decompositions by applying specified detector callbacks or assign certain variables/constraints by name
- "explore calc_strong" highly experimental feature, calculates a score that is based on strength and solving speed of the Dantzig-Wolfe subproblems
- "decomposition_toolbox" creates an empty decomposition (and modify afterwards)
- "write alloriginaldecompositions": write all known original decompositions to files (format is given by file extension, e.g. {dec,blk,ref,gp,tex})
- "write allpresolveddecompositions": write all known presolved decompositions to files (format is given by file extension, e.g. {dec,blk,ref,gp,tex})
- "write familytree": experimental feature, write all (partial) decompositions contained in family tree to files (.gp/.tex) and create family tree file (.tex), and corresponding makefile and docu
- "write reportdecompositions":experimental feature, write report of all finished decompositions to LaTeX format
- "set detection addblocknr": add candidates for the number of blocks (as a white space separated list)
Deleted and modified parameters
--------------------------------
- modified parameter "detectors/*/priority" (detection was aborted if high priority detector was successful)
New/changed parameters
-----------------------
- new parameter "constraints/decomp/createbasicdecomp" indicates whether to create a decomposition with all constraints in the master if no other specified (useful to have included comparison)
- new parameter "detection/aggregation/limitnconssperblock" if this limit on the number of constraints of a block is exceeded the aggregation information for this block is not calculated
- new parameter "detection/aggregation/limitnvarsperblock" if this limit on the number of variables of a block is exceeded the aggregation information for this block is not calculated
- new parameter "detection/allowclassifierduplicates/enabled" indicates whether classifier duplicates are allowed (for statistical reasons)
- new parameter "detection/benders/enabled" indicates whether benders detection is enabled
- new parameter "detection/benders/onlybinmaster" indicates whether only decompositions with only binary variables in the master should be searched if benders detection is enabled
- new parameter "detection/benders/onlycontsubpr" indicates whether only decompositions with only continiuous variables in the subproblems should be searched if benders detection is enabled
- new parameter "detection/consclassifier/*/enabled" indicates whether corresponding constraint classifier is enabled
- new parameter "detection/consclassifier/*/origenabled" indicates whether corresponding constraint classifier is enabled for original problem (no effect if "detection/origprob/classificationenabled" is FALSE )
- new parameter "detection/legacymode/enabled" indicates whether detection should additionally do legacy mode detection (detection of version 2.1.4)
- new parameter "detection/legacymode/onlylegacymode" indicates whether detection should only consist of legacy mode detection
- new parameter "detection/maxnclassesfornblockcandidates" to specify the maximum number of classes per classifier (if this number is exceeed two smallest classes are merged until it is reached, both classifier are kept)
- new parameter "detection/maxnclassesperclassifier" to specify the maximum number of classes per classifier (if this number is exceeed two smallest classes are merged until it is reached, both classifier are kept)
- new parameter "detection/maxnclassesperclassifierforlargeprobs" same as "detection/maxnclassesperclassifier" but only for larger problems (atm with nvars + nconss >= 50000)
- new parameter "detection/maxrounds" to specifiy the number of refinement rounds during detection
- new parameter "detection/origprob/classificationenabled" indicates whether constraint and variable classification is also enabeled for opriginal problem
- new parameter "detection/origprob/enabled" indicates whether to detect structures in original problem found decomps are tried to translate to transformed problem; only useful if presolving is enabled
- new parameter "detection/origprob/weightinggpresolvedoriginaldecomps" weighting method when comparing decompositions for presolved and unpresolved problem: 0: NO_MODIF, 1: FRACTION_OF_NNONZEROS, 2: FRACTION_OF_NROWS, 3: FAVOUR_PRESOLVED
- new parameter "detection/scoretype" indicates which score should be used for comparing (partial) decompositions (0: max white, 1: border area, 2: classic, 3: max foreseeing white, 4: ppc-max-white, 5: max foreseeing white with aggregation info, 6: ppc-max-white with aggregation info, 7: experimental benders score)
- new parameter "detection/detectors/*/enabled" is this detector enabled when detecting in the transformed problem
- new parameter "detection/detectors/*/finishingenabled" is this detector enabled when finishing partial decompsositions in the original and transformed problem
- new parameter "detection/detectors/*/freqcallround" frequency the detector gets called in detection loop ,ie it is called in round r if and only if mincallround <= r <= maxcallround AND (r - mincallround) mod freqCallRound == 0
- new paramater "detection/detectors/*/legacymode" flag to indicate whether (old) DETECTSTRUCTURE method of detector should be used
- new parameter "detection/detectors/*/maxcallround" maximum round the detector gets called in detection loop
- new parameter "detection/detectors/*/mincallround" minimum round the detector gets called in detection loop
- new parameter "detection/detectors/*/origenabled" is this detector enabled when detecting in the original problem (overruled by "detection/origprob/enabled" )
- new parameter "detection/detectors/*/origfreqcallround" same as "detectors/*/freqcallround" for original problem
- new parameter "detection/detectors/*/origmaxcallround" same as "detectors/*/maxcallround" for original problem
- new parameter "detection/detectors/*/origmincallround" same as "detectors/*/mincallround" for original problem
- new parameter "detection/detectors/*/overruleemphasis" flag to indicate whether emphasis settings for detector <%s> should be overruled by normal settings
- new parameter "detection/detectors/*/postprocessingenabled" is this detector enabled when postprocessing in the original and the transformed problem
- new parameter "detection/detectors/*/usefulrecall" indicates whether this detector is called on descendants of a partial decomposition
- new parameter "detection/detectors/connectedbase/useconssadj" should the constraint adjacency datastructure be used (and not the constraint-variable-incidency)
- new parameter "detection/detectors/{hrgpartition,hrcgpartition,hcgpartition}/maxnblockcandidates" the maximal number of block number candidates that is used by this detector
- new parameter "detection/strong_detection/coeffactororigvsrandom": convex coefficient for original dual values (1-this is factor for random dual value)
- new parameter "detection/strong_detection/dualvalrandommethod": method for random dual values use for strong decomposition: 1) naive, 2) expected equality exponential distributed, 3) expected overestimation exponential distributed
- new parameter "detection/varclassifier/*/enabled" indicates whether corresponding variable classifier is enabled
- new parameter "detection/varclassifier/*/origenabled" indicates whether corresponding variable classifier is enabled for original problem (no effect if "detection/origprob/classificationenabled" is FALSE
- new parameters "#/masterpricer/maxcolsprob*" limit number of columns to be generated per # problem
- new parameter "#/masterpricer/heur#iters" replaces old parameter "#/masterpricer/heur#" and sets maximum number of heuristic # rounds within the # loop
- new parameter "#/masterpricer/maxheurdepth" limits maximum depth in the b&b tree at which heuristic # is performed
- changed parameter "#/masterpricer/sorting" to type 'char' and add an option to sort by reliability based only on the last few rounds
- new parameter "#/masterpricer/nroundscol" sets the number of # rounds considered in that case
- new parameter "#/masterpricer/chunksize" sets the size of the subset ('chunk') of # problems to be considered in a # round
- new parameter "#/masterpricer/stabilizationtree" to enable or disable stabilization beyond the root node
- new parameter "#/masterpricer/useartificualvars" to use artificial variables to make the RMP feasible
- new parameter "#/masterpricer/bigmartificial" to set big M objective of artificial variables
- new parameter "#/masterpricer/factorunreliable" to set factor to be used for the objective of unbounded variables
- new parameter "#/masterpricer/usemaxobj" to limit big M objective of artificial variables
- new parameter "relaxing/gcg/mode" is used to set the the Dantzig-Wolfe or Benders' decomposition mode of GCG.
- new parameter "set/visual/colorscheme" sets the color scheme of visualizations produced by the gp and tex reader
- new parameter "set/visual/draftmode" sets whether nonzeros are shown in visualizations produced by the gp and tex reader
- new parameter "set/visual/nonzeroradius" sets the radius of nonzeros in visualizations produced by the gp and tex reader
- new parameter "set/visual/pdfreader" sets a PDF reader that is used for opening visualizations
- new parameter "set/visual/nmaxdecompstowrite" sets maximum number of decompositions to write
- new parameter "set/visual/colors/colorblock" sets color for blocks in visualizations produced by the gp and tex reader
- new parameter "set/visual/colors/colorlines" sets color for lines in visualizations produced by the gp and tex reader
- new parameter "set/visual/colors/colorlinking" sets color for linking variables in visualizations produced by the gp and tex reader
- new parameter "set/visual/colors/colormasterconss" sets color for master constraints in visualizations produced by the gp and tex reader
- new parameter "set/visual/colors/colormastervars" sets color for master variables in visualizations produced by the gp and tex reader
- new parameter "set/visual/colors/colornonzeros" sets color for nonzeros in visualizations produced by the gp and tex reader
- new parameter "set/visual/colors/coloropen" sets color for open areas in visualizations produced by the gp and tex reader
- new parameter "set/visual/colors/colorstairlinking" sets color for stairlinking variables in visualizations produced by the gp and tex reader
- new parameter "set/visual/famtree/maxndecomps" sets maximum number of finished decompositions in family tree
- new parameter "set/visual/report/maxndecomps" sets maximum number of decompositions shown in report
- new parameter "set/visual/report/showstatistics" sets whether statistics for each decomposition are included in report
- new parameter "set/visual/report/showtitle" sets whether a title page is included in report
- new parameter "set/visual/report/showtoc" sets whether a table of contents is included in report
- new parameter "set/visual/report/showtype" sets whether only decompositions of a certain type are included in report
- new parameter "set/visual/report/usegp" sets whether the report uses gnuplot or LaTeX/Tikz images in report
Code cleanup
------------
- use SCIP_STATISTIC for # statistics and add compiler flag STATISTICS; if STATISTICS is set to true,
SCIP_STATISTIC will be defined
- add parameter in basis separator specifying the emphasis setting used for separation in probing; remove unnecessary
distinctions on objective direction
- introduce new module solver.c for managing # solvers, to be compliant to how SCIP plugins are designed
- re-structured solver_mip
Bug fixes
---------
- fix a bug in the automatic update of the stabilization parameter alpha
- fix issue with # problem initialization in CPLEX # solver
- fix detection of knapsack subproblems in knapsack # solver by also accepting negative weights
- fix memory management in set covering heuristic
- fix a bug in GCG feasibility pump concerning wrong SCIP instances.
@page RN21 Release notes for GCG 2.1
@section RN214 GCG 2.1.4
*************************
- use SCIPaddRow() instead of deprecated SCIPaddCut()
@section RN213 GCG 2.1.3
*************************
- changed interface to SCIP 5.0.0
bug fixes
- fix memory bug in original diving event handler
- fix memory bug in DECdecompRemoveDeletedConss
- fix bugs in check script
- fix bug in checking if master is a set partitioning problem
- implement enforelax callbacks
- diving heuristics and branching rules compute fractionalities by themselves
@section RN212 GCG 2.1.2
*************************
- changed interface to SCIP 4.0.0
code cleanup
- cleanup for extreme point heuristics, moved code to own methods, added comments, remove redundant parameters
- reallocate memory for origvars array in #vardate more efficiently
- reallocate memory for original variable array in # variable data more efficiently
- reorder permutations in isomorph detector according to orbit size and add maxdecomps parameter
bug fixes
- changed/corrected variable fixing behaviour of Extreme Point RINS in case of aggregated blocks
- fixed handling of fixed variables in decompositions
- update include method of solver template
- fix GCGconsGet*() methods such that negated variables are handled correctly
- fix bug in transformation of master solution to original solution
- small bugfix in method that creates column graph from matrix
- fixed memory errors in unit tests
- fix memory issue with GCG_COL's
- fix the deletion of old columns in the column pool
- fix propagation of original variable bounds to the # problems:
propapagte bounds only if identical variables have the same bounds,
throw an error message otherwise
- in case of global bound changes on original variables, check if the current relaxation
solution satisfies the new bound, and mark it invalid if not
- stop the reduced cost # clock correctly
- free redundant decompositions correctly
- fix identity check of decompositions
- fix bug in createPolishedDecomp()
- fix bug in isomorph detector
- avoid numerical troubles by rounding integral # solutions if possible
@section RN211 GCG 2.1.1
*************************
code cleanup
- simplified logic when assigning variables to blocks
bug fixes
- use only one hashmap when initializing # problems
- small bugfix in set covering heuristic
- fixed a bug in original variable diving heuristics
- fixed a time limit issue concerning the master problem that was introduced by the SCIP reoptimization feature
- reorganized detector callbacks and thus fixed memory leaks when reading a new instance
- fixed memory allocation in basis separator
@section RN210 GCG 2.1.0
*************************
features
- column pool
- new set covering heuristic
- basis cuts separator
- numerical tolerances of the original problem are used in the master and # problems
- new compiler flag CPLEXSOLVER to solve # problems with CPLEX
code cleanup
- re-organized constraint handlers for managing branching decisions in original and master problems
- simplified code and reduced memory consumption in cutpacking detector
bug fixes
- GCG columns are freed correctly in the pricer
@page RN20 Release notes for GCG 2.0
@section RN201 GCG 2.0.1
*************************
features
- decomposition and # problems are permuted when the permutation
seed is set
- progress in dual bound is now displayed while solving the root node
- # solvers can be enabled or disabled via parameter
- display blocks found for decomposition in statistics
- new boundtype for fixed original variables due to branching
- use new GCG column structure instead SCIP solution structure in #
code cleanup
- simplify code in generic branching
- structure of method branchVar()
bug fixes
- fix bugs concerning stabilization
- disable stabilization when linking variables or variables belonging to no block are present
- CPLEX # solver is disabled as it is incompatible with generic branching
- fix memory issues
- fix bound propagation bugs
- fix bug in knapsack solver
- delete constraints added at presolving after the root node
- check feasibility of current solution in original problem if this fails in the transformed problem
- fix wrong aggregation when using bliss
- print warnings when # is aborted
- fix translation of original solution to master problem when # problems are aggregated
- better handling of infinite objective values in #
@section RN200 GCG 2.0
*************************
features
- GCG can now automatically create a decomposition to solve the LP with
empty # problems. See the cons/decomp/createbasicdecomp parameter
- GCG can aggregate # problems using bliss which enables us to
aggregate more # problems
- GCG can solve # problems in parallel
- GCG uses dual variable smoothing to stabilize dual values
- GCG can branch on integer aggregated problems using Vanderbeck's general
branching rule
- GCG can solve integer knapsack problems as a dynamic program
- GCG features additional detectors which are able to detect significantly
more structures such as staircase structures and problems that can be
aggregated
- improved heuristics
- copy solutions from original problem to master problem
- improved handling of compile flags changes such as an automatic
recompilation if, e.g., USRFLAGS change
- new solver for # problems that uses CPLEX to solve the MIP
(enabled if LPS=cpx)
code cleanup
- moved some detection methods to a more global scope to make them reusable
- added testing framework to do regression testing (uses google test)
- extracted graph methods for reuse
- branching is now done in the master problem
- remove code that was never called
- Rename methods in order to state their intention
- provide a gcg.h file to easily use the most common methods
bug fixes
- memory allocation bugs
- bound change propagation fixes
- corrected copyright
- fixed a lot of code checker issues
- use an event handler to disable the master display
- override PARASCIP=true if OPENMP=true
- correct decomp documentation and simplify decomposition interfaces
@page RN11 Release notes for GCG 1.1
@section RN110 GCG 1.1
*************************
features
- add staircase structure information
- add staircase structure detection
- the set partitioning detector can create decompositions with one block
- GCG is now separated in a library and a main file so that you can link
against it
bug fixes
- decompositions are now correctly classified
- clean up lots of errors related to inconsistent decompositions
- safe handling of empty problems
- fix detection of identical #problems for aggregation
code cleanup
- use DECfilloutDecdecompFromHashmaps where appropriate to remove redundant
code
- Provide DECfillOutFromConstoblock to enable creation of decomposition
structures by just specifying constraint to block partition
- Add consistency check function for decompositions
- removed a bit of redundant and leftover code
@page RN10 Release notes for GCG 1.0
@section RN100 GCG 1.0
*************************
features
- include variable deletion code
- add a block diagonal detector (cons_connected)
- add a new default constraint based decomposition format with reader (dec)
- added new heuristics gcgrins and xprins
- decompositions from multiple detectors are compared in cons_decomp.h
- added block diagonal detection code, GCG solves these more intelligently
- added detection of standard problems to block detection code
- add additional statistics
- structure information can now contain presolving information
- GCG works with SCIP version 3.0
plugins
- reworked decdecomp structure handling
- merge recent SCIP heuristic changes to their GCG counterparts
bug fixes
- try to deal with the time limit of the master by looping until the
original instance hits the time limit
- try to avoid infeasible problems if the timelimit is hit during farkas
#
- fix bugs related to copying master solutions to the original problem
- fix bugs where solutions are not correctly freed
- fix bug: heuristics that use SCIPcopy really create a working copy
- fix propagation bugs