gcgcol.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program */
4 /* GCG --- Generic Column Generation */
5 /* a Dantzig-Wolfe decomposition based extension */
6 /* of the branch-cut-and-price framework */
7 /* SCIP --- Solving Constraint Integer Programs */
8 /* */
9 /* Copyright (C) 2010-2018 Operations Research, RWTH Aachen University */
10 /* Zuse Institute Berlin (ZIB) */
11 /* */
12 /* This program is free software; you can redistribute it and/or */
13 /* modify it under the terms of the GNU Lesser General Public License */
14 /* as published by the Free Software Foundation; either version 3 */
15 /* of the License, or (at your option) any later version. */
16 /* */
17 /* This program is distributed in the hope that it will be useful, */
18 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
19 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
20 /* GNU Lesser General Public License for more details. */
21 /* */
22 /* You should have received a copy of the GNU Lesser General Public License */
23 /* along with this program; if not, write to the Free Software */
24 /* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.*/
25 /* */
26 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
27 
36 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
37 
38 #include "pub_gcgcol.h"
39 
40 #include "gcg.h"
41 #include "scip/def.h"
42 #include "scip/scip.h"
43 #include "scip/cons_linear.h"
44 #include "scip_misc.h"
45 #include "blockmemshell/memory.h"
46 #include "pricer_gcg.h"
47 #include "sepa_master.h"
48 
49 #include <assert.h>
50 
52 SCIP_RETCODE GCGcreateGcgCol(
53  SCIP* pricingprob,
54  GCG_COL** gcgcol,
55  int probnr,
56  SCIP_VAR** vars,
57  SCIP_Real* vals,
58  int nvars,
59  SCIP_Bool isray,
60  SCIP_Real redcost
61  )
62 {
63  int i;
64  int nnonz;
65 
66  SCIP_CALL( SCIPallocMemory(pricingprob, gcgcol) );
67 
68  SCIP_CALL( SCIPallocMemoryArray(pricingprob, &((*gcgcol)->vars), nvars) );
69  SCIP_CALL( SCIPallocMemoryArray(pricingprob, &((*gcgcol)->vals), nvars) );
70 
71  (*gcgcol)->pricingprob = pricingprob;
72  (*gcgcol)->probnr = probnr;
73  (*gcgcol)->isray = isray;
74  (*gcgcol)->redcost = redcost;
75  (*gcgcol)->age = 0;
76  (*gcgcol)->mastercoefs = NULL;
77  (*gcgcol)->mastercuts = NULL;
78  (*gcgcol)->linkvars = NULL;
79  (*gcgcol)->nmastercoefs = 0;
80  (*gcgcol)->nmastercuts = 0;
81  (*gcgcol)->nlinkvars = 0;
82  (*gcgcol)->initcoefs = FALSE;
83 
84 
85  nnonz = 0;
86  for( i = 0; i < nvars; ++i )
87  {
88  SCIP_VAR* origvar;
89  SCIP_Real scalar;
90  SCIP_Real constant;
91  SCIP_Real origval;
92 
93  scalar = 1.0;
94  constant = 0.0;
95 
96  origvar = vars[i];
97 
98  /* todo: capture vars? */
99  SCIP_CALL( SCIPvarGetOrigvarSum(&origvar, &scalar, &constant) );
100 
101  assert( !SCIPisZero(pricingprob, scalar) );
102 
103  origval = (vals[i] - constant) / scalar;
104 
105  /* round origval if possible to avoid numerical troubles */
106  if( SCIPvarIsIntegral(origvar) && SCIPisFeasIntegral(pricingprob, origval) )
107  origval = SCIPround(pricingprob, origval);
108 
109  if( !SCIPisZero(pricingprob, origval) )
110  {
111  (*gcgcol)->vars[nnonz] = origvar;
112  (*gcgcol)->vals[nnonz] = origval;
113  ++nnonz;
114  }
115  }
116 
117  (*gcgcol)->nvars = nnonz;
118 
119  /* sort vars and vals array w.r.t. variable index */
120  SCIPsortPtrReal((void**)(*gcgcol)->vars, (double*)(*gcgcol)->vals, SCIPvarComp, nnonz);
121 
122 #ifndef NDEBUG
123  for( i = 1 ; i < (*gcgcol)->nvars; ++i )
124  {
125  assert( SCIPvarCompare((*gcgcol)->vars[i-1], (*gcgcol)->vars[i]) != 0 );
126  }
127 #endif
128  return SCIP_OKAY;
129 }
130 
133  GCG_COL** gcgcol
134  )
135 {
136  assert(gcgcol != NULL);
137  assert(*gcgcol != NULL);
138 
139  /* todo: release vars? */
140  assert((*gcgcol)->nvars == 0 || (*gcgcol)->vars != NULL);
141  SCIPfreeMemoryArrayNull((*gcgcol)->pricingprob, &(*gcgcol)->vars);
142  assert((*gcgcol)->nvars == 0 || (*gcgcol)->vals != NULL);
143  SCIPfreeMemoryArrayNull((*gcgcol)->pricingprob, &(*gcgcol)->vals);
144  SCIPfreeMemoryArrayNull((*gcgcol)->pricingprob, &(*gcgcol)->mastercoefs);
145  SCIPfreeMemoryArrayNull((*gcgcol)->pricingprob, &(*gcgcol)->linkvars);
146  SCIPfreeMemoryArrayNull((*gcgcol)->pricingprob, &(*gcgcol)->mastercuts);
147  SCIPfreeMemory((*gcgcol)->pricingprob, gcgcol);
148 }
149 
152  SCIP* pricingprob,
153  GCG_COL** gcgcol,
154  int prob,
155  SCIP_SOL* sol,
156  SCIP_Bool isray,
157  SCIP_Real redcost
158 )
159 {
160  SCIP_VAR** solvars;
161  SCIP_VAR** colvars;
162 
163  SCIP_Real* colvals;
164 
165  int nsolvars;
166  int ncolvars;
167 
168  int i;
169 
170  solvars = SCIPgetOrigVars(pricingprob);
171  nsolvars = SCIPgetNOrigVars(pricingprob);
172 
173  SCIP_CALL( SCIPallocBufferArray(pricingprob, &colvars, nsolvars) );
174  SCIP_CALL( SCIPallocBufferArray(pricingprob, &colvals, nsolvars) );
175 
176  ncolvars = 0;
177 
178  for( i = 0; i < nsolvars; ++i )
179  {
180  SCIP_VAR* solvar;
181  SCIP_Real solval;
182 
183  solvar = solvars[i];
184  solval = SCIPgetSolVal(pricingprob, sol, solvar);
185 
186  /* round solval if possible to avoid numerical troubles */
187  if( SCIPvarIsIntegral(solvar) && SCIPisFeasIntegral(pricingprob, solval) )
188  solval = SCIPround(pricingprob, solval);
189 
190  if( SCIPisZero(pricingprob, solval) )
191  {
192  continue;
193  }
194 
195  colvars[ncolvars] = solvar;
196  colvals[ncolvars] = solval;
197  ++ncolvars;
198  }
199 
200  SCIP_CALL( GCGcreateGcgCol(pricingprob, gcgcol, prob, colvars, colvals, ncolvars, isray, redcost) );
201 
202  SCIPfreeBufferArray(pricingprob, &colvals);
203  SCIPfreeBufferArray(pricingprob, &colvars);
204 
205  return SCIP_OKAY;
206 }
207 
209 SCIP_DECL_SORTPTRCOMP(GCGcolCompRedcost)
210 {
211  SCIP_Real redcost1;
212  SCIP_Real redcost2;
213 
214  redcost1 = GCGcolGetRedcost((GCG_COL*) elem1);
215  redcost2 = GCGcolGetRedcost((GCG_COL*) elem2);
216 
217  if( redcost1 < redcost2 )
218  return -1;
219  else if( redcost1 > redcost2 )
220  return +1;
221  else
222  return 0;
223 }
224 
226 SCIP_DECL_SORTPTRCOMP(GCGcolCompAge)
227 {
228  int age1;
229  int age2;
230 
231  age1 = GCGcolGetAge((GCG_COL*) elem1);
232  age2 = GCGcolGetAge((GCG_COL*) elem2);
233 
234  if( age1 < age2 )
235  return +1;
236  else if( age1 > age2 )
237  return -1;
238  else
239  return 0;
240 }
241 
243 SCIP_Bool GCGcolIsEq(
244  GCG_COL* gcgcol1,
245  GCG_COL* gcgcol2
246 )
247 {
248  SCIP* pricingprob;
249 
250  SCIP_VAR** vars1;
251  SCIP_VAR** vars2;
252 
253  SCIP_Real* vals1;
254  SCIP_Real* vals2;
255 
256  int nvars1;
257  int nvars2;
258  int probnr1;
259  int probnr2;
260 
261  int i;
262 
263 
264  probnr1 = GCGcolGetProbNr(gcgcol1);
265  probnr2 = GCGcolGetProbNr(gcgcol2);
266 
267  if( probnr1 != probnr2 )
268  return FALSE;
269 
270  nvars1 = GCGcolGetNVars(gcgcol1);
271  nvars2 = GCGcolGetNVars(gcgcol2);
272 
273  if( nvars1 != nvars2 )
274  return FALSE;
275 
276  pricingprob = GCGcolGetPricingProb(gcgcol1);
277  vars1 = GCGcolGetVars(gcgcol1);
278  vars2 = GCGcolGetVars(gcgcol2);
279 
280  vals1 = GCGcolGetVals(gcgcol1);
281  vals2 = GCGcolGetVals(gcgcol2);
282 
283  for( i = 0; i < nvars1; ++i )
284  {
285  SCIP_VAR* var1;
286  SCIP_VAR* var2;
287 
288  SCIP_Real val1;
289  SCIP_Real val2;
290 
291  var1 = vars1[i];
292  var2 = vars2[i];
293 
294  val1 = vals1[i];
295  val2 = vals2[i];
296 
297  if( SCIPvarCompare(var1, var2) != 0 || !SCIPisEQ(pricingprob, val1, val2) )
298  {
299  return FALSE;
300  }
301  }
302 
303  return TRUE;
304 
305 }
306 
309  GCG_COL* gcgcol
310  )
311 {
312  return gcgcol->probnr;
313 }
314 
317  GCG_COL* gcgcol
318  )
319 {
320  return gcgcol->pricingprob;
321 }
322 
324 SCIP_VAR** GCGcolGetVars(
325  GCG_COL* gcgcol
326  )
327 {
328  return gcgcol->vars;
329 }
330 
332 SCIP_Real* GCGcolGetVals(
333  GCG_COL* gcgcol
334  )
335 {
336  return gcgcol->vals;
337 }
338 
341  GCG_COL* gcgcol
342  )
343 {
344  return gcgcol->nvars;
345 }
346 
348 SCIP_Bool GCGcolIsRay(
349  GCG_COL* gcgcol
350  )
351 {
352  return gcgcol->isray;
353 }
354 
357  GCG_COL* gcgcol
358  )
359 {
360  return gcgcol->redcost;
361 }
362 
365  GCG_COL* gcgcol
366  )
367 {
368  return gcgcol->age;
369 }
370 
373  GCG_COL* gcgcol,
374  SCIP_Real redcost,
375  SCIP_Bool growold
376  )
377 {
378  gcgcol->redcost = redcost;
379 
380  if( !growold )
381  return;
382 
383  if( !SCIPisNegative(gcgcol->pricingprob, redcost) )
384  ++(gcgcol->age);
385  else
386  gcgcol->age = 0;
387 }
388 
391  GCG_COL* gcgcol
392  )
393 {
394  return gcgcol->mastercoefs;
395 }
396 
399  GCG_COL* gcgcol
400  )
401 {
402  return gcgcol->nmastercoefs;
403 }
404 
406 SCIP_RETCODE GCGcolSetMastercoefs(
407  GCG_COL* gcgcol,
408  SCIP_Real* mastercoefs,
409  int nmastercoefs
410  )
411 {
412  int i;
413 
414  SCIPdebugMessage("Col set master coefs\n");
415  assert(gcgcol->nmastercoefs == 0);
416  if( nmastercoefs == 0 )
417  return SCIP_OKAY;
418 
419  SCIP_CALL( SCIPallocMemoryArray(gcgcol->pricingprob, &(gcgcol->mastercoefs), nmastercoefs) );
420 
421  for( i = 0; i < nmastercoefs; ++i )
422  {
423  SCIP_Real coef = mastercoefs[i];
424  gcgcol->mastercoefs[i] = coef;
425  }
426 
427  gcgcol->nmastercoefs = nmastercoefs;
428 
429  return SCIP_OKAY;
430 }
431 
434  GCG_COL* gcgcol,
435  SCIP_Real norm
436  )
437 {
438  gcgcol->norm = norm;
439 }
440 
443  SCIP* scip,
444  GCG_COL* gcgcol
445  )
446 {
447  int i;
448  SCIP_Real norm;
449 
450  SCIP_Real* solvals;
451  SCIP_Real* mastercoefs;
452  int nmastercoefs;
453  SCIP_Real* mastercuts;
454  int nmastercuts;
455  int* linkvars;
456  int nlinkvars;
457 
458  assert(scip != NULL);
459  assert(gcgcol != NULL);
460 
461  solvals = GCGcolGetVals(gcgcol);
462  nmastercoefs = GCGcolGetNMastercoefs(gcgcol);
463  mastercoefs = GCGcolGetMastercoefs(gcgcol);
464  nmastercuts = GCGcolGetNMastercuts(gcgcol);
465  mastercuts = GCGcolGetMastercuts(gcgcol);
466  nmastercuts = GCGcolGetNMastercuts(gcgcol);
467  nlinkvars = GCGcolGetNLinkvars(gcgcol);
468  linkvars = GCGcolGetLinkvars(gcgcol);
469 
470  norm = 0.0;
472  for( i = 0; i < nmastercoefs; ++i )
473  {
474  if( !SCIPisZero(scip, mastercoefs[i]))
475  norm += SQR(mastercoefs[i]);
476  }
477 
478  for( i = 0; i < nmastercuts; ++i )
479  {
480  if( !SCIPisZero(scip, mastercuts[i]))
481  norm += SQR(mastercuts[i]);
482  }
483 
484 
485  for( i = 0; i < nlinkvars; ++i )
486  {
487  if( !SCIPisZero(scip, solvals[linkvars[i]]) )
488  norm += solvals[linkvars[i]];
489  }
490 
491  /* consider convexity constraint */
492  norm += 1.0;
493 
494  gcgcol->norm = norm;
495 }
496 
499  GCG_COL* gcgcol
500  )
501 {
502  assert(!gcgcol->initcoefs);
503  gcgcol->initcoefs = TRUE;
504  return SCIP_OKAY;
505 }
506 
509  GCG_COL* gcgcol
510  )
511 {
512  return gcgcol->initcoefs;
513 }
514 
517  GCG_COL* gcgcol
518  )
519 {
520  return gcgcol->linkvars;
521 }
522 
525  GCG_COL* gcgcol
526  )
527 {
528  return gcgcol->nlinkvars;
529 }
530 
532 SCIP_RETCODE GCGcolSetLinkvars(
533  GCG_COL* gcgcol,
534  int* linkvars,
535  int nlinkvars
536  )
537 {
538  int i;
539 
540  assert(gcgcol->nlinkvars == 0);
541 
542  SCIP_CALL( SCIPallocMemoryArray(gcgcol->pricingprob, &(gcgcol->linkvars), nlinkvars) );
543 
544  for( i = 0; i < nlinkvars; ++i )
545  {
546  gcgcol->linkvars[i] = linkvars[i];
547  }
548 
549  gcgcol->nlinkvars = nlinkvars;
550 
551  return SCIP_OKAY;
552 }
553 
556  GCG_COL* gcgcol
557  )
558 {
559  return gcgcol->mastercuts;
560 }
561 
564  GCG_COL* gcgcol
565  )
566 {
567  return gcgcol->nmastercuts;
568 }
569 
571 SCIP_Real GCGcolGetNorm(
572  GCG_COL* gcgcol
573  )
574 {
575  return gcgcol->norm;
576 }
577 
580  GCG_COL* gcgcol,
581  SCIP_Real* newmastercuts,
582  int nnewmastercuts
583  )
584 {
585  int i;
586 
587  if( gcgcol->nmastercuts > 0 )
588  SCIP_CALL( SCIPreallocMemoryArray(GCGcolGetPricingProb(gcgcol), &(gcgcol->mastercuts), gcgcol->nmastercuts + nnewmastercuts) );
589  else
590  SCIP_CALL( SCIPallocMemoryArray(GCGcolGetPricingProb(gcgcol), &(gcgcol->mastercuts), nnewmastercuts) );
591 
592  for( i = 0; i < nnewmastercuts; ++i )
593  {
594  gcgcol->mastercuts[gcgcol->nmastercuts] = newmastercuts[i];
595  ++(gcgcol->nmastercuts);
596  }
597 
598  return SCIP_OKAY;
599 }
600 
602 SCIP_Real GCGcolGetSolVal(
603  SCIP* scip,
604  GCG_COL* gcgcol,
605  SCIP_VAR* var
606  )
607 {
608  SCIP_VAR** vars;
609  SCIP_Real* vals;
610  int nvars;
611  int pos;
612  SCIP_Bool found;
613 
614  vars = gcgcol->vars;
615  vals = gcgcol->vals;
616  nvars = gcgcol->nvars;
617 
618  found = SCIPsortedvecFindPtr((void**) vars, SCIPvarComp, (void*) var, nvars, &pos);
619 
620  if( !found )
621  {
622  return 0.0;
623  }
624 
625  return vals[pos];
626 }
627 
629 SCIP_Bool GCGcolIsAged(
630  GCG_COL* col,
631  int agelimit
632  )
633 {
634  assert(col != NULL);
635 
636  return (agelimit >= 0 && col->age > agelimit);
637 }
638 
641  SCIP* scip,
642  GCG_COL* gcgcol
643 )
644 {
645  SCIP_Real para;
646 
647  int i;
648 
649  SCIP_CONS** masterconss;
650  SCIP_ROW** cuts;
651 
652  int prob;
653 
654  SCIP_Real* mastercoefs;
655  int nmastercoefs;
656  SCIP_Real* mastercuts;
657  int nmastercuts;
658 
659  SCIP_Real dualobjnorm;
660 
661 
662  assert(scip != NULL);
663  assert(gcgcol != NULL);
664 
665  prob = GCGcolGetProbNr(gcgcol);
666  nmastercoefs = GCGcolGetNMastercoefs(gcgcol);
667  mastercoefs = GCGcolGetMastercoefs(gcgcol);
668  nmastercuts = GCGcolGetNMastercuts(gcgcol);
669  mastercuts = GCGcolGetMastercuts(gcgcol);
670  masterconss = GCGgetMasterConss(GCGmasterGetOrigprob(scip));
671  cuts = GCGsepaGetMastercuts(scip);
672 
673  para = 0.0;
674 
675  dualobjnorm = 0.0;
676 
678  for( i = 0; i < nmastercoefs; ++i )
679  {
680  SCIP_Real lhs;
681  SCIP_Real rhs;
682 
683  lhs = SCIPgetLhsLinear(scip, masterconss[i]);
684  rhs = SCIPgetRhsLinear(scip, masterconss[i]);
685 
686  if( !SCIPisInfinity(scip, -lhs))
687  {
688  dualobjnorm += SQR(lhs);
689 
690  if( SCIPisPositive(scip, mastercoefs[i]) )
691  para += mastercoefs[i] * lhs;
692  }
693  else if( !SCIPisInfinity(scip, rhs) )
694  {
695  dualobjnorm += SQR(rhs);
696 
697  if(SCIPisNegative(scip, mastercoefs[i] ) )
698  para += mastercoefs[i] * rhs;
699  }
700  }
701 
702  for( i = 0; i < nmastercuts; ++i )
703  {
704  SCIP_Real lhs;
705  SCIP_Real rhs;
706 
707  if( !SCIProwIsInLP(cuts[i]) )
708  continue;
709 
710  lhs = SCIProwGetLhs(cuts[i]);
711  rhs = SCIProwGetRhs(cuts[i]);
712 
713  if( !SCIPisInfinity(scip, -lhs))
714  {
715  dualobjnorm += SQR(lhs);
716 
717  if( SCIPisPositive(scip, mastercuts[i]) )
718  para += mastercuts[i] * lhs;
719  }
720  else if( !SCIPisInfinity(scip, rhs) )
721  {
722  dualobjnorm += SQR(rhs);
723 
724  if(SCIPisNegative(scip, mastercuts[i] ) )
725  para += mastercuts[i] * rhs;
726  }
727  }
728 
729  for( i = 0; i < GCGgetNPricingprobs(GCGmasterGetOrigprob(scip)); ++i )
730  dualobjnorm += SQR(GCGgetNIdenticalBlocks(GCGmasterGetOrigprob(scip), i));
731 
732  para += SQR(GCGgetNIdenticalBlocks(GCGmasterGetOrigprob(scip), prob));
733 
734  assert(!SCIPisInfinity(scip, ABS(para)));
735 
736  dualobjnorm = SQRT(dualobjnorm);
737  assert(!SCIPisInfinity(scip, dualobjnorm));
738  assert(SCIPisPositive(scip, dualobjnorm));
739  assert(SCIPisPositive(scip, gcgcol->norm));
740 
741  para = para / (dualobjnorm * gcgcol->norm);
742 
743  return para;
744 }
745 
748  SCIP* scip,
749  GCG_COL* gcgcol1,
750  GCG_COL* gcgcol2
751 )
752 {
753  int i;
754  int j;
755  SCIP_Real para = 0.0;
756  SCIP_Real norm1 = 0.0;
757  SCIP_Real norm2 = 0.0;
758 
759  int prob1;
760 
761  SCIP_VAR** solvars1;
762  SCIP_Real* solvals1;
763  SCIP_Real* mastercoefs1;
764  int nmastercoefs1;
765  SCIP_Real* mastercuts1;
766  int nmastercuts1;
767  int* linkvars1;
768  int nlinkvars1;
769 
770  int prob2;
771 
772  SCIP_VAR** solvars2;
773  SCIP_Real* solvals2;
774  SCIP_Real* mastercoefs2;
775  SCIP_Real* mastercuts2;
776  int* linkvars2;
777  int nlinkvars2;
778 
779  assert(scip != NULL);
780  assert(gcgcol1 != NULL);
781  assert(gcgcol2 != NULL);
782 
783  prob1 = GCGcolGetProbNr(gcgcol1);
784  solvars1 = GCGcolGetVars(gcgcol1);
785  solvals1 = GCGcolGetVals(gcgcol1);
786  nmastercoefs1 = GCGcolGetNMastercoefs(gcgcol1);
787  mastercoefs1 = GCGcolGetMastercoefs(gcgcol1);
788  nmastercuts1 = GCGcolGetNMastercuts(gcgcol1);
789  mastercuts1 = GCGcolGetMastercuts(gcgcol1);
790  nlinkvars1 = GCGcolGetNLinkvars(gcgcol1);
791  linkvars1 = GCGcolGetLinkvars(gcgcol1);
792 
793  prob2 = GCGcolGetProbNr(gcgcol2);
794  solvars2 = GCGcolGetVars(gcgcol2);
795  solvals2 = GCGcolGetVals(gcgcol2);
796  mastercoefs2 = GCGcolGetMastercoefs(gcgcol2);
797  mastercuts2 = GCGcolGetMastercuts(gcgcol2);
798  nlinkvars2 = GCGcolGetNLinkvars(gcgcol2);
799  linkvars2 = GCGcolGetLinkvars(gcgcol2);
800 
802  for( i = 0; i < nmastercoefs1; ++i )
803  {
804  if( SCIPisPositive(scip, mastercoefs1[i] * mastercoefs2[i]) )
805  para += mastercoefs1[i] * mastercoefs2[i];
806 
807  if( SCIPisPositive(scip, mastercoefs1[i]) )
808  norm1 += SQR(mastercoefs1[i]);
809  if( SCIPisPositive(scip, mastercoefs2[i]) )
810  norm2 += SQR(mastercoefs2[i]);
811  }
812 
813  for( i = 0; i < nmastercuts1; ++i )
814  {
815  if( SCIPisPositive(scip, mastercuts1[i] * mastercuts2[i]) )
816  para += mastercuts1[i] * mastercuts2[i];
817 
818  if( SCIPisPositive(scip, mastercuts1[i]) )
819  norm1 += SQR(mastercuts1[i]);
820  if( SCIPisPositive(scip, mastercuts2[i]) )
821  norm2 += SQR(mastercuts2[i]);
822  }
823 
824  for( i = 0; i < nlinkvars1; ++i )
825  {
826  SCIP_VAR* linkvar1;
827  SCIP_Real linkval1;
828  linkvar1 = solvars1[linkvars1[i]];
829  linkval1 = solvals1[linkvars1[i]];
830 
831  norm1 += SQR(linkval1);
832 
833  for( j = 0; j < nlinkvars2; ++j )
834  {
835  SCIP_VAR* linkvar2;
836  SCIP_Real linkval2;
837  linkvar2 = solvars2[linkvars2[j]];
838  linkval2 = solvals2[linkvars2[j]];
839 
840  if( linkvar1 == linkvar2 )
841  {
842  para += linkval1 * linkval2;
843  break;
844  }
845  }
846  }
847 
848  for( i = 0; i < nlinkvars2; ++i )
849  {
850  SCIP_Real linkval2;
851 
852  linkval2 = solvals2[linkvars2[i]];
853 
854  norm2 += SQR(linkval2);
855  }
856 
857 
858  /* scalar for convexitiy constraints */
859  if( prob1 == prob2 )
860  para *= 1.0;
861 
862  norm1 *= 1.0;
863  norm2 *= 1.0;
864 
865  norm1 = SQRT(norm1);
866  norm2 = SQRT(norm2);
867 
868  assert(SCIPisPositive(scip, norm1) && SCIPisPositive(scip, norm2));
869 
870  para = para/(norm1*norm2);
871 
872  return 1.0 - para;
873 }
SCIP_Real * GCGcolGetVals(GCG_COL *gcgcol)
Definition: gcgcol.c:332
int GCGcolGetNLinkvars(GCG_COL *gcgcol)
Definition: gcgcol.c:524
SCIP_Real GCGcolComputeDualObjPara(SCIP *scip, GCG_COL *gcgcol)
Definition: gcgcol.c:640
void GCGcolComputeNorm(SCIP *scip, GCG_COL *gcgcol)
Definition: gcgcol.c:442
SCIP_Real * GCGcolGetMastercoefs(GCG_COL *gcgcol)
Definition: gcgcol.c:390
void GCGcolSetNorm(GCG_COL *gcgcol, SCIP_Real norm)
Definition: gcgcol.c:433
GCG interface methods.
SCIP_Real GCGcolGetNorm(GCG_COL *gcgcol)
Definition: gcgcol.c:571
SCIP_RETCODE GCGcreateGcgColFromSol(SCIP *pricingprob, GCG_COL **gcgcol, int prob, SCIP_SOL *sol, SCIP_Bool isray, SCIP_Real redcost)
Definition: gcgcol.c:151
SCIP_Real * GCGcolGetMastercuts(GCG_COL *gcgcol)
Definition: gcgcol.c:555
SCIP_Bool GCGcolIsEq(GCG_COL *gcgcol1, GCG_COL *gcgcol2)
Definition: gcgcol.c:243
SCIP_DECL_SORTPTRCOMP(GCGcolCompRedcost)
Definition: gcgcol.c:209
master separator
SCIP_Real GCGcolGetRedcost(GCG_COL *gcgcol)
Definition: gcgcol.c:356
SCIP_CONS ** GCGgetMasterConss(SCIP *scip)
Definition: relax_gcg.c:4011
int GCGgetNPricingprobs(SCIP *scip)
Definition: relax_gcg.c:3897
SCIP_Bool GCGcolIsRay(GCG_COL *gcgcol)
Definition: gcgcol.c:348
SCIP_Real GCGcolComputeOrth(SCIP *scip, GCG_COL *gcgcol1, GCG_COL *gcgcol2)
Definition: gcgcol.c:747
SCIP_ROW ** GCGsepaGetMastercuts(SCIP *scip)
Definition: sepa_master.c:437
public methods for working with gcg columns
struct GCG_Col GCG_COL
Definition: type_gcgcol.h:45
SCIP_Real GCGcolGetSolVal(SCIP *scip, GCG_COL *gcgcol, SCIP_VAR *var)
Definition: gcgcol.c:602
various SCIP helper methods
SCIP * GCGcolGetPricingProb(GCG_COL *gcgcol)
Definition: gcgcol.c:316
int * GCGcolGetLinkvars(GCG_COL *gcgcol)
Definition: gcgcol.c:516
SCIP_RETCODE GCGcolUpdateMastercuts(GCG_COL *gcgcol, SCIP_Real *newmastercuts, int nnewmastercuts)
Definition: gcgcol.c:579
GCG variable pricer.
SCIP_RETCODE GCGcolSetInitializedCoefs(GCG_COL *gcgcol)
Definition: gcgcol.c:498
SCIP_RETCODE GCGcolSetLinkvars(GCG_COL *gcgcol, int *linkvars, int nlinkvars)
Definition: gcgcol.c:532
int GCGcolGetNVars(GCG_COL *gcgcol)
Definition: gcgcol.c:340
SCIP_RETCODE GCGcreateGcgCol(SCIP *pricingprob, GCG_COL **gcgcol, int probnr, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_Bool isray, SCIP_Real redcost)
Definition: gcgcol.c:52
SCIP * GCGmasterGetOrigprob(SCIP *scip)
SCIP_Bool GCGcolIsAged(GCG_COL *col, int agelimit)
Definition: gcgcol.c:629
int GCGcolGetProbNr(GCG_COL *gcgcol)
Definition: gcgcol.c:308
SCIP_VAR ** GCGcolGetVars(GCG_COL *gcgcol)
Definition: gcgcol.c:324
int GCGcolGetNMastercuts(GCG_COL *gcgcol)
Definition: gcgcol.c:563
SCIP_RETCODE GCGcolSetMastercoefs(GCG_COL *gcgcol, SCIP_Real *mastercoefs, int nmastercoefs)
Definition: gcgcol.c:406
void GCGfreeGcgCol(GCG_COL **gcgcol)
Definition: gcgcol.c:132
int GCGcolGetAge(GCG_COL *gcgcol)
Definition: gcgcol.c:364
SCIP_Bool GCGcolGetInitializedCoefs(GCG_COL *gcgcol)
Definition: gcgcol.c:508
int GCGgetNIdenticalBlocks(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:3966
int GCGcolGetNMastercoefs(GCG_COL *gcgcol)
Definition: gcgcol.c:398
void GCGcolUpdateRedcost(GCG_COL *gcgcol, SCIP_Real redcost, SCIP_Bool growold)
Definition: gcgcol.c:372