SCIP-SDP  2.1.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
relax_sdp.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of SCIPSDP - a solving framework for mixed-integer */
4 /* semidefinite programms based on SCIP. */
5 /* */
6 /* Copyright (C) 2011-2013 Discrete Optimization, TU Darmstadt */
7 /* EDOM, FAU Erlangen-Nürnberg */
8 /* 2014-2016 Discrete Optimization, TU Darmstadt */
9 /* */
10 /* */
11 /* This program is free software; you can redistribute it and/or */
12 /* modify it under the terms of the GNU Lesser General Public License */
13 /* as published by the Free Software Foundation; either version 3 */
14 /* of the License, or (at your option) any later version. */
15 /* */
16 /* This program is distributed in the hope that it will be useful, */
17 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
18 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
19 /* GNU Lesser General Public License for more details. */
20 /* */
21 /* You should have received a copy of the GNU Lesser General Public License */
22 /* along with this program; if not, write to the Free Software */
23 /* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.*/
24 /* */
25 /* */
26 /* Based on SCIP - Solving Constraint Integer Programs */
27 /* Copyright (C) 2002-2016 Zuse Institute Berlin */
28 /* SCIP is distributed under the terms of the SCIP Academic Licence, */
29 /* see file COPYING in the SCIP distribution. */
30 /* */
31 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
32 
40 /* #define SCIP_DEBUG*/
41 /* #define SCIP_MORE_DEBUG *//* displays complete solution for each relaxation */
42 /* #define SCIP_EVEN_MORE_DEBUG *//* shows number of deleted empty cols/rows for every relaxation and variable status &
43  * bounds as well as all constraints in the beginning */
44 /* #define SLATERSOLVED_ABSOLUTE *//* uncomment this to return the absolute number of nodes for, e.g., solved fast with slater in addition to percentages */
45 
46 #include "relax_sdp.h"
47 
48 #include "assert.h" /*lint !e451*/
49 #include "string.h" /* for strcmp */
50 
51 #include "SdpVarmapper.h"
52 #include "sdpi/sdpi.h"
53 #include "scipsdp/cons_sdp.h"
54 #include "scipsdp/cons_savedsdpsettings.h"
55 
56 /* turn off lint warnings for whole file: */
57 /*lint --e{788,818}*/
58 
59 #define RELAX_NAME "SDP"
60 #define RELAX_DESC "SDP-relaxator"
61 #define RELAX_PRIORITY 1
62 #define RELAX_FREQ 1
63 
64 
65 /* default values for parameters: */
66 #define DEFAULT_SDPSOLVEREPSILON 1e-4
67 #define DEFAULT_SDPSOLVERFEASTOL 1e-6
68 #define DEFAULT_PENALTYPARAM -1.0
69 #define DEFAULT_LAMBDASTAR -1.0
70 #define DEFAULT_MAXPENALTYPARAM -1.0
71 #define DEFAULT_SLATERCHECK 0
72 #define DEFAULT_OBJLIMIT FALSE
73 #define DEFAULT_RESOLVE TRUE
74 #define DEFAULT_TIGHTENVB FALSE
75 #define DEFAULT_SDPINFO FALSE
76 #define DEFAULT_DISPLAYSTAT TRUE
77 #define DEFAULT_SETTINGSRESETFREQ -1
78 #define DEFAULT_SETTINGSRESETOFS 0
80 /*
81  * Data structures
82  */
83 
85 struct SCIP_RelaxData
86 {
87  SCIP_SDPI* sdpi;
88  SdpVarmapper* varmapper;
89  SCIP_Real objval;
90  SCIP_Bool origsolved;
91  SCIP_Bool probingsolved;
92  SCIP_Real sdpsolverepsilon;
93  SCIP_Real sdpsolverfeastol;
94  SCIP_Real penaltyparam;
95  SCIP_Real maxpenaltyparam;
96  SCIP_Real lambdastar;
97  int sdpiterations;
98  int solvedfast;
99  int solvedmedium;
100  int solvedstable;
101  int solvedpenalty;
102  int unsolved;
103  int slatercheck;
104  SCIP_Bool sdpinfo;
105  SCIP_Bool displaystat;
106  SCIP_Bool objlimit;
107  SCIP_Bool resolve;
108  SCIP_Bool tightenvb;
109  int settingsresetfreq;
110  int settingsresetofs;
111  int sdpcalls;
112  int sdpinterfacecalls;
113  long int lastsdpnode;
114  SCIP_Bool feasible;
115  int stablewslater;
116  int unstablewslater;
117  int penaltywslater;
118  int boundedwslater;
119  int unsolvedwslater;
120  int stablenoslater;
121  int unstablenoslater;
122  int penaltynoslater;
123  int boundednoslater;
124  int unsolvednoslater;
125  int nslaterholds;
126  int nnoslater;
127  int nslatercheckfailed;
129  int npslaterholds;
130  int npnoslater;
131  int npslatercheckfailed;
132  int ndslaterholds;
133  int ndnoslater;
134  int ndslatercheckfailed;
135  int nslaterinfeasible;
136  int stableinfeasible;
137  int unstableinfeasible;
138  int penaltyinfeasible;
139  int boundedinfeasible;
140  int unsolvedinfeasible;
141 };
142 
144 static
145 SCIP_RETCODE putSdpDataInInterface(
146  SCIP* scip,
147  SCIP_SDPI* sdpi,
148  SdpVarmapper* varmapper
149  )
150 {
151  SCIP_CONSHDLR* conshdlr;
152  const char* conshdlrname;
153  SCIP_CONS** conss;
154  SCIP_VAR** blockvars;
155  SCIP_VAR** vars;
156  SCIP_Real*** val;
157  SCIP_Real** constval;
158  SCIP_Real* obj;
159  SCIP_Real* lb;
160  SCIP_Real* ub;
161  SCIP_Real param;
162  int*** row;
163  int*** col;
164  int** nblockvarnonz;
165  int** constrow;
166  int** constcol;
167  int** sdpvar;
168  int* sdpblocksizes;
169  int* nblockvars;
170  int* nconstblocknonz;
171  int constnnonzcounter;
172  int blocknnonz;
173  int sdpconstnnonz;
174  int sdpnnonz;
175  int nsdpblocks;
176  int constlength;
177  int nvars;
178  int nconss;
179  int ind;
180  int i;
181  int j;
182 
183  SCIP_CALL( SCIPgetRealParam(scip, "relaxing/SDP/sdpsolverepsilon", &param) );
184 
185  SCIPdebugMessage("Putting SDP Data in general SDP interface!\n");
186 
187  assert( scip != NULL );
188  assert( sdpi != NULL );
189  assert( varmapper != NULL );
190 
191  vars = SCIPgetVars(scip);
192  nvars = SCIPgetNVars(scip);
193 
194  /* prepare arrays of objective values and bounds */
195  SCIP_CALL( SCIPallocBufferArray(scip, &obj, nvars) );
196  SCIP_CALL( SCIPallocBufferArray(scip, &lb, nvars) );
197  SCIP_CALL( SCIPallocBufferArray(scip, &ub, nvars) );
198 
199  for (i = 0; i < nvars; i++)
200  {
201  obj[i] = SCIPvarGetObj(vars[i]);
202  lb[i] = SCIPvarGetLbLocal(vars[i]);
203  ub[i] = SCIPvarGetUbLocal(vars[i]);
204  }
205 
206  nconss = SCIPgetNConss(scip);
207  conss = SCIPgetConss(scip);
208 
209  /* count the number of sdpblocks and compute the number of nonzeros */
210  nsdpblocks = 0;
211  sdpnnonz = 0;
212  sdpconstnnonz = 0;
213 
214  for (i = 0; i < nconss; i++)
215  {
216  conshdlr = SCIPconsGetHdlr(conss[i]);
217  assert( conshdlr != NULL );
218 
219  conshdlrname = SCIPconshdlrGetName(conshdlr);
220 
221 #ifdef SCIP_EVEN_MORE_DEBUG
222  SCIP_CALL( SCIPprintCons(scip, conss[i], NULL) );
223  SCIPinfoMessage(scip, NULL, "\n");
224 #endif
225 
226  if ( strcmp(conshdlrname, "SDP") == 0 )
227  {
228  nsdpblocks++;
229 
230  SCIP_CALL( SCIPconsSdpGetNNonz(scip, conss[i], &blocknnonz, &constnnonzcounter) );
231  sdpnnonz += blocknnonz;
232  sdpconstnnonz += constnnonzcounter;
233  }
234  }
235 
236  /* create the sdp- and sdpconst-arrays */
237  SCIP_CALL( SCIPallocBufferArray(scip, &sdpblocksizes, nsdpblocks) );
238  SCIP_CALL( SCIPallocBufferArray(scip, &nblockvarnonz, nsdpblocks) );
239  SCIP_CALL( SCIPallocBufferArray(scip, &nconstblocknonz, nsdpblocks) );
240  SCIP_CALL( SCIPallocBufferArray(scip, &col, nsdpblocks) );
241  SCIP_CALL( SCIPallocBufferArray(scip, &row, nsdpblocks) );
242  SCIP_CALL( SCIPallocBufferArray(scip, &val, nsdpblocks) );
243  SCIP_CALL( SCIPallocBufferArray(scip, &constcol, nsdpblocks) );
244  SCIP_CALL( SCIPallocBufferArray(scip, &constrow, nsdpblocks) );
245  SCIP_CALL( SCIPallocBufferArray(scip, &constval, nsdpblocks) );
246  SCIP_CALL( SCIPallocBufferArray(scip, &nblockvars, nsdpblocks) );
247  SCIP_CALL( SCIPallocBufferArray(scip, &sdpvar, nsdpblocks) );
248 
249  for (i = 0; i < nsdpblocks; i++)
250  {
251  SCIP_CALL( SCIPallocBufferArray(scip, &(nblockvarnonz[i]), nvars) );
252  SCIP_CALL( SCIPallocBufferArray(scip, &col[i], nvars) );
253  SCIP_CALL( SCIPallocBufferArray(scip, &row[i], nvars) );
254  SCIP_CALL( SCIPallocBufferArray(scip, &val[i], nvars) );
255  }
256 
257  /* get the SDP-data */
258  ind = 0; /* index of the current sdp block in the complete sdp */
259  SCIP_CALL( SCIPallocBufferArray(scip, &blockvars, nvars) );
260 
261  for (i = 0; i < nconss; i++)
262  {
263  conshdlr = SCIPconsGetHdlr(conss[i]);
264  assert( conshdlr != NULL );
265 
266  conshdlrname = SCIPconshdlrGetName(conshdlr);
267 
268  if ( strcmp(conshdlrname, "SDP") == 0 )
269  {
270  assert( ind < nsdpblocks );
271 
272  /* allocate memory for the constant nonzeros */
273  SCIP_CALL( SCIPconsSdpGetNNonz(scip, conss[i], NULL, &constlength) );
274  nconstblocknonz[ind] = constlength;
275  SCIP_CALL( SCIPallocBufferArray(scip, &(constcol[ind]), constlength) );
276  SCIP_CALL( SCIPallocBufferArray(scip, &(constrow[ind]), constlength) );
277  SCIP_CALL( SCIPallocBufferArray(scip, &(constval[ind]), constlength) );
278 
279  /* get the data */
280  SCIP_CALL( SCIPconsSdpGetData(scip, conss[i], &nblockvars[ind], &blocknnonz, &sdpblocksizes[ind], &nvars, nblockvarnonz[ind], col[ind],
281  row[ind], val[ind], blockvars, &nconstblocknonz[ind], constcol[ind], constrow[ind], constval[ind]) );
282 
283  /* nvars and nconstblocknonz[ind] would have been overwritten if the space in the given arrays hadn't been sufficient */
284  assert( nvars == SCIPgetNVars(scip) );
285  assert( nconstblocknonz[ind] <= constlength );
286 
287  SCIP_CALL( SCIPallocBufferArray(scip, &(sdpvar[ind]), nblockvars[ind]) );
288 
289  /* get global variable indices */
290  for (j = 0; j < nblockvars[ind]; j++)
291  sdpvar[ind][j] = SCIPsdpVarmapperGetSdpIndex(varmapper, blockvars[j]);
292 
293  ind++;
294  }
295  }
296 
297  /* free the memory that is no longer needed */
298  SCIPfreeBufferArray(scip, &blockvars);
299 
300  /* load data into SDPI */
301  SCIP_CALL( SCIPsdpiLoadSDP(sdpi, nvars, obj, lb, ub, nsdpblocks, sdpblocksizes, nblockvars, sdpconstnnonz, nconstblocknonz, constrow,
302  constcol, constval, sdpnnonz, nblockvarnonz, sdpvar, row, col, val, 0,
303  NULL, NULL, 0, NULL, NULL, NULL) ); /* insert the SDP part, add an empty LP part */
304 
305  /* free the remaining memory */
306  for (i = 0; i < nsdpblocks; i++)
307  {
308  SCIPfreeBufferArrayNull(scip, &(sdpvar[i]));
309  SCIPfreeBufferArrayNull(scip, &val[i]);
310  SCIPfreeBufferArrayNull(scip, &row[i]);
311  SCIPfreeBufferArrayNull(scip, &col[i]);
312  SCIPfreeBufferArrayNull(scip, &(nblockvarnonz[i]));
313  SCIPfreeBufferArrayNull(scip, &(constval[i]));
314  SCIPfreeBufferArrayNull(scip, &(constrow[i]));
315  SCIPfreeBufferArrayNull(scip, &(constcol[i]));
316  }
317 
318  SCIPfreeBufferArrayNull(scip, &sdpvar);
319  SCIPfreeBufferArrayNull(scip, &nblockvars);
320  SCIPfreeBufferArrayNull(scip, &constval);
321  SCIPfreeBufferArrayNull(scip, &constrow);
322  SCIPfreeBufferArrayNull(scip, &constcol);
323  SCIPfreeBufferArrayNull(scip, &val);
324  SCIPfreeBufferArrayNull(scip, &row);
325  SCIPfreeBufferArrayNull(scip, &col);
326  SCIPfreeBufferArrayNull(scip, &nconstblocknonz);
327  SCIPfreeBufferArrayNull(scip, &nblockvarnonz);
328  SCIPfreeBufferArrayNull(scip, &sdpblocksizes);
329  SCIPfreeBufferArray(scip, &ub);
330  SCIPfreeBufferArray(scip, &lb);
331  SCIPfreeBufferArray(scip, &obj);
332 
333  return SCIP_OKAY;
334 }
335 
337 static
338 SCIP_RETCODE putLpDataInInterface(
339  SCIP* scip,
340  SCIP_SDPI* sdpi,
341  SdpVarmapper* varmapper
342  )
343 {
344  SCIP_VAR** vars;
345  SCIP_COL** rowcols;
346  SCIP_ROW** rows;
347  SCIP_Bool tightenvb;
348  SCIP_Real* rowvals;
349  SCIP_Real* lhs;
350  SCIP_Real* rhs;
351  SCIP_Real* obj;
352  SCIP_Real* lb;
353  SCIP_Real* ub;
354  SCIP_Real* val;
355  SCIP_Real sciplhs;
356  SCIP_Real sciprhs;
357  int* inds;
358  int* objinds;
359  int* rowind;
360  int* colind;
361  int nrowssdpi;
362  int nrows;
363  int rownnonz;
364  int nvars;
365  int nconss;
366  int scipnnonz;
367  int nnonz;
368  int i;
369  int j;
370 
371  assert( scip != NULL );
372  assert( sdpi != NULL );
373  assert( varmapper != NULL );
374 
375  nvars = SCIPgetNVars(scip);
376  assert( nvars > 0 );
377 
378  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
379  SCIP_CALL( SCIPgetBoolParam(scip, "relaxing/SDP/tightenvb", &tightenvb) );
380 
381  SCIPdebugMessage("inserting %d LPRows into the interface.\n", nrows);
382 
383  /* compute the total number of LP nonzeroes in SCIP */
384  scipnnonz = 0;
385  for (i = 0; i < nrows; i++)
386  {
387  assert( rows[i] != NULL );
388  scipnnonz += SCIProwGetNNonz(rows[i]);
389  }
390 
391  /* allocate memory */
392  SCIP_CALL( SCIPallocBufferArray(scip, &lhs, nrows) );
393  SCIP_CALL( SCIPallocBufferArray(scip, &rhs, nrows) );
394  SCIP_CALL( SCIPallocBufferArray(scip, &rowind, scipnnonz) );
395  SCIP_CALL( SCIPallocBufferArray(scip, &colind, scipnnonz) );
396  SCIP_CALL( SCIPallocBufferArray(scip, &val, scipnnonz) );
397 
398  /* insert the nonzeroes */
399  nnonz = 0; /* this is recomputed for the sdpi, because of the possible duplication of non-zeroes for lhs and rhs */
400  nconss = 0; /* this will be increased for each finite lhs and rhs */
401 
402  for (i = 0; i < nrows; i++)
403  {
404  SCIP_ROW* row;
405  SCIP_Bool tightened = FALSE;
406  SCIP_Real tightenedval = 0.0;
407  SCIP_Bool swapped = FALSE;
408 
409  row = rows[i];
410  assert( row != 0 );
411  rownnonz = SCIProwGetNNonz(row);
412 
413  rowvals = SCIProwGetVals(row);
414  rowcols = SCIProwGetCols(row);
415  sciplhs = SCIProwGetLhs(row) - SCIProwGetConstant(row);
416  sciprhs = SCIProwGetRhs(row) - SCIProwGetConstant(row);
417 
418  /* check whether we have a variable bound and can strenghten the big-M */
419  if ( tightenvb && rownnonz == 2 && (SCIPisZero(scip, sciplhs) || SCIPisZero(scip, sciprhs) ) )
420  {
421  SCIP_VAR* var1;
422  SCIP_VAR* var2;
423  SCIP_Real val1;
424  SCIP_Real val2;
425 
426  val1 = rowvals[0];
427  val2 = rowvals[1];
428 
429  assert( rowcols[0] != NULL );
430  assert( rowcols[1] != NULL );
431  var1 = SCIPcolGetVar(rowcols[0]);
432  var2 = SCIPcolGetVar(rowcols[1]);
433  assert( var1 != NULL );
434  assert( var2 != NULL );
435 
436  /* check that variables are not locally fixed */
437  if ( ! SCIPisEQ(scip, SCIPvarGetLbLocal(var1), SCIPvarGetUbLocal(var1)) && ! SCIPisEQ(scip, SCIPvarGetLbLocal(var2), SCIPvarGetUbLocal(var2)) )
438  {
439  /* one coefficient must be 1 and the other negative */
440  if ( (SCIPisEQ(scip, val1, 1.0) || SCIPisEQ(scip, val2, 1.0)) && ( SCIPisNegative(scip, val1) || SCIPisNegative(scip, val2) ) )
441  {
442  /* We want x - a z <= 0 or x - a z >= 0, where var1 = x and var2 = z; possibly swap variables otherwise */
443  if ( ! SCIPisEQ(scip, val1, 1.0) || ! SCIPisNegative(scip, val2) )
444  {
445  SCIPswapPointers((void**) &var1, (void**) &var2);
446 
447  val2 = val1;
448  swapped = TRUE;
449  }
450 
451  /* var2 needs to be binary */
452  if ( SCIPvarIsBinary(var2) )
453  {
454  if ( SCIPisZero(scip, sciprhs) )
455  {
456  if ( SCIPisLT(scip, SCIPvarGetUbLocal(var1), REALABS(val2)) )
457  {
458  SCIPdebugMessage("Big-M in %s changed from %f to %f\n", SCIProwGetName(row), REALABS(val2), SCIPvarGetUbLocal(var1));
459 
460  tightened = TRUE;
461  tightenedval = -SCIPvarGetUbLocal(var1); /* negative sign because the coefficient needs to be negative */
462  }
463  }
464 
465  if ( SCIPisZero(scip, sciplhs) )
466  {
467  if ( SCIPisGT(scip, SCIPvarGetLbLocal(var1), REALABS(val2)) )
468  {
469  SCIPdebugMessage("Big-M in %s changed from %f to %f\n", SCIProwGetName(row), REALABS(val2), SCIPvarGetLbLocal(var1));
470 
471  tightened = TRUE;
472  tightenedval = -SCIPvarGetUbLocal(var1); /* negative sign because the coefficient needs to be negative */
473  }
474  }
475  }
476  }
477  }
478  }
479 
480  for (j = 0; j < rownnonz; j++)
481  {
482  /* if the Big-M was tightened, we use the new value (the position where this new value is used is dependant on wheter we needed to swap) */
483  if ( tightened && ( (swapped && (j == 0)) || ((! swapped) && (j == 1)) ) ) /* use the tightened value */
484  {
485  if ( SCIPisFeasGT(scip, REALABS(tightenedval), 0.0) )
486  {
487  assert( SCIPcolGetVar(rowcols[j]) != 0 );
488  colind[nnonz] = SCIPsdpVarmapperGetSdpIndex(varmapper, SCIPcolGetVar(rowcols[j]));
489  rowind[nnonz] = nconss;
490  val[nnonz] = tightenedval;
491  nnonz++;
492  }
493  }
494  else if ( SCIPisFeasGT(scip, REALABS(rowvals[j]), 0.0))
495  {
496  assert( SCIPcolGetVar(rowcols[j]) != 0 );
497  colind[nnonz] = SCIPsdpVarmapperGetSdpIndex(varmapper, SCIPcolGetVar(rowcols[j]));
498  rowind[nnonz] = nconss;
499  val[nnonz] = rowvals[j];
500  nnonz++;
501  }
502  }
503  lhs[nconss] = sciplhs;
504  rhs[nconss] = sciprhs;
505  nconss++;
506  }
507 
508  /* delete the old LP-block from the sdpi */
509  SCIP_CALL( SCIPsdpiGetNLPRows(sdpi, &nrowssdpi) );
510  if ( nrowssdpi > 0 )
511  {
512  SCIP_CALL( SCIPsdpiDelLPRows(sdpi, 0, nrowssdpi - 1) );
513  }
514 
515  /* add the LP-block to the sdpi */
516  SCIP_CALL( SCIPsdpiAddLPRows(sdpi, nconss, lhs, rhs, nnonz, (const int*)rowind, (const int*)colind, val) );
517 
518  /* free the remaining arrays */
519  SCIPfreeBufferArray(scip, &val);
520  SCIPfreeBufferArray(scip, &colind);
521  SCIPfreeBufferArray(scip, &rowind);
522  SCIPfreeBufferArray(scip, &rhs);
523  SCIPfreeBufferArray(scip, &lhs);
524 
525  /* update bounds */
526 
527  /* get the variables */
528  vars = SCIPgetVars(scip);
529  assert( vars != NULL );
530 
531  /* prepare arrays of bounds */
532  SCIP_CALL( SCIPallocBufferArray(scip, &lb, nvars) );
533  SCIP_CALL( SCIPallocBufferArray(scip, &ub, nvars) );
534  SCIP_CALL( SCIPallocBufferArray(scip, &inds, nvars) );
535  SCIP_CALL( SCIPallocBufferArray(scip, &obj, nvars) );
536  SCIP_CALL( SCIPallocBufferArray(scip, &objinds, nvars) );
537 
538  /* get new bounds and objective coefficients */
539  for (i = 0; i < nvars; i++)
540  {
541  assert( vars[i] != NULL );
542  lb[i] = SCIPvarGetLbLocal(vars[i]);
543  ub[i] = SCIPvarGetUbLocal(vars[i]);
544  inds[i] = i; /* we want to change all bounds, so all indices are included in inds */
545  obj[i] = SCIPvarGetObj(vars[i]);
546  objinds[i] = i;
547  }
548 
549  /* inform interface */
550  SCIP_CALL( SCIPsdpiChgBounds(sdpi, nvars, inds, lb, ub) );
551  SCIP_CALL( SCIPsdpiChgObj(sdpi, nvars, objinds, obj) );
552 
553  /* free the bounds-arrays */
554  SCIPfreeBufferArray(scip, &objinds);
555  SCIPfreeBufferArray(scip, &obj);
556  SCIPfreeBufferArray(scip, &inds);
557  SCIPfreeBufferArray(scip, &ub);
558  SCIPfreeBufferArray(scip, &lb);
559 
560  return SCIP_OKAY;
561 }
562 
564 static
565 SCIP_RETCODE calcRelax(
566  SCIP* scip,
567  SCIP_RELAXDATA* relaxdata,
568  SCIP_RESULT* result,
569  SCIP_Real* lowerbound
570  )
571 {
572  char saveconsname[SCIP_MAXSTRLEN];
573  SCIP_SDPSOLVERSETTING startsetting;
574  SCIP_SDPSOLVERSETTING usedsetting;
575  SdpVarmapper* varmapper;
576  SCIP_CONS* savedsetting;
577  SCIP_CONS** conss;
578  SCIP_VAR** vars;
579  SCIP_SDPI* sdpi;
580  SCIP_Bool rootnode;
581  SCIP_Bool enforceslater;
582  SCIP_Real timelimit;
583  SCIP_Real objforscip;
584  SCIP_Real* solforscip;
585  SCIP_Bool allint;
586  SCIP_SDPSLATERSETTING slatersetting;
587  SCIP_SDPSLATER primalslater;
588  SCIP_SDPSLATER dualslater;
589  int naddediters;
590  int naddedsdpcalls;
591  int nvars;
592  int i;
593  int v;
594 
595  SCIPdebugMessage("calcRelax called\n");
596 
597  assert( scip != NULL );
598  assert( relaxdata != NULL );
599  assert( result != NULL );
600  assert( lowerbound != NULL );
601 
602  nvars = SCIPgetNVars(scip);
603  assert( nvars > 0 );
604  vars = SCIPgetVars (scip);
605 
606  sdpi = relaxdata->sdpi;
607  assert( sdpi != NULL );
608  varmapper = relaxdata->varmapper;
609  assert( varmapper != NULL );
610 
611  if ( relaxdata->objlimit )
612  {
613  /* set the objective limit */
614  assert( SCIPgetUpperbound(scip) > -SCIPsdpiInfinity(sdpi) );
615  SCIP_CALL( SCIPsdpiSetRealpar(sdpi, SCIP_SDPPAR_OBJLIMIT, SCIPgetUpperbound(scip)) );
616  }
617 
618  /* if this is the root node and we cannot solve the problem, we want to check for the Slater condition independent from the SCIP parameter */
619  rootnode = ! SCIPnodeGetParent(SCIPgetCurrentNode(scip));
620 
621  /* find settings to use for this relaxation */
622  if ( rootnode || (SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) == relaxdata->settingsresetofs) ||
623  ( relaxdata->settingsresetfreq > 0 && ((SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) - relaxdata->settingsresetofs) % relaxdata->settingsresetfreq == 0)) )
624  {
625  startsetting = SCIP_SDPSOLVERSETTING_UNSOLVED; /* in the root node we have no information, at each multiple of resetfreq we reset */
626  }
627  else
628  {
629  SCIP_CONSHDLR* conshdlr;
630  int lastconsind;
631 
632  /* get constraint handler */
633  conshdlr = SCIPfindConshdlr(scip, "Savedsdpsettings");
634  if ( conshdlr == NULL )
635  {
636  SCIPerrorMessage("Savedsdpsettings constraint handler not found!\n");
637  return SCIP_PLUGINNOTFOUND;
638  }
639 
640  /* get constraints */
641  conss = SCIPconshdlrGetConss(conshdlr);
642  lastconsind = SCIPconshdlrGetNConss(conshdlr) - 1;
643  assert ( conss != NULL );
644  assert ( conss[lastconsind] != NULL ); /* we always use the last information we got (important e.g. in fracdiving) */
645 
646  /* start with the settings of the parentnode */
647  startsetting = SCIPconsSavedsdpsettingsGetSettings(scip, conss[lastconsind]);
648  }
649 
650  /* set time limit */
651  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
652  if ( ! SCIPisInfinity(scip, timelimit) )
653  {
654  timelimit -= SCIPgetSolvingTime(scip);
655  if ( timelimit <= 0.0 )
656  {
657  *result = SCIP_DIDNOTRUN;
658  return SCIP_OKAY;
659  }
660  }
661 
662  /* if no dual bound is known (we are in the root node and not only repropagating), we will have to abort, so we want
663  * to check the Slater condition in this case */
664  enforceslater = SCIPisInfinity(scip, -1 * SCIPnodeGetLowerbound(SCIPgetCurrentNode(scip)));
665 
666  /* solve the problem */
667  SCIP_CALL( SCIPsdpiSolve(sdpi, NULL, startsetting, enforceslater, timelimit) );
668  relaxdata->lastsdpnode = SCIPnodeGetNumber(SCIPgetCurrentNode(scip));
669 
670  /* update calls, iterations and stability numbers */
671  relaxdata->sdpinterfacecalls++;
672  naddedsdpcalls = 0;
673  SCIP_CALL( SCIPsdpiGetSdpCalls(relaxdata->sdpi, &naddedsdpcalls) );
674  relaxdata->sdpcalls += naddedsdpcalls;
675  naddediters = 0;
676  SCIP_CALL( SCIPsdpiGetIterations(relaxdata->sdpi, &naddediters) );
677  relaxdata->sdpiterations += naddediters;
678 
679  usedsetting = SCIP_SDPSOLVERSETTING_UNSOLVED;
680  SCIP_CALL( SCIPsdpiSettingsUsed(relaxdata->sdpi, &usedsetting) );
681 
682  switch( usedsetting )/*lint --e{788}*/
683  {
684  case SCIP_SDPSOLVERSETTING_PENALTY:
685  relaxdata->solvedpenalty++;
686  break;
687  case SCIP_SDPSOLVERSETTING_FAST:
688  relaxdata->solvedfast++;
689  break;
690  case SCIP_SDPSOLVERSETTING_MEDIUM:
691  relaxdata->solvedmedium++;
692  break;
693  case SCIP_SDPSOLVERSETTING_STABLE:
694  relaxdata->solvedstable++;
695  break;
696  case SCIP_SDPSOLVERSETTING_UNSOLVED:
697  relaxdata->unsolved++;
698  break;
699  default:
700  break;
701  }
702  primalslater = SCIP_SDPSLATER_NOINFO;
703  dualslater = SCIP_SDPSLATER_NOINFO;
704  SCIP_CALL( SCIPsdpiSlater(relaxdata->sdpi, &primalslater, &dualslater) );
705  switch( primalslater )/*lint --e{788}*/
706  {
707  case SCIP_SDPSLATER_NOINFO:
708  relaxdata->npslatercheckfailed++;
709  switch( dualslater )/*lint --e{788}*/
710  {
711  case SCIP_SDPSLATER_NOINFO:
712  relaxdata->ndslatercheckfailed++;
713  relaxdata->nslatercheckfailed++;
714  break;
715  case SCIP_SDPSLATER_NOT:
716  relaxdata->ndnoslater++;
717  relaxdata->nnoslater++;
718  break;
719  case SCIP_SDPSLATER_HOLDS:
720  relaxdata->ndslaterholds++;
721  relaxdata->nslatercheckfailed++;
722  break;
723  case SCIP_SDPSLATER_INF:
724  relaxdata->nslaterinfeasible++;
725  break;
726  default:
727  relaxdata->ndslatercheckfailed++;
728  relaxdata->nslatercheckfailed++;
729  break;
730  }
731  break;
732  case SCIP_SDPSLATER_NOT:
733  relaxdata->npnoslater++;
734  switch( dualslater )/*lint --e{788}*/
735  {
736  case SCIP_SDPSLATER_NOINFO:
737  relaxdata->ndslatercheckfailed++;
738  relaxdata->nnoslater++;
739  break;
740  case SCIP_SDPSLATER_NOT:
741  relaxdata->ndnoslater++;
742  relaxdata->nnoslater++;
743  break;
744  case SCIP_SDPSLATER_HOLDS:
745  relaxdata->ndslaterholds++;
746  relaxdata->nnoslater++;
747  break;
748  case SCIP_SDPSLATER_INF:
749  relaxdata->nslaterinfeasible++;
750  break;
751  default:
752  relaxdata->ndslatercheckfailed++;
753  relaxdata->nnoslater++;
754  break;
755  }
756  break;
757  case SCIP_SDPSLATER_HOLDS:
758  relaxdata->npslaterholds++;
759  switch( dualslater )/*lint --e{788}*/
760  {
761  case SCIP_SDPSLATER_NOINFO:
762  relaxdata->ndslatercheckfailed++;
763  relaxdata->nslatercheckfailed++;
764  break;
765  case SCIP_SDPSLATER_NOT:
766  relaxdata->ndnoslater++;
767  relaxdata->nnoslater++;
768  break;
769  case SCIP_SDPSLATER_HOLDS:
770  relaxdata->ndslaterholds++;
771  relaxdata->nslaterholds++;
772  break;
773  case SCIP_SDPSLATER_INF:
774  relaxdata->nslaterinfeasible++;
775  break;
776  default:
777  relaxdata->ndslatercheckfailed++;
778  relaxdata->nslatercheckfailed++;
779  break;
780  }
781  break;
782  default:
783  relaxdata->npslatercheckfailed++;
784  relaxdata->ndslatercheckfailed++;
785  relaxdata->nslatercheckfailed++;
786  break;
787  }
788  slatersetting = SCIP_SDPSLATERSETTING_NOINFO;
789  SCIP_CALL( SCIPsdpiSlaterSettings(relaxdata->sdpi, &slatersetting) );
790  switch( slatersetting )/*lint --e{788}*/
791  {
792  case SCIP_SDPSLATERSETTING_STABLEWSLATER:
793  relaxdata->stablewslater++;
794  break;
795  case SCIP_SDPSLATERSETTING_UNSTABLEWSLATER:
796  relaxdata->unstablewslater++;
797  break;
798  case SCIP_SDPSLATERSETTING_PENALTYWSLATER:
799  relaxdata->penaltywslater++;
800  break;
801  case SCIP_SDPSLATERSETTING_BOUNDEDWSLATER:
802  relaxdata->boundedwslater++;
803  break;
804  case SCIP_SDPSLATERSETTING_UNSOLVEDWSLATER:
805  relaxdata->unsolvedwslater++;
806  break;
807  case SCIP_SDPSLATERSETTING_STABLENOSLATER:
808  relaxdata->stablenoslater++;
809  break;
810  case SCIP_SDPSLATERSETTING_UNSTABLENOSLATER:
811  relaxdata->unstablenoslater++;
812  break;
813  case SCIP_SDPSLATERSETTING_PENALTYNOSLATER:
814  relaxdata->penaltynoslater++;
815  break;
816  case SCIP_SDPSLATERSETTING_BOUNDEDNOSLATER:
817  relaxdata->boundednoslater++;
818  break;
819  case SCIP_SDPSLATERSETTING_UNSOLVEDNOSLATER:
820  relaxdata->unsolvednoslater++;
821  break;
822  case SCIP_SDPSLATERSETTING_STABLEINFEASIBLE:
823  relaxdata->stableinfeasible++;
824  break;
825  case SCIP_SDPSLATERSETTING_UNSTABLEINFEASIBLE:
826  relaxdata->unstableinfeasible++;
827  break;
828  case SCIP_SDPSLATERSETTING_PENALTYINFEASIBLE:
829  relaxdata->penaltyinfeasible++;
830  break;
831  case SCIP_SDPSLATERSETTING_BOUNDEDINFEASIBLE:
832  relaxdata->boundedinfeasible++;
833  break;
834  case SCIP_SDPSLATERSETTING_UNSOLVEDINFEASIBLE:
835  relaxdata->unsolvedinfeasible++;
836  break;
837  default:
838  break;
839  }
840 
841  /* remember settings */
842  (void) SCIPsnprintf(saveconsname, SCIP_MAXSTRLEN, "savedsettings_node_%d", SCIPnodeGetNumber(SCIPgetCurrentNode(scip)));
843  SCIP_CALL( createConsSavedsdpsettings(scip, &savedsetting, saveconsname, usedsetting) );
844  SCIP_CALL( SCIPaddCons(scip, savedsetting) );
845  SCIP_CALL( SCIPreleaseCons(scip, &savedsetting) );
846 
847  if ( ! SCIPsdpiWasSolved(sdpi) )
848  relaxdata->feasible = FALSE;
849 
850  if ( SCIPinProbing(scip) )
851  relaxdata->probingsolved = SCIPsdpiWasSolved(sdpi);
852  else
853  relaxdata->origsolved = SCIPsdpiSolvedOrig(sdpi);
854 
855 
856  if ( SCIPsdpiIsAcceptable(sdpi) )
857  {
858 #ifdef SCIP_MORE_DEBUG /* print the optimal solution */
859  {
860  int sollength;
861  SCIP_CALL( SCIPallocBufferArray(scip, &solforscip, nvars) );
862  sollength = nvars;
863  SCIP_CALL( SCIPsdpiGetSol(sdpi, &objforscip, solforscip, &sollength) ); /* get both the objective and the solution from the SDP solver */
864 
865  assert( sollength == nvars ); /* If this isn't true any longer, the getSol-call was unsuccessfull, because the given array wasn't long enough,
866  * but this can't happen, because the array has enough space for all SDP variables. */
867 
868  if ( SCIPsdpiFeasibilityKnown(sdpi) )
869  {
870  SCIPdebugMessage("optimal solution: objective = %f, dual feasible: %d, primal feasible: %d.\n",
871  objforscip, SCIPsdpiIsDualFeasible(sdpi), SCIPsdpiIsPrimalFeasible(sdpi));
872  }
873  else
874  {
875  SCIPdebugMessage("The solver could not determine feasibility ! ");
876  }
877 
878  /* output solution */
879  for (i = 0; i < nvars; ++i)
880  {
881  SCIPdebugMessage("<%s> = %f\n", SCIPvarGetName(vars[i]), solforscip[i]);
882  }
883  SCIPfreeBufferArray(scip, &solforscip);
884  }
885 #endif
886 
887  if ( SCIPsdpiIsDualInfeasible(sdpi) )
888  {
889  SCIPdebugMessage("Node cut off due to infeasibility.\n");
890  relaxdata->feasible = FALSE;
891  *result = SCIP_CUTOFF;
892  return SCIP_OKAY;
893  }
894  else if ( SCIPsdpiIsObjlimExc(sdpi) )
895  {
896  SCIPdebugMessage("Node cut off due to objective limit.\n");
897  relaxdata->feasible = FALSE;
898  *result = SCIP_CUTOFF;
899  return SCIP_OKAY;
900  }
901  else if ( SCIPsdpiIsDualUnbounded(sdpi) )
902  {
903  SCIPdebugMessage("Node unbounded.");
904  relaxdata->feasible = TRUE;
905  *result = SCIP_SUCCESS;
906  *lowerbound = -SCIPinfinity(scip);
907  return SCIP_OKAY;
908  }
909  else if ( SCIPsdpiIsPrimalFeasible(sdpi) && SCIPsdpiIsDualFeasible(sdpi) )
910  {
911  SCIP_SOL* scipsol;
912  SCIP_COL** cols;
913  SCIP_Bool stored;
914  SCIP_Bool allfeas;
915  int ncols;
916  int slength;
917 
918  /* get solution w.r.t. SCIP variables */
919  SCIP_CALL( SCIPallocBufferArray(scip, &solforscip, nvars) );
920  slength = nvars;
921  SCIP_CALL( SCIPsdpiGetSol(sdpi, &objforscip, solforscip, &slength) ); /* get both the objective and the solution from the SDP solver */
922 
923  assert( slength == nvars ); /* If this isn't true any longer, the getSol-Call was unsuccessfull, because the given array wasn't long enough,
924  * but this can't happen, because the array has enough space for all sdp variables. */
925 
926  /* check if the solution is integral */
927  allint = TRUE;
928  for (v = 0; v < nvars; v++)
929  {
930  if ( SCIPvarIsIntegral(SCIPsdpVarmapperGetSCIPvar(varmapper, v)) && ! SCIPisFeasIntegral(scip, solforscip[v]) )
931  {
932  allint = FALSE;
933  break;
934  }
935  }
936 
937  /* create SCIP solution */
938  SCIP_CALL( SCIPcreateSol(scip, &scipsol, NULL) );
939  SCIP_CALL( SCIPsetSolVals(scip, scipsol, nvars, vars, solforscip) );
940 
941  *lowerbound = objforscip;
942  relaxdata->objval = objforscip;
943 
944  if ( allint ) /* if the solution is integer, we might have found a new best solution for the MISDP */
945  {
946  SCIP_CALL( SCIPcheckSol(scip, scipsol, TRUE, FALSE, FALSE, FALSE, &allfeas) ); /* is this really needed ? */
947  if ( allfeas )
948  {
949  /* if we are not in probing give the solution to SCIP so that we can cut the node off, otherwise let the heuristic do it */
950  if ( ! SCIPinProbing(scip) )
951  {
952  SCIP_CALL( SCIPtrySol(scip, scipsol, TRUE, FALSE, FALSE, FALSE, &stored) );
953  if (stored)
954  {
955  SCIPdebugMessage("feasible solution for MISDP found, cut node off, solution is stored.\n");
956  }
957  else
958  {
959  SCIPdebugMessage("feasible solution for MISDP found, cut node off, solution is worse than earlier one.\n");
960  }
961  }
962 
963  /* set relax sol */
964  SCIP_CALL( SCIPsetRelaxSolVals(scip, nvars, vars, solforscip) );
965  SCIP_CALL( SCIPmarkRelaxSolValid(scip) );
966 
967  SCIPfreeBufferArray(scip, &solforscip);
968  SCIP_CALL( SCIPfreeSol(scip, &scipsol) );
969 
970  relaxdata->feasible = TRUE;
971  *result = SCIP_CUTOFF;
972  return SCIP_OKAY;
973  }
974  SCIPdebugMessage("Found a solution that is feasible for the SDP-solver and integrality, but infeasible for SCIP!\n");
975  }
976 
977  /* copy solution */
978  SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
979  for (i = 0; i < ncols; i++)
980  {
981  SCIP_CALL( SCIPsetRelaxSolVal(scip, SCIPcolGetVar(cols[i]), SCIPgetSolVal(scip, scipsol, SCIPcolGetVar(cols[i]))) );
982  }
983 
984  SCIP_CALL( SCIPmarkRelaxSolValid(scip) );
985  relaxdata->feasible = TRUE;
986  *result = SCIP_SUCCESS;
987 
988  /* if all int and binary vars are integral, nothing else needs to be done */
989  if ( ! allint )
990  {
991  for (i = 0; i < nvars; ++i)
992  {
993  SCIP_VAR* var = vars[i];
994  if ( SCIPvarIsIntegral(var) && ! SCIPisFeasIntegral(scip, solforscip[i]) && ! SCIPisEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) )
995  {
996  /* we don't set a true score, we will just let the branching rule decide */
997  SCIP_CALL( SCIPaddExternBranchCand(scip, var, 10000.0, solforscip[i]) );
998  }
999  }
1000  }
1001 
1002  SCIPfreeBufferArray(scip, &solforscip);
1003  SCIP_CALL( SCIPfreeSol(scip, &scipsol) );
1004  }
1005  }
1006  else
1007  {
1008  SCIP_Real objlb;
1009 
1010  if ( SCIPsdpiIsTimelimExc(relaxdata->sdpi) )
1011  {
1012  *result = SCIP_DIDNOTRUN;
1013  return SCIP_OKAY;
1014  }
1015 
1016  /* if we used the penalty approach, we might have calculated a good lower bound, even if we did not produce a feasible solution, otherwise we
1017  * keep the current bound, if the current bound is -infty, we abort */
1018  objlb = -SCIPinfinity(scip);
1019  SCIP_CALL( SCIPsdpiGetLowerObjbound(relaxdata->sdpi, &objlb) );
1020  if ( ! SCIPisInfinity(scip, objlb) )
1021  {
1022  *lowerbound = objlb;
1023  SCIPdebugMessage("The relaxation could not be solved, using best computed bound from penalty formulation.\n");
1024  }
1025  else if ( ! SCIPisInfinity(scip, -1 * SCIPnodeGetLowerbound(SCIPgetCurrentNode(scip))) )
1026  {
1027  *lowerbound = SCIPnodeGetLowerbound(SCIPgetCurrentNode(scip));
1028  SCIPdebugMessage("The relaxation could not be solved, keeping old bound.\n");
1029  }
1030  else
1031  {
1032  *result = SCIP_SUSPENDED;
1033  SCIPerrorMessage("The relaxation of the root node could not be solved, so there is no hope to solve this instance.\n");
1034  return SCIP_ERROR;
1035  }
1036 
1037  *result = SCIP_SUCCESS;
1038  SCIP_CALL( SCIPupdateLocalLowerbound(scip, *lowerbound) );
1039  return SCIP_OKAY;
1040  }
1041 
1042  return SCIP_OKAY;
1043 }
1044 
1046 static
1047 SCIP_Bool allVarsFixed(
1048  SCIP* scip
1049  )
1050 {
1051  SCIP_VAR** vars;
1052  int i;
1053 
1054  assert( scip != NULL );
1055 
1056  vars = SCIPgetVars(scip);
1057 
1058  /* try to find a variable that is not fixed */
1059  for (i = 0; i < SCIPgetNVars(scip); i++)
1060  {
1061  if ( SCIPisFeasLT(scip, SCIPvarGetLbLocal(vars[i]), SCIPvarGetUbLocal(vars[i])) )
1062  return FALSE;
1063  }
1064 
1065  /* if no variable with lower bound strictly lower than upper bound has been found, all variables are fixed */
1066  return TRUE;
1067 }
1068 
1070 static
1071 SCIP_DECL_RELAXEXEC(relaxExecSdp)
1072 {
1073  SCIP_RELAXDATA* relaxdata;
1074  SCIP_VAR** vars;
1075  SCIP_Real* ubs;
1076  SCIP_Bool cutoff;
1077  SCIP_SOL* scipsol;
1078  SCIP_Bool stored;
1079  int nconss;
1080  int nvars;
1081  int i;
1082 #ifdef SCIP_EVEN_MORE_DEBUG
1083  SCIP_VAR** varsfordebug = SCIPgetVars(scip);
1084  const int nvarsfordebug = SCIPgetNVars(scip);
1085 #endif
1086 
1087  SCIPdebugMessage("Calling relaxExecSdp.\n");
1088 
1089  relaxdata = SCIPrelaxGetData(relax);
1090  vars = SCIPgetVars(scip);
1091  nvars = SCIPgetNVars(scip);
1092 
1093  /* don't run again if we already solved the current node (except during probing), and we solved the correct problem */
1094  if ( (relaxdata->lastsdpnode == SCIPnodeGetNumber(SCIPgetCurrentNode(scip)) && ( ! SCIPinProbing(scip) ) ) && relaxdata->origsolved && ! relaxdata->resolve )
1095  {
1096  SCIP_COL** cols;
1097  SCIP_Real objforscip;
1098  SCIP_Real* solforscip;
1099  int ncols;
1100  int slength;
1101 
1102  SCIPdebugMessage("Already solved SDP-relaxation for node %ld, returning with SCIP_SUCCESS so that no other relaxator is called.\n",
1103  SCIPrelaxGetData(relax)->lastsdpnode);
1104 
1105  if ( SCIPsdpiIsDualUnbounded(relaxdata->sdpi) )
1106  {
1107  relaxdata->feasible = TRUE;
1108  *result = SCIP_SUCCESS;
1109  *lowerbound = -SCIPinfinity(scip);
1110  return SCIP_OKAY;
1111  }
1112 
1113  /* get solution w.r.t. SCIP variables */
1114  SCIP_CALL( SCIPallocBufferArray(scip, &solforscip, nvars) );
1115  slength = nvars;
1116  SCIP_CALL( SCIPsdpiGetSol(relaxdata->sdpi, &objforscip, solforscip, &slength) ); /* get both the objective and the solution from the SDP solver */
1117 
1118  assert( slength == nvars ); /* If this isn't true any longer, the getSol-Call was unsuccessfull, because the given array wasn't long enough,
1119  * but this can't happen, because the array has enough space for all sdp variables. */
1120 
1121  /* create SCIP solution */
1122  SCIP_CALL( SCIPcreateSol(scip, &scipsol, NULL) );
1123  SCIP_CALL( SCIPsetSolVals(scip, scipsol, nvars, vars, solforscip) );
1124 
1125  *lowerbound = objforscip;
1126 
1127  /* copy solution */
1128  SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
1129  for (i = 0; i < ncols; i++)
1130  {
1131  SCIP_CALL( SCIPsetRelaxSolVal(scip, SCIPcolGetVar(cols[i]), SCIPgetSolVal(scip, scipsol, SCIPcolGetVar(cols[i]))) );
1132  }
1133 
1134  SCIP_CALL( SCIPmarkRelaxSolValid(scip) );
1135  *result = SCIP_SUCCESS;
1136 
1137  SCIPfreeBufferArray(scip, &solforscip);
1138  SCIP_CALL( SCIPfreeSol(scip, &scipsol) );
1139 
1140  *result = SCIP_SUCCESS;
1141  return SCIP_OKAY;
1142  }
1143 
1144  /* if we are solving a probing SDP, remember that we didn't solve the original problem */
1145  relaxdata->origsolved = FALSE;
1146 
1147  /* construct the lp and make sure, that everything is where it should be */
1148  SCIP_CALL( SCIPconstructLP(scip, &cutoff) );
1149 
1150  if ( cutoff )
1151  {
1152  relaxdata->feasible = FALSE;
1153  *result = SCIP_CUTOFF;
1154  return SCIP_OKAY;
1155  }
1156 
1157  /* very important to call flushLP */
1158  SCIP_CALL( SCIPflushLP(scip) );
1159 
1160  /* get varmapper */
1161  nconss = SCIPgetNConss(scip);
1162 
1163 #ifdef SCIP_EVEN_MORE_DEBUG
1164  for (i = 0; i < nvarsfordebug; i++)
1165  {
1166  SCIPdebugMessage("variable %s: status = %u, integral = %u, bounds = [%f, %f] \n", SCIPvarGetName(varsfordebug[i]), SCIPvarGetStatus(varsfordebug[i]),
1167  SCIPvarIsIntegral(varsfordebug[i]), SCIPvarGetLbLocal(varsfordebug[i]), SCIPvarGetUbLocal(varsfordebug[i]));
1168  }
1169 #endif
1170 
1171  if ( nconss == 0 )
1172  {
1173  /* if there are no constraints, there is nothing to do */
1174  relaxdata->feasible = TRUE;
1175  *result = SCIP_DIDNOTRUN;
1176  return SCIP_OKAY;
1177  }
1178 
1179  if ( allVarsFixed(scip) )
1180  {
1181  SCIP_Bool feasible;
1182 
1183  /* if all variables, really all, are fixed, we give this fixed solution to SCIP */
1184 
1185  SCIP_CALL( SCIPallocBufferArray(scip, &ubs, nvars) );
1186 
1187  *lowerbound = 0.0;
1188  for (i = 0; i < nvars; i++)
1189  {
1190  ubs[i] = SCIPvarGetUbLocal(vars[i]);
1191  *lowerbound += SCIPvarGetObj(vars[i]) * ubs[i];
1192  assert( SCIPisFeasEQ(scip, SCIPvarGetUbLocal(vars[i]), SCIPvarGetLbLocal(vars[i])));
1193  }
1194  if ( SCIPgetObjsense(scip) == SCIP_OBJSENSE_MAXIMIZE )
1195  *lowerbound *= -1;
1196 
1197  SCIPdebugMessage("EVERYTHING IS FIXED, objective value = %f\n", *lowerbound);
1198 
1199  SCIP_CALL( SCIPcreateSol(scip, &scipsol, NULL) );
1200  SCIP_CALL( SCIPsetSolVals(scip, scipsol, nvars, vars, ubs) );
1201 
1202  /* set the relaxation solution */
1203  for (i = 0; i < nvars; i++)
1204  {
1205  SCIP_CALL( SCIPsetRelaxSolVal(scip, vars[i], SCIPvarGetLbLocal(vars[i])) );
1206  }
1207  SCIP_CALL( SCIPmarkRelaxSolValid(scip) );
1208 
1209  /* check if the solution really is feasible */
1210  SCIP_CALL( SCIPcheckSol(scip, scipsol, FALSE, TRUE, TRUE, TRUE, &feasible) );
1211 
1212  stored = FALSE;
1213  if ( feasible )
1214  {
1215  SCIP_CALL( SCIPtrySolFree(scip, &scipsol, FALSE, FALSE, FALSE, FALSE, &stored) );
1216  }
1217  else
1218  {
1219  SCIP_CALL( SCIPfreeSol(scip, &scipsol) );
1220  }
1221 
1222  relaxdata->feasible = feasible;
1223 
1224  if ( feasible && stored )
1225  {
1226  *result = SCIP_CUTOFF;
1227  SCIPdebugMessage("New solution was stored, node is cut off!\n");
1228  }
1229  else
1230  {
1231  *result = SCIP_CUTOFF;
1232  SCIPdebugMessage("Fixed solution either infeasible or not good enough for storage, node cut off!\n");
1233  }
1234 
1235  SCIPfreeBufferArray(scip, &ubs);
1236 
1237  return SCIP_OKAY;
1238  }
1239 
1240  /* update LP Data in Interface */
1241  SCIP_CALL( putLpDataInInterface(scip, relaxdata->sdpi, relaxdata->varmapper) );
1242 
1243  SCIP_CALL( calcRelax(scip, relaxdata, result, lowerbound));
1244 
1245  return SCIP_OKAY;
1246 }
1247 
1248 
1251 static
1252 SCIP_DECL_RELAXINITSOL(relaxInitSolSdp)
1253 {
1254  SCIP_RELAXDATA* relaxdata;
1255  SCIP_RETCODE retcode;
1256  SCIP_VAR** vars;
1257  SCIP_Real epsilon;
1258  SCIP_Real feastol;
1259  SCIP_Real penaltyparam;
1260  SCIP_Real maxpenaltyparam;
1261  SCIP_Bool sdpinfo;
1262  SCIP_Real givenpenaltyparam;
1263  int slatercheck;
1264  int nvars;
1265 
1266  assert( relax != NULL );
1267 
1268  relaxdata = SCIPrelaxGetData(relax);
1269  assert( relaxdata != NULL );
1270 
1271  relaxdata->objval = 0.0;
1272  relaxdata->origsolved = FALSE;
1273  relaxdata->probingsolved = FALSE;
1274  relaxdata->sdpcalls = 0;
1275  relaxdata->sdpinterfacecalls = 0;
1276  relaxdata->sdpiterations = 0;
1277  relaxdata->solvedfast = 0;
1278  relaxdata->solvedmedium = 0;
1279  relaxdata->solvedstable = 0;
1280  relaxdata->solvedpenalty = 0;
1281  relaxdata->stablewslater = 0;
1282  relaxdata->unstablewslater = 0;
1283  relaxdata->boundedwslater = 0;
1284  relaxdata->unsolvedwslater = 0;
1285  relaxdata->stablenoslater = 0;
1286  relaxdata->unsolvednoslater = 0;
1287  relaxdata->boundednoslater = 0;
1288  relaxdata->unsolvednoslater = 0;
1289  relaxdata->nslaterholds = 0;
1290  relaxdata->nnoslater = 0;
1291  relaxdata->nslatercheckfailed = 0;
1292  relaxdata->npslaterholds = 0;
1293  relaxdata->npnoslater = 0;
1294  relaxdata->npslatercheckfailed = 0;
1295  relaxdata->ndslaterholds = 0;
1296  relaxdata->ndnoslater = 0;
1297  relaxdata->ndslatercheckfailed = 0;
1298  relaxdata->nslaterinfeasible = 0;
1299  relaxdata->stableinfeasible = 0;
1300  relaxdata->unstableinfeasible = 0;
1301  relaxdata->penaltyinfeasible = 0;
1302  relaxdata->boundedinfeasible = 0;
1303  relaxdata->unsolvedinfeasible = 0;
1304  relaxdata->unsolved = 0;
1305  relaxdata->feasible = FALSE;
1306 
1307  nvars = SCIPgetNVars(scip);
1308  vars = SCIPgetVars(scip);
1309 
1310  /* all SCIPvars will be added to this list, and 3/4 seems like a good load factor (java uses this factor) */
1311  SCIP_CALL( SCIPsdpVarmapperCreate(scip, &(relaxdata->varmapper), (int) ceil(1.33 * nvars)) );
1312  SCIP_CALL( SCIPsdpVarmapperAddVars(scip, relaxdata->varmapper, nvars, vars) );
1313 
1314  if ( SCIPgetNVars(scip) > 0 )
1315  {
1316  SCIP_CALL( putSdpDataInInterface(scip, relaxdata->sdpi, relaxdata->varmapper) );
1317  }
1318 
1319  /* set the parameters of the SDP-Solver */
1320  SCIP_CALL( SCIPgetRealParam(scip, "relaxing/SDP/sdpsolverepsilon", &epsilon) );
1321  retcode = SCIPsdpiSetRealpar(relaxdata->sdpi, SCIP_SDPPAR_EPSILON, epsilon);
1322  if ( retcode == SCIP_PARAMETERUNKNOWN )
1323  {
1324  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL,
1325  "SDP Solver <%s>: epsilon setting not available -- SCIP parameter has no effect.\n",
1326  SCIPsdpiGetSolverName());
1327  }
1328  else
1329  {
1330  SCIP_CALL( retcode );
1331  }
1332 
1333  SCIP_CALL( SCIPgetRealParam(scip, "relaxing/SDP/sdpsolverfeastol", &feastol) );
1334  retcode = SCIPsdpiSetRealpar(relaxdata->sdpi, SCIP_SDPPAR_FEASTOL, feastol);
1335  if ( retcode == SCIP_PARAMETERUNKNOWN )
1336  {
1337  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL,
1338  "SDP Solver <%s>: feastol setting not available -- SCIP parameter has no effect.\n",
1339  SCIPsdpiGetSolverName());
1340  }
1341  else
1342  {
1343  SCIP_CALL( retcode );
1344  }
1345 
1346  /* set/compute the starting penalty parameter */
1347  SCIP_CALL( SCIPgetRealParam(scip, "relaxing/SDP/penaltyparam", &penaltyparam) );
1348  if ( SCIPisGE(scip, penaltyparam, 0.0) )
1349  {
1350  retcode = SCIPsdpiSetRealpar(relaxdata->sdpi, SCIP_SDPPAR_PENALTYPARAM, penaltyparam);
1351  givenpenaltyparam = penaltyparam;
1352  if ( retcode == SCIP_PARAMETERUNKNOWN )
1353  {
1354  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL,
1355  "SDP Solver <%s>: penaltyparam setting not available -- SCIP parameter has no effect\n",
1356  SCIPsdpiGetSolverName());
1357  }
1358  else
1359  {
1360  SCIP_CALL( retcode );
1361  }
1362  }
1363  else
1364  {
1365  SCIP_Real maxcoeff;
1366  int v;
1367 
1368  /* compute the maximum coefficient in the objective */
1369  maxcoeff = 0.0;
1370  for (v = 0; v < nvars; v++)
1371  {
1372  if ( SCIPisGT(scip, REALABS(SCIPvarGetObj(vars[v])), maxcoeff) )
1373  maxcoeff = REALABS(SCIPvarGetObj(vars[v]));
1374  }
1375 
1376  SCIP_CALL( SCIPsdpiComputePenaltyparam(relaxdata->sdpi, maxcoeff, &givenpenaltyparam) );
1377  }
1378 
1379  /* set/compute the maximum penalty parameter */
1380  SCIP_CALL( SCIPgetRealParam(scip, "relaxing/SDP/maxpenaltyparam", &maxpenaltyparam) );
1381  if ( SCIPisGE(scip, maxpenaltyparam, 0.0) )
1382  {
1383  retcode = SCIPsdpiSetRealpar(relaxdata->sdpi, SCIP_SDPPAR_MAXPENALTYPARAM, maxpenaltyparam);
1384 
1385  if ( retcode == SCIP_PARAMETERUNKNOWN )
1386  {
1387  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL,
1388  "SDP Solver <%s>: maxpenaltyparam setting not available -- SCIP parameter has no effect.\n",
1389  SCIPsdpiGetSolverName());
1390  }
1391  else
1392  {
1393  SCIP_CALL( retcode );
1394  }
1395 
1396  /* check if the starting value is not bigger than the maximum one, otherwise update it */
1397  if ( SCIPisLT(scip, givenpenaltyparam, maxpenaltyparam) )
1398  {
1399  SCIPdebugMessage("Penalty parameter %f overwritten by maxpenaltyparam %f! \n", givenpenaltyparam, maxpenaltyparam);
1400  SCIP_CALL( SCIPsdpiSetRealpar(relaxdata->sdpi, SCIP_SDPPAR_PENALTYPARAM, maxpenaltyparam) );
1401  }
1402  }
1403  else
1404  {
1405  SCIP_Real givenmaxpenaltyparam;
1406 
1407  SCIP_CALL( SCIPsdpiComputeMaxPenaltyparam(relaxdata->sdpi, givenpenaltyparam, &givenmaxpenaltyparam) );
1408  }
1409 
1410 
1411 
1412  /* set/compute lambda star if SDPA is used as the SDP-Solver */
1413  if ( strcmp(SCIPsdpiGetSolverName(), "SDPA") == 0.0 )
1414  {
1415  SCIP_Real lambdastar;
1416 
1417  SCIP_CALL( SCIPgetRealParam(scip, "relaxing/SDP/lambdastar", &lambdastar) );
1418  if ( SCIPisGE(scip, lambdastar, 0.0) )
1419  {
1420  retcode = SCIPsdpiSetRealpar(relaxdata->sdpi, SCIP_SDPPAR_LAMBDASTAR, lambdastar);
1421  }
1422  else
1423  {
1424  SCIP_Real guess;
1425  SCIP_Real maxguess;
1426  SCIP_CONS** conss;
1427  int nconss;
1428  int c;
1429 
1430  /* iterate over all SDP-constraints to compute the biggest guess for lambdastar */
1431  conss = SCIPgetConss(scip);
1432  nconss = SCIPgetNConss(scip);
1433  maxguess = 0.0;
1434 
1435  for (c = 0; c < nconss; c++)
1436  {
1437  /* only check the SDP constraints */
1438  if ( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(conss[c])), "SDP") == 0 )
1439  {
1440  SCIP_CALL( SCIPconsSdpGuessInitialPoint(scip, conss[c], &guess) );
1441  if ( SCIPisGT(scip, guess, maxguess) )
1442  maxguess = guess;
1443  }
1444  }
1445 
1446  SCIP_CALL( SCIPsdpiComputeLambdastar(relaxdata->sdpi, maxguess) );
1447  }
1448  }
1449 
1450  if ( retcode == SCIP_PARAMETERUNKNOWN )
1451  {
1452  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL,
1453  "SDP Solver <%s>: lambdastar setting not available -- SCIP parameter has no effect.\n",
1454  SCIPsdpiGetSolverName());
1455  }
1456  else
1457  {
1458  SCIP_CALL( retcode );
1459  }
1460 
1461  SCIP_CALL( SCIPgetBoolParam(scip, "relaxing/SDP/sdpinfo", &sdpinfo) );
1462  retcode = SCIPsdpiSetIntpar(relaxdata->sdpi, SCIP_SDPPAR_SDPINFO, (int) sdpinfo);
1463  if ( retcode == SCIP_PARAMETERUNKNOWN )
1464  {
1465  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL,
1466  "SDP Solver <%s>: sdpinfo setting not available -- SCIP parameter has no effect.\n",
1467  SCIPsdpiGetSolverName());
1468  }
1469  else
1470  {
1471  SCIP_CALL( retcode );
1472  }
1473 
1474  SCIP_CALL( SCIPgetIntParam(scip, "relaxing/SDP/slatercheck", &slatercheck) );
1475  retcode = SCIPsdpiSetIntpar(relaxdata->sdpi, SCIP_SDPPAR_SLATERCHECK, slatercheck);
1476  if ( retcode == SCIP_PARAMETERUNKNOWN )
1477  {
1478  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL,
1479  "SDP Solver <%s>: slatercheck setting not available -- SCIP parameter has no effect.\n",
1480  SCIPsdpiGetSolverName());
1481  }
1482  else
1483  {
1484  SCIP_CALL( retcode );
1485  }
1486 
1487  return SCIP_OKAY;
1488 }
1489 
1491 static
1492 SCIP_DECL_RELAXCOPY(relaxCopySdp)
1493 {
1494  assert( scip != NULL );
1495  assert( relax != NULL );
1496  assert(strcmp(SCIPrelaxGetName(relax), RELAX_NAME) == 0);
1497 
1498  SCIP_CALL( SCIPincludeRelaxSdp(scip) );
1499 
1500  return SCIP_OKAY;
1501 }
1502 
1504 static
1505 SCIP_DECL_RELAXEXIT(relaxExitSdp)
1506 {
1507  SCIP_RELAXDATA* relaxdata;
1508 
1509  assert( scip != NULL );
1510  assert( relax != NULL );
1511 
1512  relaxdata = SCIPrelaxGetData(relax);
1513  assert( relaxdata != NULL );
1514 
1515  SCIPdebugMessage("Exiting Relaxation Handler.\n");
1516 
1517  if ( relaxdata->displaystat && SCIPgetSubscipDepth(scip) == 0 )
1518  {
1519  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "\nSDP iterations:\t\t\t\t%6d\n", relaxdata->sdpiterations);
1520  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Average SDP-iterations:\t\t\t%6.2f \n", (SCIP_Real) relaxdata->sdpiterations / (SCIP_Real) relaxdata->sdpcalls );
1521  if ( strcmp(SCIPsdpiGetSolverName(), "SDPA") == 0 )
1522  {
1523  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'fastest settings' solved:\t%6.2f \n", 100.0 * (SCIP_Real) relaxdata->solvedfast / (SCIP_Real) relaxdata->sdpinterfacecalls);
1524  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'medium settings' solved:\t%6.2f \n", 100.0 * (SCIP_Real) relaxdata->solvedmedium / (SCIP_Real) relaxdata->sdpinterfacecalls);
1525  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'stable settings' solved:\t%6.2f \n", 100.0 * (SCIP_Real) relaxdata->solvedstable / (SCIP_Real) relaxdata->sdpinterfacecalls);
1526  }
1527  else
1528  {
1529  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'default formulation' solved:\t%6.2f \n", 100.0 * (SCIP_Real) relaxdata->solvedfast / (SCIP_Real) relaxdata->sdpinterfacecalls);
1530  }
1531  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage penalty formulation used:\t%6.2f \n", 100.0 * (SCIP_Real) relaxdata->solvedpenalty / (SCIP_Real) relaxdata->sdpinterfacecalls);
1532  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage unsolved even with penalty:\t%6.2f \n", 100.0 * (SCIP_Real) relaxdata->unsolved / (SCIP_Real) relaxdata->sdpinterfacecalls);
1533 
1534  if ( relaxdata->slatercheck )
1535  {
1536  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage primal Slater condition held:\t%6.2f \n", 100.0 * (SCIP_Real) relaxdata->npslaterholds / (SCIP_Real) relaxdata->sdpinterfacecalls);
1537  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage primal Slater condition did not hold:\t%6.2f \n", 100.0 * (SCIP_Real) relaxdata->npnoslater / (SCIP_Real) relaxdata->sdpinterfacecalls);
1538  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage primal Slater check failed:\t%6.2f \n", 100.0 * (SCIP_Real) relaxdata->npslatercheckfailed / (SCIP_Real) relaxdata->sdpinterfacecalls);
1539 
1540  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage dual Slater condition held:\t%6.2f \n", 100.0 * (SCIP_Real) relaxdata->ndslaterholds / (SCIP_Real) relaxdata->sdpinterfacecalls);
1541  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage dual Slater condition did not hold:\t%6.2f \n", 100.0 * (SCIP_Real) relaxdata->ndnoslater / (SCIP_Real) relaxdata->sdpinterfacecalls);
1542  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage dual Slater check failed:\t%6.2f \n", 100.0 * (SCIP_Real) relaxdata->ndslatercheckfailed / (SCIP_Real) relaxdata->sdpinterfacecalls);
1543  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage dual Slater check detected infeasibility:\t%6.2f \n", 100.0 * (SCIP_Real) relaxdata->nslaterinfeasible / (SCIP_Real) relaxdata->sdpinterfacecalls);
1544 
1545  if ( relaxdata->nslaterholds )
1546  {
1547  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'fastest settings' with primal and dual slater holding:\t%6.2f \n",
1548  100.0 * (SCIP_Real) relaxdata->stablewslater / (SCIP_Real) relaxdata->nslaterholds);
1549  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'stable settings' with primal and dual slater holding:\t%6.2f \n",
1550  100.0 * (SCIP_Real) relaxdata->unstablewslater / (SCIP_Real) relaxdata->nslaterholds);
1551  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'penalty' with primal and dual slater holding:\t%6.2f \n",
1552  100.0 * (SCIP_Real) relaxdata->penaltywslater / (SCIP_Real) relaxdata->nslaterholds);
1553  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'computed infeasible lower bound' with primal and dual slater holding:\t%6.2f \n",
1554  100.0 * (SCIP_Real) relaxdata->boundedwslater / (SCIP_Real) relaxdata->nslaterholds);
1555  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'unsolved' with primal and dual slater holding:\t%6.2f \n",
1556  100.0 * (SCIP_Real) relaxdata->unsolvedwslater / (SCIP_Real) relaxdata->nslaterholds);
1557  }
1558  if ( relaxdata->nnoslater )
1559  {
1560  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'fastest settings' with either primal or dual slater not holding:\t%6.2f \n",
1561  100.0 * (SCIP_Real) relaxdata->stablenoslater / (SCIP_Real) relaxdata->nnoslater);
1562  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'stable settings' with either primal or dual slater not holding:\t%6.2f \n",
1563  100.0 * (SCIP_Real) relaxdata->unstablenoslater / (SCIP_Real) relaxdata->nnoslater);
1564  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'penalty' with either primal or dual slater not holding:\t%6.2f \n",
1565  100.0 * (SCIP_Real) relaxdata->penaltynoslater / (SCIP_Real) relaxdata->nnoslater);
1566  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'computed infeasible lower bound' with either primal or dual slater not holding:\t%6.2f \n",
1567  100.0 * (SCIP_Real) relaxdata->boundednoslater / (SCIP_Real) relaxdata->nnoslater);
1568  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'unsolved' with either primal or dual slater not holding:\t%6.2f \n",
1569  100.0 * (SCIP_Real) relaxdata->unsolvednoslater / (SCIP_Real) relaxdata->nnoslater);
1570  }
1571  if ( relaxdata->nslaterinfeasible )
1572  {
1573  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'fastest settings' with slater check showing infeasibility:\t%6.2f \n",
1574  100.0 * (SCIP_Real) relaxdata->stableinfeasible / (SCIP_Real) relaxdata->nslaterinfeasible);
1575  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'stable settings' with slater check showing infeasibility:\t%6.2f \n",
1576  100.0 * (SCIP_Real) relaxdata->unstableinfeasible / (SCIP_Real) relaxdata->nslaterinfeasible);
1577  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'penalty' with slater check showing infeasibility:\t%6.2f \n",
1578  100.0 * (SCIP_Real) relaxdata->penaltyinfeasible / (SCIP_Real) relaxdata->nslaterinfeasible);
1579  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'computed infeasible lower bound' with slater check showing infeasibility:\t%6.2f \n",
1580  100.0 * (SCIP_Real) relaxdata->boundedinfeasible / (SCIP_Real) relaxdata->nslaterinfeasible);
1581  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'unsolved' with slater check showing infeasibility:\t%6.2f \n",
1582  100.0 * (SCIP_Real) relaxdata->unsolvedinfeasible / (SCIP_Real) relaxdata->nslaterinfeasible);
1583  }
1584 #ifdef SLATERSOLVED_ABSOLUTE
1585  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of nodes with primal and dual slater holding:\t%d \n", relaxdata->nslaterholds);
1586  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of nodes with 'fastest settings' and primal and dual slater holding:\t%d \n", relaxdata->stablewslater);
1587  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of nodes with 'stable settings' and primal and dual slater holding:\t%d \n", relaxdata->unstablewslater);
1588  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of nodes with 'penalty' and primal and dual slater holding:\t%d \n", relaxdata->penaltywslater);
1589  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of nodes with 'computed infeasible lower bound' and primal and dual slater holding:\t%d \n", relaxdata->boundedwslater);
1590  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of nodes with 'unsolved' and primal and dual slater holding:\t%d \n", relaxdata->unsolvedwslater);
1591 
1592  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of nodes with either primal or dual slater not holding:\t%d \n", relaxdata->nnoslater);
1593  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of nodes with 'fastest settings' and either primal or dual slater not holding:\t%d \n", relaxdata->stablenoslater);
1594  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of nodes with 'stable settings' and either primal or dual slater not holding:\t%d \n", relaxdata->unstablenoslater);
1595  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of nodes with 'penalty' and either primal or dual slater not holding:\t%d \n", relaxdata->penaltynoslater);
1596  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of nodes with 'computed infeasible lower bound' and either primal or dual slater not holding:\t%d \n", relaxdata->boundednoslater);
1597  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of nodes with 'unsolved' and either primal or dual slater not holding:\t%d \n", relaxdata->unsolvednoslater);
1598 
1599  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of infeasible nodes:\t%d \n", relaxdata->nslaterinfeasible);
1600  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of infeasible nodes with 'fastest settings':\t%d \n", relaxdata->stableinfeasible);
1601  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of infeasible nodes with 'stable settings':\t%d \n", relaxdata->unstableinfeasible);
1602  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of infeasible nodes with 'penalty':\t%d \n", relaxdata->penaltyinfeasible);
1603  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of infeasible nodes with 'computed infeasible lower bound':\t%d \n", relaxdata->boundedinfeasible);
1604  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of infeasible nodes with 'unsolved':\t%d \n", relaxdata->unsolvedinfeasible);
1605 #endif
1606  }
1607  }
1608 
1609  if ( relaxdata->varmapper != NULL )
1610  {
1611  SCIP_CALL( SCIPsdpVarmapperFree(scip, &(relaxdata->varmapper)) );
1612  }
1613 
1614  relaxdata->objval = 0.0;
1615  relaxdata->origsolved = FALSE;
1616  relaxdata->probingsolved = FALSE;
1617  relaxdata->feasible = FALSE;
1618  relaxdata->sdpiterations = 0;
1619  relaxdata->sdpcalls = 0;
1620  relaxdata->sdpinterfacecalls = 0;
1621  relaxdata->lastsdpnode = 0;
1622  SCIP_CALL( SCIPsdpiClear(relaxdata->sdpi) );
1623 
1624  return SCIP_OKAY;
1625 }
1626 
1628 static
1629 SCIP_DECL_RELAXFREE(relaxFreeSdp)
1630 {/*lint --e{715}*/
1631  SCIP_RELAXDATA* relaxdata;
1632 
1633  relaxdata = SCIPrelaxGetData(relax);
1634  assert(relaxdata != NULL);
1635 
1636  if ( relaxdata->sdpi != NULL )
1637  {
1638  SCIP_CALL( SCIPsdpiFree(&(relaxdata->sdpi)) );
1639  }
1640 
1641  SCIPfreeMemory(scip, &relaxdata);
1642 
1643  SCIPrelaxSetData(relax, NULL);
1644 
1645  return SCIP_OKAY;
1646 }
1647 
1649 SCIP_RETCODE SCIPincludeRelaxSdp(
1650  SCIP* scip
1651  )
1652 {
1653  SCIP_RELAXDATA* relaxdata = NULL;
1654  SCIP_RELAX* relax;
1655  SCIP_SDPI* sdpi;
1656 
1657  assert( scip != NULL );
1658 
1659  /* create SDP-relaxator data */
1660  SCIP_CALL( SCIPallocMemory(scip, &relaxdata) );
1661  SCIP_CALL( SCIPsdpiCreate(&sdpi, SCIPgetMessagehdlr(scip), SCIPblkmem(scip)) );
1662 
1663  relaxdata->sdpi = sdpi;
1664  relaxdata->lastsdpnode = -1;
1665 
1666  /* include relaxator */
1667  SCIP_CALL( SCIPincludeRelaxBasic(scip, &relax, RELAX_NAME, RELAX_DESC, RELAX_PRIORITY, RELAX_FREQ, relaxExecSdp, relaxdata) );
1668  assert( relax != NULL );
1669 
1670  /* include additional callbacks */
1671  SCIP_CALL( SCIPsetRelaxInitsol(scip, relax, relaxInitSolSdp) );
1672  SCIP_CALL( SCIPsetRelaxExit(scip, relax, relaxExitSdp) );
1673  SCIP_CALL( SCIPsetRelaxFree(scip, relax, relaxFreeSdp) );
1674  SCIP_CALL( SCIPsetRelaxCopy(scip, relax, relaxCopySdp) );
1675 
1676  /* add parameters for SDP-solver */
1677  SCIP_CALL( SCIPaddRealParam(scip, "relaxing/SDP/sdpsolverepsilon",
1678  "the stopping criterion for the duality gap the sdpsolver should use",
1679  &(relaxdata->sdpsolverepsilon), TRUE, DEFAULT_SDPSOLVEREPSILON, 1e-20, 0.001, NULL, NULL) );
1680 
1681  SCIP_CALL( SCIPaddRealParam(scip, "relaxing/SDP/sdpsolverfeastol",
1682  "the feasibility tolerance the SDP solver should use for the SDP constraints",
1683  &(relaxdata->sdpsolverfeastol), TRUE, DEFAULT_SDPSOLVERFEASTOL, 1e-17, 0.001, NULL, NULL) );
1684 
1685  SCIP_CALL( SCIPaddRealParam(scip, "relaxing/SDP/penaltyparam",
1686  "the starting value of the penalty parameter Gamma used for the penalty formulation if the "
1687  "SDP solver didn't converge; set this to a negative value to compute the parameter depending on the given problem", &(relaxdata->penaltyparam),
1688  TRUE, DEFAULT_PENALTYPARAM, -1.0, 1e+20, NULL, NULL) );
1689 
1690  SCIP_CALL( SCIPaddRealParam(scip, "relaxing/SDP/maxpenaltyparam",
1691  "the maximum value of the penalty parameter Gamma used for the penalty formulation if the "
1692  "SDP solver didn't converge; set this to a negative value to compute the parameter depending on the given problem", &(relaxdata->maxpenaltyparam),
1693  TRUE, DEFAULT_MAXPENALTYPARAM, -1.0, 1e+20, NULL, NULL) );
1694 
1695  SCIP_CALL( SCIPaddRealParam(scip, "relaxing/SDP/lambdastar",
1696  "the parameter lambda star used by SDPA to set the initial point , "
1697  "set this to a negative value to compute the parameter depending on the given problem", &(relaxdata->lambdastar),
1698  TRUE, DEFAULT_LAMBDASTAR, -1.0, 1e+20, NULL, NULL) );
1699 
1700  SCIP_CALL( SCIPaddIntParam(scip, "relaxing/SDP/slatercheck",
1701  "Should the Slater condition for the primal and dual problem be checked ahead of solving each SDP? 0: no, 1: yes and output statistics, 2: yes and print warning for "
1702  "every problem not satisfying primal and dual Slater condition", &(relaxdata->slatercheck), TRUE, DEFAULT_SLATERCHECK, 0, 2, NULL, NULL) );
1703 
1704  SCIP_CALL( SCIPaddBoolParam(scip, "relaxing/SDP/sdpinfo",
1705  "Should the SDP solver output information to the screen?",
1706  &(relaxdata->sdpinfo), TRUE, DEFAULT_SDPINFO, NULL, NULL) );
1707 
1708  SCIP_CALL( SCIPaddBoolParam(scip, "relaxing/SDP/objlimit",
1709  "Should an objective limit be given to the SDP-Solver?",
1710  &(relaxdata->objlimit), TRUE, DEFAULT_OBJLIMIT, NULL, NULL) );
1711 
1712  SCIP_CALL( SCIPaddBoolParam(scip, "relaxing/SDP/resolve",
1713  "Should the relaxation be resolved after bound-tightenings were found during propagation (outside of probing)?",
1714  &(relaxdata->resolve), TRUE, DEFAULT_RESOLVE, NULL, NULL) );
1715 
1716  SCIP_CALL( SCIPaddBoolParam(scip, "relaxing/SDP/tightenvb",
1717  "Should Big-Ms in varbound-like constraints be tightened before giving them to the SDP-solver ?",
1718  &(relaxdata->tightenvb), TRUE, DEFAULT_TIGHTENVB, NULL, NULL) );
1719 
1720  SCIP_CALL( SCIPaddBoolParam(scip, "relaxing/SDP/displaystatistics",
1721  "Should statistics about SDP iterations and solver settings/success be printed after quitting SCIP-SDP ?",
1722  &(relaxdata->displaystat), TRUE, DEFAULT_DISPLAYSTAT, NULL, NULL) );
1723 
1724  SCIP_CALL( SCIPaddIntParam(scip, "relaxing/SDP/settingsresetfreq",
1725  "frequency for resetting parameters in SDP solver and trying again with fastest settings (-1: never, 0: only at depth settingsresetofs)",
1726  &(relaxdata->settingsresetfreq), TRUE, DEFAULT_SETTINGSRESETFREQ, -1, INT_MAX, NULL, NULL) );
1727 
1728  SCIP_CALL( SCIPaddIntParam(scip, "relaxing/SDP/settingsresetofs",
1729  "frequency offset for resetting parameters in SDP solver and trying again with fastest settings",
1730  &(relaxdata->settingsresetofs), TRUE, DEFAULT_SETTINGSRESETOFS, 0, INT_MAX, NULL, NULL) );
1731 
1732  /* add description of SDP-solver */
1733  SCIP_CALL( SCIPincludeExternalCodeInformation(scip, SCIPsdpiGetSolverName(), SCIPsdpiGetSolverDesc()) );
1734 
1735  return SCIP_OKAY;
1736 }
1737 
1738 
1739 /* external functions */
1740 
1749 SCIP_RETCODE SCIPrelaxSdpGetPrimalBoundVars(
1750  SCIP_RELAX* relax,
1751  SCIP_Real* lbvars,
1752  SCIP_Real* ubvars,
1753  int* arraylength
1755  )
1756 {
1757  SCIP_RELAXDATA* relaxdata;
1758 
1759  assert( relax != NULL );
1760  assert( lbvars != NULL );
1761  assert( ubvars != NULL );
1762  assert( arraylength != NULL );
1763  assert( *arraylength >= 0 );
1764 
1765  relaxdata = SCIPrelaxGetData(relax);
1766  assert( relaxdata != NULL );
1767 
1768  SCIP_CALL( SCIPsdpiGetPrimalBoundVars(relaxdata->sdpi, lbvars, ubvars, arraylength) );
1769 
1770  return SCIP_OKAY;
1771 }
1772 
1774 SCIP_RETCODE SCIPrelaxSdpRelaxVal(
1775  SCIP_RELAX* relax,
1776  SCIP_Bool* success,
1777  SCIP_Real* objval
1778  )
1779 {
1780  SCIP_RELAXDATA* relaxdata;
1781 
1782  assert( relax != NULL );
1783  assert( success != NULL );
1784  assert( objval != NULL );
1785 
1786  relaxdata = SCIPrelaxGetData(relax);
1787  assert( relaxdata != NULL );
1788 
1789  *success = relaxdata->origsolved;
1790  *objval = relaxdata->objval;
1791 
1792  return SCIP_OKAY;
1793 }
1794 
1796 SCIP_RETCODE SCIPrelaxSdpGetRelaxSol(
1797  SCIP* scip,
1798  SCIP_RELAX* relax,
1799  SCIP_Bool* success,
1800  SCIP_Real* solarray,
1801  int* sollength
1802  )
1803 {
1804  SCIP_RELAXDATA* relaxdata;
1805 
1806  assert( relax != NULL );
1807  assert( success != NULL );
1808  assert( solarray != NULL );
1809 
1810  relaxdata = SCIPrelaxGetData(relax);
1811  assert( relaxdata != NULL );
1812 
1813  *success = relaxdata->origsolved;
1814 
1815  if ( *sollength >= SCIPgetNVars(scip) )
1816  {
1817  SCIP_CALL( SCIPsdpiGetSol(relaxdata->sdpi, NULL, solarray, sollength) );
1818  }
1819  else
1820  {
1821  SCIPdebugMessage("Called SCIPrelaxSdpGetRelaxSol with an array that wasn't big enough, needed length %d, given %d!\n", SCIPgetNVars(scip), *sollength);
1822  *sollength = SCIPgetNVars(scip);
1823  }
1824 
1825  return SCIP_OKAY;
1826 }
1827 
1829 long int SCIPrelaxSdpGetSdpNode(
1830  SCIP_RELAX* relax
1831  )
1832 {
1833  assert( relax != NULL );
1834  assert( SCIPrelaxGetData(relax) != NULL );
1835 
1836  return SCIPrelaxGetData(relax)->lastsdpnode;
1837 }
1838 
1840 SCIP_Bool SCIPrelaxSdpSolvedOrig(
1841  SCIP_RELAX* relax
1842  )
1843 {
1844  SCIP_RELAXDATA* relaxdata;
1845 
1846  assert( relax != NULL );
1847 
1848  relaxdata = SCIPrelaxGetData(relax);
1849 
1850  assert( relaxdata != NULL );
1851  assert( relaxdata->sdpi != NULL );
1852 
1853  return relaxdata->origsolved && SCIPsdpiSolvedOrig(relaxdata->sdpi);
1854 }
1855 
1857 SCIP_Bool SCIPrelaxSdpSolvedProbing(
1858  SCIP_RELAX* relax
1859  )
1860 {
1861  SCIP_RELAXDATA* relaxdata;
1862 
1863  assert( relax != NULL );
1864 
1865  relaxdata = SCIPrelaxGetData(relax);
1866 
1867  assert( relaxdata != NULL );
1868  assert( relaxdata->sdpi != NULL );
1869 
1870  return relaxdata->probingsolved;
1871 }
1872 
1874 SCIP_Bool SCIPrelaxSdpIsFeasible(
1875  SCIP_RELAX* relax
1876  )
1877 {
1878  assert( relax != NULL );
1879  assert( SCIPrelaxGetData(relax) != NULL );
1880 
1881  return ( SCIPrelaxGetData(relax)->feasible );
1882 }
1883 
1885 int SCIPrelaxSdpGetNIterations(
1886  SCIP_RELAX* relax
1887  )
1888 {
1889  assert( relax != NULL );
1890  assert( SCIPrelaxGetData(relax) != NULL );
1891 
1892  return SCIPrelaxGetData(relax)->sdpiterations;
1893 }
1894 
1896 int SCIPrelaxSdpGetNSdpCalls(
1897  SCIP_RELAX* relax
1898  )
1899 {
1900  assert( relax != NULL );
1901  assert( SCIPrelaxGetData(relax) != NULL );
1902 
1903  return ( SCIPrelaxGetData(relax)->sdpcalls );
1904 }
1905 
1907 int SCIPrelaxSdpGetNSdpFast(
1908  SCIP_RELAX* relax
1909  )
1910 {
1911  assert( relax != NULL );
1912  assert( SCIPrelaxGetData(relax) != NULL );
1913 
1914  return ( SCIPrelaxGetData(relax)->solvedfast );
1915 }
1916 
1918 int SCIPrelaxSdpGetNSdpMedium(
1919  SCIP_RELAX* relax
1920  )
1921 {
1922  assert( relax != NULL );
1923  assert( SCIPrelaxGetData(relax) != NULL );
1924 
1925  return ( SCIPrelaxGetData(relax)->solvedmedium );
1926 }
1927 
1929 int SCIPrelaxSdpGetNSdpStable(
1930  SCIP_RELAX* relax
1931  )
1932 {
1933  assert( relax != NULL );
1934  assert( SCIPrelaxGetData(relax) != NULL );
1935 
1936  return ( SCIPrelaxGetData(relax)->solvedstable );
1937 }
1938 
1940 int SCIPrelaxSdpGetNSdpPenalty(
1941  SCIP_RELAX* relax
1942  )
1943 {
1944  assert( relax != NULL );
1945  assert( SCIPrelaxGetData(relax) != NULL );
1946 
1947  return ( SCIPrelaxGetData(relax)->solvedpenalty );
1948 }
1949 
1951 int SCIPrelaxSdpGetNSdpUnsolved(
1952  SCIP_RELAX* relax
1953  )
1954 {
1955  assert( relax != NULL );
1956  assert( SCIPrelaxGetData(relax) != NULL );
1957 
1958  return ( SCIPrelaxGetData(relax)->unsolved );
1959 }
RELAX_DESC
#define RELAX_DESC
Definition: relax_sdp.c:60
SCIPsdpiFree
SCIP_RETCODE SCIPsdpiFree(SCIP_SDPI **sdpi)
Definition: sdpi.c:1454
SCIP_SDPSOLVERSETTING_MEDIUM
Definition: type_sdpi.h:71
SCIPsdpiIsDualUnbounded
SCIP_Bool SCIPsdpiIsDualUnbounded(SCIP_SDPI *sdpi)
Definition: sdpi.c:2886
SCIPsdpiDelLPRows
SCIP_RETCODE SCIPsdpiDelLPRows(SCIP_SDPI *sdpi, int firstrow, int lastrow)
Definition: sdpi.c:1923
SCIP_SDPSOLVERSETTING_UNSOLVED
Definition: type_sdpi.h:68
SCIPsdpiGetSdpCalls
SCIP_RETCODE SCIPsdpiGetSdpCalls(SCIP_SDPI *sdpi, int *calls)
Definition: sdpi.c:3314
calcRelax
static SCIP_RETCODE calcRelax(SCIP *scip, SCIP_RELAXDATA *relaxdata, SCIP_RESULT *result, SCIP_Real *lowerbound)
Definition: relax_sdp.c:565
SCIP_DECL_RELAXCOPY
static SCIP_DECL_RELAXCOPY(relaxCopySdp)
Definition: relax_sdp.c:1492
SCIPsdpVarmapperAddVars
SCIP_RETCODE SCIPsdpVarmapperAddVars(SCIP *scip, SdpVarmapper *varmapper, int nvars, SCIP_VAR **vars)
Definition: SdpVarmapper.c:113
allVarsFixed
static SCIP_Bool allVarsFixed(SCIP *scip)
Definition: relax_sdp.c:1047
SCIP_SDPPAR_EPSILON
Definition: type_sdpi.h:53
DEFAULT_SLATERCHECK
#define DEFAULT_SLATERCHECK
Definition: relax_sdp.c:71
SCIPrelaxSdpGetNSdpPenalty
int SCIPrelaxSdpGetNSdpPenalty(SCIP_RELAX *relax)
Definition: relax_sdp.c:1940
SCIP_SDPSOLVERSETTING
enum SCIP_SDPSolverSetting SCIP_SDPSOLVERSETTING
Definition: type_sdpi.h:74
SCIP_DECL_RELAXEXIT
static SCIP_DECL_RELAXEXIT(relaxExitSdp)
Definition: relax_sdp.c:1505
DEFAULT_SDPSOLVERFEASTOL
#define DEFAULT_SDPSOLVERFEASTOL
Definition: relax_sdp.c:67
SCIP_SDPSLATERSETTING_PENALTYWSLATER
Definition: type_sdpi.h:82
SCIP_SDPSLATER_INF
Definition: type_sdpi.h:101
SCIPsdpiGetSolverName
const char * SCIPsdpiGetSolverName(void)
Definition: sdpi.c:1351
SCIP_SDPSOLVERSETTING_FAST
Definition: type_sdpi.h:70
SCIP_SDPPAR_MAXPENALTYPARAM
Definition: type_sdpi.h:60
SCIPsdpiGetSol
SCIP_RETCODE SCIPsdpiGetSol(SCIP_SDPI *sdpi, SCIP_Real *objval, SCIP_Real *dualsol, int *dualsollength)
Definition: sdpi.c:3214
SCIP_SDPSLATERSETTING_PENALTYINFEASIBLE
Definition: type_sdpi.h:92
SCIP_SDPSLATERSETTING_STABLEWSLATER
Definition: type_sdpi.h:80
relax_sdp.h
SDP-relaxator.
SCIP_SDPSLATERSETTING_UNSOLVEDWSLATER
Definition: type_sdpi.h:84
SCIP_SDPPAR_SLATERCHECK
Definition: type_sdpi.h:58
RELAX_PRIORITY
#define RELAX_PRIORITY
Definition: relax_sdp.c:61
SCIP_SDPSOLVERSETTING_PENALTY
Definition: type_sdpi.h:69
SCIPrelaxSdpGetNSdpUnsolved
int SCIPrelaxSdpGetNSdpUnsolved(SCIP_RELAX *relax)
Definition: relax_sdp.c:1951
DEFAULT_PENALTYPARAM
#define DEFAULT_PENALTYPARAM
Definition: relax_sdp.c:68
SCIPsdpiFeasibilityKnown
SCIP_Bool SCIPsdpiFeasibilityKnown(SCIP_SDPI *sdpi)
Definition: sdpi.c:2774
SCIPsdpiLoadSDP
SCIP_RETCODE SCIPsdpiLoadSDP(SCIP_SDPI *sdpi, int nvars, SCIP_Real *obj, SCIP_Real *lb, SCIP_Real *ub, int nsdpblocks, int *sdpblocksizes, int *sdpnblockvars, int sdpconstnnonz, int *sdpconstnblocknonz, int **sdpconstrow, int **sdpconstcol, SCIP_Real **sdpconstval, int sdpnnonz, int **sdpnblockvarnonz, int **sdpvar, int ***sdprow, int ***sdpcol, SCIP_Real ***sdpval, int nlpcons, SCIP_Real *lplhs, SCIP_Real *lprhs, int lpnnonz, int *lprow, int *lpcol, SCIP_Real *lpval)
Definition: sdpi.c:1638
SCIPsdpiComputeLambdastar
SCIP_RETCODE SCIPsdpiComputeLambdastar(SCIP_SDPI *sdpi, SCIP_Real maxguess)
Definition: sdpi.c:3894
createConsSavedsdpsettings
SCIP_RETCODE createConsSavedsdpsettings(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_SDPSOLVERSETTING settings)
Definition: cons_savedsdpsettings.c:200
DEFAULT_TIGHTENVB
#define DEFAULT_TIGHTENVB
Definition: relax_sdp.c:74
SCIP_DECL_RELAXEXEC
static SCIP_DECL_RELAXEXEC(relaxExecSdp)
Definition: relax_sdp.c:1071
SCIPsdpVarmapperGetSCIPvar
SCIP_VAR * SCIPsdpVarmapperGetSCIPvar(SdpVarmapper *varmapper, int ind)
Definition: SdpVarmapper.c:242
SCIP_SDPSLATERSETTING_BOUNDEDWSLATER
Definition: type_sdpi.h:83
SCIPsdpiGetIterations
SCIP_RETCODE SCIPsdpiGetIterations(SCIP_SDPI *sdpi, int *iterations)
Definition: sdpi.c:3300
DEFAULT_SETTINGSRESETFREQ
#define DEFAULT_SETTINGSRESETFREQ
Definition: relax_sdp.c:77
SCIPsdpiSettingsUsed
SCIP_RETCODE SCIPsdpiSettingsUsed(SCIP_SDPI *sdpi, SCIP_SDPSOLVERSETTING *usedsetting)
Definition: sdpi.c:3328
SCIP_SDPSLATER_NOINFO
Definition: type_sdpi.h:102
SCIPsdpiSlaterSettings
SCIP_RETCODE SCIPsdpiSlaterSettings(SCIP_SDPI *sdpi, SCIP_SDPSLATERSETTING *slatersetting)
Definition: sdpi.c:3365
SCIP_SDPSLATERSETTING_BOUNDEDNOSLATER
Definition: type_sdpi.h:88
SCIPsdpiIsAcceptable
SCIP_Bool SCIPsdpiIsAcceptable(SCIP_SDPI *sdpi)
Definition: sdpi.c:3104
SCIP_DECL_RELAXINITSOL
static SCIP_DECL_RELAXINITSOL(relaxInitSolSdp)
Definition: relax_sdp.c:1252
SCIPrelaxSdpGetNSdpStable
int SCIPrelaxSdpGetNSdpStable(SCIP_RELAX *relax)
Definition: relax_sdp.c:1929
SCIPrelaxSdpGetNSdpMedium
int SCIPrelaxSdpGetNSdpMedium(SCIP_RELAX *relax)
Definition: relax_sdp.c:1918
SCIPsdpVarmapperCreate
SCIP_RETCODE SCIPsdpVarmapperCreate(SCIP *scip, SdpVarmapper **varmapper, int size)
Definition: SdpVarmapper.c:58
SCIPsdpiIsTimelimExc
SCIP_Bool SCIPsdpiIsTimelimExc(SCIP_SDPI *sdpi)
Definition: sdpi.c:3020
SCIPrelaxSdpRelaxVal
SCIP_RETCODE SCIPrelaxSdpRelaxVal(SCIP_RELAX *relax, SCIP_Bool *success, SCIP_Real *objval)
Definition: relax_sdp.c:1774
SCIPsdpiIsDualInfeasible
SCIP_Bool SCIPsdpiIsDualInfeasible(SCIP_SDPI *sdpi)
Definition: sdpi.c:2909
sdpi.h
General interface methods for SDP-preprocessing (mainly fixing variables and removing empty rows/cols...
SCIP_DECL_RELAXFREE
static SCIP_DECL_RELAXFREE(relaxFreeSdp)
Definition: relax_sdp.c:1629
SdpVarmapper
struct Sdpvarmapper SdpVarmapper
Definition: SdpVarmapper.h:48
SCIP_SDPPAR_PENALTYPARAM
Definition: type_sdpi.h:59
SCIP_SDPSLATERSETTING
enum SCIP_SDPSlaterSetting SCIP_SDPSLATERSETTING
Definition: type_sdpi.h:96
SCIP_SDPSLATERSETTING_PENALTYNOSLATER
Definition: type_sdpi.h:87
DEFAULT_DISPLAYSTAT
#define DEFAULT_DISPLAYSTAT
Definition: relax_sdp.c:76
SCIPsdpVarmapperGetSdpIndex
int SCIPsdpVarmapperGetSdpIndex(SdpVarmapper *varmapper, SCIP_VAR *var)
Definition: SdpVarmapper.c:230
putLpDataInInterface
static SCIP_RETCODE putLpDataInInterface(SCIP *scip, SCIP_SDPI *sdpi, SdpVarmapper *varmapper)
Definition: relax_sdp.c:338
SCIPsdpiChgBounds
SCIP_RETCODE SCIPsdpiChgBounds(SCIP_SDPI *sdpi, int nvars, const int *ind, const SCIP_Real *lb, const SCIP_Real *ub)
Definition: sdpi.c:2120
SCIPrelaxSdpGetNSdpCalls
int SCIPrelaxSdpGetNSdpCalls(SCIP_RELAX *relax)
Definition: relax_sdp.c:1896
cons_sdp.h
Constraint handler for SDP-constraints.
SCIPsdpiGetLowerObjbound
SCIP_RETCODE SCIPsdpiGetLowerObjbound(SCIP_SDPI *sdpi, SCIP_Real *objlb)
Definition: sdpi.c:3165
SCIPsdpiIsObjlimExc
SCIP_Bool SCIPsdpiIsObjlimExc(SCIP_SDPI *sdpi)
Definition: sdpi.c:2976
SdpVarmapper.h
class that maps SCIP variables to SDP indices (the SCIP variables are given SDP indices in the order ...
DEFAULT_MAXPENALTYPARAM
#define DEFAULT_MAXPENALTYPARAM
Definition: relax_sdp.c:70
SCIPsdpiCreate
SCIP_RETCODE SCIPsdpiCreate(SCIP_SDPI **sdpi, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem)
Definition: sdpi.c:1390
SCIP_SDPPAR_OBJLIMIT
Definition: type_sdpi.h:55
SCIP_SDPSLATERSETTING_BOUNDEDINFEASIBLE
Definition: type_sdpi.h:93
SCIPconsSdpGetData
SCIP_RETCODE SCIPconsSdpGetData(SCIP *scip, SCIP_CONS *cons, int *nvars, int *nnonz, int *blocksize, int *arraylength, int *nvarnonz, int **col, int **row, SCIP_Real **val, SCIP_VAR **vars, int *constnnonz, int *constcol, int *constrow, SCIP_Real *constval)
Definition: cons_sdp.c:2319
DEFAULT_SDPINFO
#define DEFAULT_SDPINFO
Definition: relax_sdp.c:75
SCIPsdpiAddLPRows
SCIP_RETCODE SCIPsdpiAddLPRows(SCIP_SDPI *sdpi, int nrows, const SCIP_Real *lhs, const SCIP_Real *rhs, int nnonz, const int *row, const int *col, const SCIP_Real *val)
Definition: sdpi.c:1858
DEFAULT_OBJLIMIT
#define DEFAULT_OBJLIMIT
Definition: relax_sdp.c:72
SCIPsdpiGetSolverDesc
const char * SCIPsdpiGetSolverDesc(void)
Definition: sdpi.c:1359
SCIPsdpiComputePenaltyparam
SCIP_RETCODE SCIPsdpiComputePenaltyparam(SCIP_SDPI *sdpi, SCIP_Real maxcoeff, SCIP_Real *penaltyparam)
Definition: sdpi.c:3903
SCIPsdpiSetIntpar
SCIP_RETCODE SCIPsdpiSetIntpar(SCIP_SDPI *sdpi, SCIP_SDPPARAM type, int ival)
Definition: sdpi.c:3857
SCIPconsSavedsdpsettingsGetSettings
SCIP_SDPSOLVERSETTING SCIPconsSavedsdpsettingsGetSettings(SCIP *scip, SCIP_CONS *cons)
Definition: cons_savedsdpsettings.c:235
DEFAULT_SETTINGSRESETOFS
#define DEFAULT_SETTINGSRESETOFS
Definition: relax_sdp.c:78
SCIPrelaxSdpSolvedProbing
SCIP_Bool SCIPrelaxSdpSolvedProbing(SCIP_RELAX *relax)
Definition: relax_sdp.c:1857
SCIPsdpiInfinity
SCIP_Real SCIPsdpiInfinity(SCIP_SDPI *sdpi)
Definition: sdpi.c:3714
SCIPsdpiSolve
SCIP_RETCODE SCIPsdpiSolve(SCIP_SDPI *sdpi, SCIP_Real *start, SCIP_SDPSOLVERSETTING startsettings, SCIP_Bool enforceslatercheck, SCIP_Real timelimit)
Definition: sdpi.c:2388
RELAX_FREQ
#define RELAX_FREQ
Definition: relax_sdp.c:62
SCIPrelaxSdpGetSdpNode
long int SCIPrelaxSdpGetSdpNode(SCIP_RELAX *relax)
Definition: relax_sdp.c:1829
SCIPrelaxSdpGetNSdpFast
int SCIPrelaxSdpGetNSdpFast(SCIP_RELAX *relax)
Definition: relax_sdp.c:1907
SCIPrelaxSdpSolvedOrig
SCIP_Bool SCIPrelaxSdpSolvedOrig(SCIP_RELAX *relax)
Definition: relax_sdp.c:1840
SCIP_SDPPAR_SDPINFO
Definition: type_sdpi.h:57
SCIP_SDPSLATERSETTING_NOINFO
Definition: type_sdpi.h:79
SCIP_SDPPAR_LAMBDASTAR
Definition: type_sdpi.h:61
putSdpDataInInterface
static SCIP_RETCODE putSdpDataInInterface(SCIP *scip, SCIP_SDPI *sdpi, SdpVarmapper *varmapper)
Definition: relax_sdp.c:145
SCIPsdpiWasSolved
SCIP_Bool SCIPsdpiWasSolved(SCIP_SDPI *sdpi)
Definition: sdpi.c:2752
SCIPrelaxSdpGetNIterations
int SCIPrelaxSdpGetNIterations(SCIP_RELAX *relax)
Definition: relax_sdp.c:1885
SCIPsdpiComputeMaxPenaltyparam
SCIP_RETCODE SCIPsdpiComputeMaxPenaltyparam(SCIP_SDPI *sdpi, SCIP_Real penaltyparam, SCIP_Real *maxpenaltyparam)
Definition: sdpi.c:3917
SCIP_SDPSOLVERSETTING_STABLE
Definition: type_sdpi.h:72
SCIPsdpiClear
SCIP_RETCODE SCIPsdpiClear(SCIP_SDPI *sdpi)
Definition: sdpi.c:2075
SCIP_SDPPAR_FEASTOL
Definition: type_sdpi.h:54
SCIPsdpiChgObj
SCIP_RETCODE SCIPsdpiChgObj(SCIP_SDPI *sdpi, int nvars, const int *ind, const SCIP_Real *obj)
Definition: sdpi.c:2091
SCIPrelaxSdpGetRelaxSol
SCIP_RETCODE SCIPrelaxSdpGetRelaxSol(SCIP *scip, SCIP_RELAX *relax, SCIP_Bool *success, SCIP_Real *solarray, int *sollength)
Definition: relax_sdp.c:1796
SCIPsdpVarmapperFree
SCIP_RETCODE SCIPsdpVarmapperFree(SCIP *scip, SdpVarmapper **varmapper)
Definition: SdpVarmapper.c:85
SCIPrelaxSdpGetPrimalBoundVars
SCIP_RETCODE SCIPrelaxSdpGetPrimalBoundVars(SCIP_RELAX *relax, SCIP_Real *lbvars, SCIP_Real *ubvars, int *arraylength)
Definition: relax_sdp.c:1749
DEFAULT_LAMBDASTAR
#define DEFAULT_LAMBDASTAR
Definition: relax_sdp.c:69
SCIP_SDPSLATERSETTING_STABLENOSLATER
Definition: type_sdpi.h:85
SCIP_SDPSLATERSETTING_UNSTABLENOSLATER
Definition: type_sdpi.h:86
SCIPsdpiIsDualFeasible
SCIP_Bool SCIPsdpiIsDualFeasible(SCIP_SDPI *sdpi)
Definition: sdpi.c:2932
SCIP_SDPI
struct SCIP_SDPi SCIP_SDPI
Definition: type_sdpi.h:108
SCIPsdpiIsPrimalFeasible
SCIP_Bool SCIPsdpiIsPrimalFeasible(SCIP_SDPI *sdpi)
Definition: sdpi.c:2863
SCIP_SDPSLATERSETTING_UNSOLVEDNOSLATER
Definition: type_sdpi.h:89
SCIPrelaxSdpIsFeasible
SCIP_Bool SCIPrelaxSdpIsFeasible(SCIP_RELAX *relax)
Definition: relax_sdp.c:1874
SCIPsdpiSetRealpar
SCIP_RETCODE SCIPsdpiSetRealpar(SCIP_SDPI *sdpi, SCIP_SDPPARAM type, SCIP_Real dval)
Definition: sdpi.c:3781
SCIP_SDPSLATERSETTING_UNSOLVEDINFEASIBLE
Definition: type_sdpi.h:94
SCIP_SDPSLATER
enum SCIP_SDPSlater SCIP_SDPSLATER
Definition: type_sdpi.h:106
SCIP_SDPSLATERSETTING_UNSTABLEINFEASIBLE
Definition: type_sdpi.h:91
RELAX_NAME
#define RELAX_NAME
Definition: relax_sdp.c:59
SCIPconsSdpGetNNonz
SCIP_RETCODE SCIPconsSdpGetNNonz(SCIP *scip, SCIP_CONS *cons, int *nnonz, int *constnnonz)
Definition: cons_sdp.c:2415
SCIP_SDPSLATERSETTING_STABLEINFEASIBLE
Definition: type_sdpi.h:90
SCIP_SDPSLATER_NOT
Definition: type_sdpi.h:103
SCIP_SDPSLATERSETTING_UNSTABLEWSLATER
Definition: type_sdpi.h:81
SCIP_SDPSLATER_HOLDS
Definition: type_sdpi.h:104
DEFAULT_RESOLVE
#define DEFAULT_RESOLVE
Definition: relax_sdp.c:73
SCIPsdpiGetNLPRows
SCIP_RETCODE SCIPsdpiGetNLPRows(SCIP_SDPI *sdpi, int *nlprows)
Definition: sdpi.c:2198
SCIPsdpiGetPrimalBoundVars
SCIP_RETCODE SCIPsdpiGetPrimalBoundVars(SCIP_SDPI *sdpi, SCIP_Real *lbvars, SCIP_Real *ubvars, int *arraylength)
Definition: sdpi.c:3268
SCIPconsSdpGuessInitialPoint
SCIP_RETCODE SCIPconsSdpGuessInitialPoint(SCIP *scip, SCIP_CONS *cons, SCIP_Real *lambdastar)
Definition: cons_sdp.c:2548
SCIPsdpiSolvedOrig
SCIP_Bool SCIPsdpiSolvedOrig(SCIP_SDPI *sdpi)
Definition: sdpi.c:2762
SCIPsdpiSlater
SCIP_RETCODE SCIPsdpiSlater(SCIP_SDPI *sdpi, SCIP_SDPSLATER *primalslater, SCIP_SDPSLATER *dualslater)
Definition: sdpi.c:3670
DEFAULT_SDPSOLVEREPSILON
#define DEFAULT_SDPSOLVEREPSILON
Definition: relax_sdp.c:66
SCIPincludeRelaxSdp
SCIP_RETCODE SCIPincludeRelaxSdp(SCIP *scip)
Definition: relax_sdp.c:1649
cons_savedsdpsettings.h
constraint handler for saving SDP settings
Generated on Tue May 24 2016 11:23:37 for SCIP-SDP by   doxygen 1.8.6