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