SCIP-SDP  3.0.1
 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  (strcmp(SCIPsdpiGetSolverName(), "DSDP") == 0) || (strstr(SCIPsdpiGetSolverName(), "Mosek") != NULL))
621  {
622  startsetting = SCIP_SDPSOLVERSETTING_UNSOLVED; /* in the root node we have no information, at each multiple of resetfreq we reset */
623  }
624  else
625  {
626  SCIP_CONSHDLR* conshdlr;
627  int parentconsind;
628 
629  /* get constraint handler */
630  conshdlr = SCIPfindConshdlr(scip, "Savedsdpsettings");
631  if ( conshdlr == NULL )
632  {
633  SCIPerrorMessage("Savedsdpsettings constraint handler not found!\n");
634  return SCIP_PLUGINNOTFOUND;
635  }
636 
637  /* get startsettings of parent node, usually it will be the last active constraint of the corresponding constraint handler, so we iterate from
638  * the end of the list until we find the correct one */
639  conss = SCIPconshdlrGetConss(conshdlr);
640  parentconsind = SCIPconshdlrGetNActiveConss(conshdlr) - 1;
641  (void) SCIPsnprintf(saveconsname, SCIP_MAXSTRLEN, "savedsettings_node_%d", SCIPnodeGetNumber(SCIPnodeGetParent(SCIPgetCurrentNode(scip))));
642 
643  while ( parentconsind >= 0 && strcmp(saveconsname, SCIPconsGetName(conss[parentconsind])) )
644  parentconsind--;
645  if ( parentconsind >= 0 )
646  startsetting = SCIPconsSavedsdpsettingsGetSettings(scip, conss[parentconsind]);
647  else
648  {
649  SCIPdebugMessage("Startsetting from parent node not found, restarting with fastest settings!\n");
650  startsetting = SCIP_SDPSOLVERSETTING_UNSOLVED;
651  }
652 
653  }
654 
655  /* set time limit */
656  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
657  if ( ! SCIPisInfinity(scip, timelimit) )
658  {
659  timelimit -= SCIPgetSolvingTime(scip);
660  if ( timelimit <= 0.0 )
661  {
662  *result = SCIP_DIDNOTRUN;
663  return SCIP_OKAY;
664  }
665  }
666 
667  /* if no dual bound is known (we are in the root node and not only repropagating), we will have to abort, so we want
668  * to check the Slater condition in this case */
669  enforceslater = SCIPisInfinity(scip, -1 * SCIPnodeGetLowerbound(SCIPgetCurrentNode(scip)));
670 
671  /* solve the problem */
672  SCIP_CALL( SCIPsdpiSolve(sdpi, NULL, startsetting, enforceslater, timelimit) );
673  relaxdata->lastsdpnode = SCIPnodeGetNumber(SCIPgetCurrentNode(scip));
674 
675  /* update calls, iterations and stability numbers (only if the SDP-solver was actually called) */
676  relaxdata->sdpinterfacecalls++;
677  naddedsdpcalls = 0;
678  SCIP_CALL( SCIPsdpiGetSdpCalls(relaxdata->sdpi, &naddedsdpcalls) );
679  usedsetting = SCIP_SDPSOLVERSETTING_UNSOLVED;
680  if ( naddedsdpcalls )
681  {
682  relaxdata->sdpcalls += naddedsdpcalls;
683  naddediters = 0;
684  SCIP_CALL( SCIPsdpiGetIterations(relaxdata->sdpi, &naddediters) );
685  relaxdata->sdpiterations += naddediters;
686 
687  SCIP_CALL( SCIPsdpiSettingsUsed(relaxdata->sdpi, &usedsetting) );
688 
689  switch( usedsetting )/*lint --e{788}*/
690  {
691  case SCIP_SDPSOLVERSETTING_PENALTY:
692  relaxdata->solvedpenalty++;
693  break;
694  case SCIP_SDPSOLVERSETTING_FAST:
695  relaxdata->solvedfast++;
696  break;
697  case SCIP_SDPSOLVERSETTING_MEDIUM:
698  relaxdata->solvedmedium++;
699  break;
700  case SCIP_SDPSOLVERSETTING_STABLE:
701  relaxdata->solvedstable++;
702  break;
703  case SCIP_SDPSOLVERSETTING_UNSOLVED:
704  relaxdata->unsolved++;
705  break;
706  default:
707  break;
708  }
709  primalslater = SCIP_SDPSLATER_NOINFO;
710  dualslater = SCIP_SDPSLATER_NOINFO;
711  SCIP_CALL( SCIPsdpiSlater(relaxdata->sdpi, &primalslater, &dualslater) );
712  switch( primalslater )/*lint --e{788}*/
713  {
714  case SCIP_SDPSLATER_NOINFO:
715  relaxdata->npslatercheckfailed++;
716  switch( dualslater )/*lint --e{788}*/
717  {
718  case SCIP_SDPSLATER_NOINFO:
719  relaxdata->ndslatercheckfailed++;
720  relaxdata->nslatercheckfailed++;
721  break;
722  case SCIP_SDPSLATER_NOT:
723  relaxdata->ndnoslater++;
724  relaxdata->nnoslater++;
725  break;
726  case SCIP_SDPSLATER_HOLDS:
727  relaxdata->ndslaterholds++;
728  relaxdata->nslatercheckfailed++;
729  break;
730  case SCIP_SDPSLATER_INF:
731  relaxdata->nslaterinfeasible++;
732  break;
733  default:
734  relaxdata->ndslatercheckfailed++;
735  relaxdata->nslatercheckfailed++;
736  break;
737  }
738  break;
739  case SCIP_SDPSLATER_NOT:
740  relaxdata->npnoslater++;
741  switch( dualslater )/*lint --e{788}*/
742  {
743  case SCIP_SDPSLATER_NOINFO:
744  relaxdata->ndslatercheckfailed++;
745  relaxdata->nnoslater++;
746  break;
747  case SCIP_SDPSLATER_NOT:
748  relaxdata->ndnoslater++;
749  relaxdata->nnoslater++;
750  break;
751  case SCIP_SDPSLATER_HOLDS:
752  relaxdata->ndslaterholds++;
753  relaxdata->nnoslater++;
754  break;
755  case SCIP_SDPSLATER_INF:
756  relaxdata->nslaterinfeasible++;
757  break;
758  default:
759  relaxdata->ndslatercheckfailed++;
760  relaxdata->nnoslater++;
761  break;
762  }
763  break;
764  case SCIP_SDPSLATER_HOLDS:
765  relaxdata->npslaterholds++;
766  switch( dualslater )/*lint --e{788}*/
767  {
768  case SCIP_SDPSLATER_NOINFO:
769  relaxdata->ndslatercheckfailed++;
770  relaxdata->nslatercheckfailed++;
771  break;
772  case SCIP_SDPSLATER_NOT:
773  relaxdata->ndnoslater++;
774  relaxdata->nnoslater++;
775  break;
776  case SCIP_SDPSLATER_HOLDS:
777  relaxdata->ndslaterholds++;
778  relaxdata->nslaterholds++;
779  break;
780  case SCIP_SDPSLATER_INF:
781  relaxdata->nslaterinfeasible++;
782  break;
783  default:
784  relaxdata->ndslatercheckfailed++;
785  relaxdata->nslatercheckfailed++;
786  break;
787  }
788  break;
789  default:
790  relaxdata->npslatercheckfailed++;
791  relaxdata->ndslatercheckfailed++;
792  relaxdata->nslatercheckfailed++;
793  break;
794  }
795  slatersetting = SCIP_SDPSLATERSETTING_NOINFO;
796  SCIP_CALL( SCIPsdpiSlaterSettings(relaxdata->sdpi, &slatersetting) );
797  switch( slatersetting )/*lint --e{788}*/
798  {
799  case SCIP_SDPSLATERSETTING_STABLEWSLATER:
800  relaxdata->stablewslater++;
801  break;
802  case SCIP_SDPSLATERSETTING_UNSTABLEWSLATER:
803  relaxdata->unstablewslater++;
804  break;
805  case SCIP_SDPSLATERSETTING_PENALTYWSLATER:
806  relaxdata->penaltywslater++;
807  break;
808  case SCIP_SDPSLATERSETTING_BOUNDEDWSLATER:
809  relaxdata->boundedwslater++;
810  break;
811  case SCIP_SDPSLATERSETTING_UNSOLVEDWSLATER:
812  relaxdata->unsolvedwslater++;
813  break;
814  case SCIP_SDPSLATERSETTING_STABLENOSLATER:
815  relaxdata->stablenoslater++;
816  break;
817  case SCIP_SDPSLATERSETTING_UNSTABLENOSLATER:
818  relaxdata->unstablenoslater++;
819  break;
820  case SCIP_SDPSLATERSETTING_PENALTYNOSLATER:
821  relaxdata->penaltynoslater++;
822  break;
823  case SCIP_SDPSLATERSETTING_BOUNDEDNOSLATER:
824  relaxdata->boundednoslater++;
825  break;
826  case SCIP_SDPSLATERSETTING_UNSOLVEDNOSLATER:
827  relaxdata->unsolvednoslater++;
828  break;
829  case SCIP_SDPSLATERSETTING_STABLEINFEASIBLE:
830  relaxdata->stableinfeasible++;
831  break;
832  case SCIP_SDPSLATERSETTING_UNSTABLEINFEASIBLE:
833  relaxdata->unstableinfeasible++;
834  break;
835  case SCIP_SDPSLATERSETTING_PENALTYINFEASIBLE:
836  relaxdata->penaltyinfeasible++;
837  break;
838  case SCIP_SDPSLATERSETTING_BOUNDEDINFEASIBLE:
839  relaxdata->boundedinfeasible++;
840  break;
841  case SCIP_SDPSLATERSETTING_UNSOLVEDINFEASIBLE:
842  relaxdata->unsolvedinfeasible++;
843  break;
844  default:
845  break;
846  }
847  }
848 
849  /* remember settings */
850  if ( ! (strcmp(SCIPsdpiGetSolverName(), "DSDP") == 0) && ! (strstr(SCIPsdpiGetSolverName(), "MOSEK") != NULL) )
851  {
852  (void) SCIPsnprintf(saveconsname, SCIP_MAXSTRLEN, "savedsettings_node_%d", SCIPnodeGetNumber(SCIPgetCurrentNode(scip)));
853  SCIP_CALL( createConsSavedsdpsettings(scip, &savedsetting, saveconsname, usedsetting) );
854  SCIP_CALL( SCIPaddCons(scip, savedsetting) );
855  SCIP_CALL( SCIPreleaseCons(scip, &savedsetting) );
856  }
857 
858  if ( ! SCIPsdpiWasSolved(sdpi) )
859  relaxdata->feasible = FALSE;
860 
861  if ( SCIPinProbing(scip) )
862  relaxdata->probingsolved = SCIPsdpiWasSolved(sdpi);
863  else
864  relaxdata->origsolved = SCIPsdpiSolvedOrig(sdpi);
865 
866 
867  if ( SCIPsdpiIsAcceptable(sdpi) )
868  {
869 #ifdef SCIP_MORE_DEBUG /* print the optimal solution */
870  {
871  int sollength;
872  int i;
873  SCIP_CALL( SCIPallocBufferArray(scip, &solforscip, nvars) );
874  sollength = nvars;
875  SCIP_CALL( SCIPsdpiGetSol(sdpi, &objforscip, solforscip, &sollength) ); /* get both the objective and the solution from the SDP solver */
876 
877  assert( sollength == nvars ); /* If this isn't true any longer, the getSol-call was unsuccessfull, because the given array wasn't long enough,
878  * but this can't happen, because the array has enough space for all SDP variables. */
879 
880  if ( SCIPsdpiFeasibilityKnown(sdpi) )
881  {
882  SCIPdebugMessage("optimal solution: objective = %f, dual feasible: %u, primal feasible: %u.\n",
883  objforscip, SCIPsdpiIsDualFeasible(sdpi), SCIPsdpiIsPrimalFeasible(sdpi));
884  }
885  else
886  {
887  SCIPdebugMessage("The solver could not determine feasibility ! ");
888  }
889 
890  /* output solution */
891  for (i = 0; i < nvars; ++i)
892  {
893  SCIPdebugMessage("<%s> = %f\n", SCIPvarGetName(vars[i]), solforscip[i]);
894  }
895  SCIPfreeBufferArray(scip, &solforscip);
896  }
897 #endif
898 
899  if ( SCIPsdpiIsDualInfeasible(sdpi) )
900  {
901  SCIPdebugMessage("Node cut off due to infeasibility.\n");
902  relaxdata->feasible = FALSE;
903  *result = SCIP_CUTOFF;
904  return SCIP_OKAY;
905  }
906  else if ( SCIPsdpiIsObjlimExc(sdpi) )
907  {
908  SCIPdebugMessage("Node cut off due to objective limit.\n");
909  relaxdata->feasible = FALSE;
910  *result = SCIP_CUTOFF;
911  return SCIP_OKAY;
912  }
913  else if ( SCIPsdpiIsDualUnbounded(sdpi) )
914  {
915  SCIPdebugMessage("Node unbounded.");
916  relaxdata->feasible = TRUE;
917  *result = SCIP_SUCCESS;
918  *lowerbound = -SCIPinfinity(scip);
919  return SCIP_OKAY;
920  }
921  else if ( SCIPsdpiIsPrimalFeasible(sdpi) && SCIPsdpiIsDualFeasible(sdpi) )
922  {
923  SCIP_SOL* scipsol;
924  int slength;
925 
926  /* get solution w.r.t. SCIP variables */
927  SCIP_CALL( SCIPallocBufferArray(scip, &solforscip, nvars) );
928  slength = nvars;
929  SCIP_CALL( SCIPsdpiGetSol(sdpi, &objforscip, solforscip, &slength) ); /* get both the objective and the solution from the SDP solver */
930 
931  assert( slength == nvars ); /* If this isn't true any longer, the getSol-Call was unsuccessfull, because the given array wasn't long enough,
932  * but this can't happen, because the array has enough space for all sdp variables. */
933 
934  /* create SCIP solution */
935  SCIP_CALL( SCIPcreateSol(scip, &scipsol, NULL) );
936  for (v = 0; v < nvars; v++)
937  {
938  SCIP_CALL( SCIPsetSolVal(scip, scipsol, vars[v], solforscip[SCIPsdpVarmapperGetSdpIndex(relaxdata->varmapper, vars[v])]));
939  }
940 
941  *lowerbound = objforscip;
942  relaxdata->objval = objforscip;
943 
944  /* copy solution */
945  SCIP_CALL( SCIPsetRelaxSolValsSol(scip, scipsol) );
946 
947  SCIP_CALL( SCIPmarkRelaxSolValid(scip) );
948 
949  relaxdata->feasible = TRUE;
950  *result = SCIP_SUCCESS;
951 
952  SCIPfreeBufferArray(scip, &solforscip);
953  SCIP_CALL( SCIPfreeSol(scip, &scipsol) );
954  }
955  }
956  else
957  {
958  SCIP_Real objlb;
959 
960  if ( SCIPsdpiIsTimelimExc(relaxdata->sdpi) )
961  {
962  *result = SCIP_DIDNOTRUN;
963  return SCIP_OKAY;
964  }
965 
966  /* 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
967  * keep the current bound, if the current bound is -infty, we abort */
968  objlb = -SCIPinfinity(scip);
969  SCIP_CALL( SCIPsdpiGetLowerObjbound(relaxdata->sdpi, &objlb) );
970  if ( ! SCIPisInfinity(scip, objlb) )
971  {
972  *lowerbound = objlb;
973  SCIPdebugMessage("The relaxation could not be solved, using best computed bound from penalty formulation.\n");
974  }
975  else if ( ! SCIPisInfinity(scip, -1 * SCIPnodeGetLowerbound(SCIPgetCurrentNode(scip))) )
976  {
977  *lowerbound = SCIPnodeGetLowerbound(SCIPgetCurrentNode(scip));
978  SCIPdebugMessage("The relaxation could not be solved, keeping old bound.\n");
979  }
980  else
981  {
982  *result = SCIP_SUSPENDED;
983  SCIPerrorMessage("The relaxation of the root node could not be solved, so there is no hope to solve this instance.\n");
984  return SCIP_ERROR;
985  }
986 
987  *result = SCIP_SUCCESS;
988  return SCIP_OKAY;
989  }
990 
991  return SCIP_OKAY;
992 }
993 
995 static
996 SCIP_Bool allVarsFixed(
997  SCIP* scip
998  )
999 {
1000  SCIP_VAR** vars;
1001  int i;
1002 
1003  assert( scip != NULL );
1004 
1005  vars = SCIPgetVars(scip);
1006 
1007  /* try to find a variable that is not fixed */
1008  for (i = 0; i < SCIPgetNVars(scip); i++)
1009  {
1010  if ( SCIPisLT(scip, SCIPvarGetLbLocal(vars[i]), SCIPvarGetUbLocal(vars[i])) )
1011  return FALSE;
1012  }
1013 
1014  /* if no variable with lower bound strictly lower than upper bound has been found, all variables are fixed */
1015  return TRUE;
1016 }
1017 
1019 static
1020 SCIP_DECL_RELAXEXEC(relaxExecSdp)
1021 {
1022  SCIP_RELAXDATA* relaxdata;
1023  SCIP_VAR** vars;
1024  SCIP_Real* ubs;
1025  SCIP_Bool cutoff;
1026  SCIP_SOL* scipsol;
1027  int nconss;
1028  int nvars;
1029  int i;
1030 #ifdef SCIP_EVEN_MORE_DEBUG
1031  SCIP_VAR** varsfordebug = SCIPgetVars(scip);
1032  const int nvarsfordebug = SCIPgetNVars(scip);
1033 #endif
1034 
1035  SCIPdebugMessage("Calling relaxExecSdp.\n");
1036 
1037  relaxdata = SCIPrelaxGetData(relax);
1038  vars = SCIPgetVars(scip);
1039  nvars = SCIPgetNVars(scip);
1040 
1041  /* don't run again if we already solved the current node (except during probing), and we solved the correct problem */
1042  if ( (relaxdata->lastsdpnode == SCIPnodeGetNumber(SCIPgetCurrentNode(scip)) && ( ! SCIPinProbing(scip) ) ) && relaxdata->origsolved && ! relaxdata->resolve )
1043  {
1044  SCIP_COL** cols;
1045  SCIP_Real objforscip;
1046  SCIP_Real* solforscip;
1047  int ncols;
1048  int slength;
1049 
1050  SCIPdebugMessage("Already solved SDP-relaxation for node %ld, returning with SCIP_SUCCESS so that no other relaxator is called.\n",
1051  SCIPrelaxGetData(relax)->lastsdpnode);
1052 
1053  if ( SCIPsdpiIsDualUnbounded(relaxdata->sdpi) )
1054  {
1055  relaxdata->feasible = TRUE;
1056  *result = SCIP_SUCCESS;
1057  *lowerbound = -SCIPinfinity(scip);
1058  return SCIP_OKAY;
1059  }
1060 
1061  /* get solution w.r.t. SCIP variables */
1062  SCIP_CALL( SCIPallocBufferArray(scip, &solforscip, nvars) );
1063  slength = nvars;
1064  SCIP_CALL( SCIPsdpiGetSol(relaxdata->sdpi, &objforscip, solforscip, &slength) ); /* get both the objective and the solution from the SDP solver */
1065 
1066  assert( slength == nvars ); /* If this isn't true any longer, the getSol-Call was unsuccessfull, because the given array wasn't long enough,
1067  * but this can't happen, because the array has enough space for all sdp variables. */
1068 
1069  /* create SCIP solution */
1070  SCIP_CALL( SCIPcreateSol(scip, &scipsol, NULL) );
1071  SCIP_CALL( SCIPsetSolVals(scip, scipsol, nvars, vars, solforscip) );
1072 
1073  /* Update the lower bound. Note that we cannot use the objective value given by the SDP-solver since this might
1074  * vary from the value SCIP computes internally because of rounding errors when extracting the solution from the
1075  * SDP-solver */
1076  *lowerbound = SCIPgetSolTransObj(scip, scipsol);
1077 
1078  /* copy solution */
1079  SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
1080  for (i = 0; i < ncols; i++)
1081  {
1082  SCIP_CALL( SCIPsetRelaxSolVal(scip, SCIPcolGetVar(cols[i]), SCIPgetSolVal(scip, scipsol, SCIPcolGetVar(cols[i]))) );
1083  }
1084 
1085  SCIP_CALL( SCIPmarkRelaxSolValid(scip) );
1086  *result = SCIP_SUCCESS;
1087 
1088  SCIPfreeBufferArray(scip, &solforscip);
1089  SCIP_CALL( SCIPfreeSol(scip, &scipsol) );
1090 
1091  *result = SCIP_SUCCESS;
1092  return SCIP_OKAY;
1093  }
1094 
1095  /* if we are solving a probing SDP, remember that we didn't solve the original problem */
1096  relaxdata->origsolved = FALSE;
1097 
1098  /* construct the lp and make sure, that everything is where it should be */
1099  SCIP_CALL( SCIPconstructLP(scip, &cutoff) );
1100 
1101  if ( cutoff )
1102  {
1103  relaxdata->feasible = FALSE;
1104  *result = SCIP_CUTOFF;
1105  return SCIP_OKAY;
1106  }
1107 
1108  /* very important to call flushLP */
1109  SCIP_CALL( SCIPflushLP(scip) );
1110 
1111  /* get varmapper */
1112  nconss = SCIPgetNConss(scip);
1113 
1114 #ifdef SCIP_EVEN_MORE_DEBUG
1115  for (i = 0; i < nvarsfordebug; i++)
1116  {
1117  SCIPdebugMessage("variable %s: status = %u, integral = %u, bounds = [%f, %f] \n", SCIPvarGetName(varsfordebug[i]), SCIPvarGetStatus(varsfordebug[i]),
1118  SCIPvarIsIntegral(varsfordebug[i]), SCIPvarGetLbLocal(varsfordebug[i]), SCIPvarGetUbLocal(varsfordebug[i]));
1119  }
1120 #endif
1121 
1122  if ( nconss == 0 )
1123  {
1124  /* if there are no constraints, there is nothing to do */
1125  relaxdata->feasible = TRUE;
1126  *result = SCIP_DIDNOTRUN;
1127  return SCIP_OKAY;
1128  }
1129 
1130  if ( allVarsFixed(scip) )
1131  {
1132  SCIP_Bool feasible;
1133 
1134  /* if all variables, really all, are fixed, we give this fixed solution to SCIP */
1135 
1136  SCIP_CALL( SCIPallocBufferArray(scip, &ubs, nvars) );
1137 
1138  *lowerbound = 0.0;
1139  for (i = 0; i < nvars; i++)
1140  {
1141  ubs[i] = SCIPvarGetUbLocal(vars[i]);
1142  *lowerbound += SCIPvarGetObj(vars[i]) * ubs[i];
1143  assert( SCIPisFeasEQ(scip, SCIPvarGetUbLocal(vars[i]), SCIPvarGetLbLocal(vars[i])));
1144  }
1145 
1146  SCIPdebugMessage("EVERYTHING IS FIXED, objective value = %f\n", *lowerbound);
1147 
1148  SCIP_CALL( SCIPcreateSol(scip, &scipsol, NULL) );
1149  SCIP_CALL( SCIPsetSolVals(scip, scipsol, nvars, vars, ubs) );
1150 
1151  /* set the relaxation solution */
1152  for (i = 0; i < nvars; i++)
1153  {
1154  SCIP_CALL( SCIPsetRelaxSolVal(scip, vars[i], SCIPvarGetLbLocal(vars[i])) );
1155  }
1156  SCIP_CALL( SCIPmarkRelaxSolValid(scip) );
1157 
1158  /* check if the solution really is feasible */
1159  SCIP_CALL( SCIPcheckSol(scip, scipsol, FALSE, TRUE, TRUE, TRUE, TRUE, &feasible) );
1160 
1161  relaxdata->feasible = feasible;
1162 
1163  SCIP_CALL( SCIPfreeSol(scip, &scipsol) );
1164 
1165  SCIPfreeBufferArray(scip, &ubs);
1166 
1167  *result = SCIP_SUCCESS;
1168  return SCIP_OKAY;
1169  }
1170 
1171  /* update LP Data in Interface */
1172  SCIP_CALL( putLpDataInInterface(scip, relaxdata->sdpi, relaxdata->varmapper) );
1173 
1174  SCIP_CALL( calcRelax(scip, relaxdata, result, lowerbound));
1175 
1176  return SCIP_OKAY;
1177 }
1178 
1179 
1182 static
1183 SCIP_DECL_RELAXINITSOL(relaxInitSolSdp)
1184 {
1185  SCIP_RELAXDATA* relaxdata;
1186  SCIP_RETCODE retcode;
1187  SCIP_VAR** vars;
1188  SCIP_Real gaptol;
1189  SCIP_Real feastol;
1190  SCIP_Real penaltyparam;
1191  SCIP_Real maxpenaltyparam;
1192  int npenaltyincr;
1193  SCIP_Bool sdpinfo;
1194  SCIP_Real givenpenaltyparam;
1195  int nthreads;
1196  int slatercheck;
1197  int nvars;
1198 
1199  assert( relax != NULL );
1200 
1201  relaxdata = SCIPrelaxGetData(relax);
1202  assert( relaxdata != NULL );
1203 
1204  relaxdata->objval = 0.0;
1205  relaxdata->origsolved = FALSE;
1206  relaxdata->probingsolved = FALSE;
1207  relaxdata->sdpcalls = 0;
1208  relaxdata->sdpinterfacecalls = 0;
1209  relaxdata->sdpiterations = 0;
1210  relaxdata->solvedfast = 0;
1211  relaxdata->solvedmedium = 0;
1212  relaxdata->solvedstable = 0;
1213  relaxdata->solvedpenalty = 0;
1214  relaxdata->stablewslater = 0;
1215  relaxdata->unstablewslater = 0;
1216  relaxdata->boundedwslater = 0;
1217  relaxdata->unsolvedwslater = 0;
1218  relaxdata->stablenoslater = 0;
1219  relaxdata->unsolvednoslater = 0;
1220  relaxdata->boundednoslater = 0;
1221  relaxdata->unsolvednoslater = 0;
1222  relaxdata->nslaterholds = 0;
1223  relaxdata->nnoslater = 0;
1224  relaxdata->nslatercheckfailed = 0;
1225  relaxdata->npslaterholds = 0;
1226  relaxdata->npnoslater = 0;
1227  relaxdata->npslatercheckfailed = 0;
1228  relaxdata->ndslaterholds = 0;
1229  relaxdata->ndnoslater = 0;
1230  relaxdata->ndslatercheckfailed = 0;
1231  relaxdata->nslaterinfeasible = 0;
1232  relaxdata->stableinfeasible = 0;
1233  relaxdata->unstableinfeasible = 0;
1234  relaxdata->penaltyinfeasible = 0;
1235  relaxdata->boundedinfeasible = 0;
1236  relaxdata->unsolvedinfeasible = 0;
1237  relaxdata->unsolved = 0;
1238  relaxdata->feasible = FALSE;
1239 
1240  nvars = SCIPgetNVars(scip);
1241  vars = SCIPgetVars(scip);
1242 
1243  /* all SCIPvars will be added to this list, and 3/4 seems like a good load factor (java uses this factor) */
1244  SCIP_CALL( SCIPsdpVarmapperCreate(scip, &(relaxdata->varmapper), (int) ceil(1.33 * nvars)) );
1245  SCIP_CALL( SCIPsdpVarmapperAddVars(scip, relaxdata->varmapper, nvars, vars) );
1246 
1247  if ( SCIPgetNVars(scip) > 0 )
1248  {
1249  SCIP_CALL( putSdpDataInInterface(scip, relaxdata->sdpi, relaxdata->varmapper) );
1250  }
1251 
1252  /* set the parameters of the SDP-Solver */
1253  SCIP_CALL( SCIPgetRealParam(scip, "relaxing/SDP/sdpsolvergaptol", &gaptol) );
1254  retcode = SCIPsdpiSetRealpar(relaxdata->sdpi, SCIP_SDPPAR_GAPTOL, gaptol);
1255  if ( retcode == SCIP_PARAMETERUNKNOWN )
1256  {
1257  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL,
1258  "SDP Solver <%s>: gaptol setting not available -- SCIP parameter has no effect.\n",
1259  SCIPsdpiGetSolverName());
1260  }
1261  else
1262  {
1263  SCIP_CALL( retcode );
1264  }
1265 
1266  SCIP_CALL( SCIPgetRealParam(scip, "relaxing/SDP/sdpsolverfeastol", &feastol) );
1267  retcode = SCIPsdpiSetRealpar(relaxdata->sdpi, SCIP_SDPPAR_SDPSOLVERFEASTOL, feastol);
1268  if ( retcode == SCIP_PARAMETERUNKNOWN )
1269  {
1270  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL,
1271  "SDP Solver <%s>: sdpsolverfeastol setting not available -- SCIP parameter has no effect.\n",
1272  SCIPsdpiGetSolverName());
1273  }
1274  else
1275  {
1276  SCIP_CALL( retcode );
1277  }
1278 
1279  retcode = SCIPsdpiSetRealpar(relaxdata->sdpi, SCIP_SDPPAR_EPSILON, SCIPepsilon(scip));
1280  if ( retcode == SCIP_PARAMETERUNKNOWN )
1281  {
1282  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL,
1283  "SDP Solver <%s>: epsilon setting not available -- SCIP parameter has no effect.\n",
1284  SCIPsdpiGetSolverName());
1285  }
1286  else
1287  {
1288  SCIP_CALL( retcode );
1289  }
1290 
1291  retcode = SCIPsdpiSetRealpar(relaxdata->sdpi, SCIP_SDPPAR_FEASTOL, SCIPfeastol(scip));
1292  if ( retcode == SCIP_PARAMETERUNKNOWN )
1293  {
1294  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL,
1295  "SDP Solver <%s>: feastol setting not available -- SCIP parameter has no effect.\n",
1296  SCIPsdpiGetSolverName());
1297  }
1298  else
1299  {
1300  SCIP_CALL( retcode );
1301  }
1302 
1303  /* set/compute the starting penalty parameter */
1304  SCIP_CALL( SCIPgetRealParam(scip, "relaxing/SDP/penaltyparam", &penaltyparam) );
1305  if ( SCIPisGE(scip, penaltyparam, 0.0) )
1306  {
1307  retcode = SCIPsdpiSetRealpar(relaxdata->sdpi, SCIP_SDPPAR_PENALTYPARAM, penaltyparam);
1308  givenpenaltyparam = penaltyparam;
1309  if ( retcode == SCIP_PARAMETERUNKNOWN )
1310  {
1311  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL,
1312  "SDP Solver <%s>: penaltyparam setting not available -- SCIP parameter has no effect\n",
1313  SCIPsdpiGetSolverName());
1314  }
1315  else
1316  {
1317  SCIP_CALL( retcode );
1318  }
1319  }
1320  else
1321  {
1322  SCIP_Real maxcoeff;
1323  int v;
1324 
1325  /* compute the maximum coefficient in the objective */
1326  maxcoeff = 0.0;
1327  for (v = 0; v < nvars; v++)
1328  {
1329  if ( SCIPisGT(scip, REALABS(SCIPvarGetObj(vars[v])), maxcoeff) )
1330  maxcoeff = REALABS(SCIPvarGetObj(vars[v]));
1331  }
1332 
1333  SCIP_CALL( SCIPsdpiComputePenaltyparam(relaxdata->sdpi, maxcoeff, &givenpenaltyparam) );
1334  }
1335 
1336  /* set/compute the maximum penalty parameter */
1337  SCIP_CALL( SCIPgetRealParam(scip, "relaxing/SDP/maxpenaltyparam", &maxpenaltyparam) );
1338  if ( SCIPisGE(scip, maxpenaltyparam, 0.0) )
1339  {
1340  retcode = SCIPsdpiSetRealpar(relaxdata->sdpi, SCIP_SDPPAR_MAXPENALTYPARAM, maxpenaltyparam);
1341 
1342  if ( retcode == SCIP_PARAMETERUNKNOWN )
1343  {
1344  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL,
1345  "SDP Solver <%s>: maxpenaltyparam setting not available -- SCIP parameter has no effect.\n",
1346  SCIPsdpiGetSolverName());
1347  }
1348  else
1349  {
1350  SCIP_CALL( retcode );
1351  }
1352 
1353  /* check if the starting value is not bigger than the maximum one, otherwise update it */
1354  if ( SCIPisLT(scip, givenpenaltyparam, maxpenaltyparam) )
1355  {
1356  SCIPdebugMessage("Penalty parameter %f overwritten by maxpenaltyparam %f! \n", givenpenaltyparam, maxpenaltyparam);
1357  SCIP_CALL( SCIPsdpiSetRealpar(relaxdata->sdpi, SCIP_SDPPAR_PENALTYPARAM, maxpenaltyparam) );
1358  }
1359  }
1360  else
1361  {
1362  SCIP_Real givenmaxpenaltyparam;
1363 
1364  SCIP_CALL( SCIPsdpiComputeMaxPenaltyparam(relaxdata->sdpi, givenpenaltyparam, &givenmaxpenaltyparam) );
1365  }
1366 
1367  /* set maximum number of penalty increasing rounds */
1368  SCIP_CALL( SCIPgetIntParam(scip, "relaxing/SDP/npenaltyincr", &npenaltyincr) );
1369  retcode = SCIPsdpiSetIntpar(relaxdata->sdpi, SCIP_SDPPAR_NPENALTYINCR, npenaltyincr);
1370  if ( retcode == SCIP_PARAMETERUNKNOWN )
1371  {
1372  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL,
1373  "SDP Solver <%s>: npenaltyincr setting not available -- SCIP parameter has no effect.\n",
1374  SCIPsdpiGetSolverName());
1375  }
1376  else
1377  {
1378  SCIP_CALL( retcode );
1379  }
1380 
1381 
1382  /* set/compute lambda star if SDPA is used as the SDP-Solver */
1383  if ( strcmp(SCIPsdpiGetSolverName(), "SDPA") == 0.0 )
1384  {
1385  SCIP_Real lambdastar;
1386 
1387  SCIP_CALL( SCIPgetRealParam(scip, "relaxing/SDP/lambdastar", &lambdastar) );
1388  if ( SCIPisGE(scip, lambdastar, 0.0) )
1389  {
1390  retcode = SCIPsdpiSetRealpar(relaxdata->sdpi, SCIP_SDPPAR_LAMBDASTAR, lambdastar);
1391  }
1392  else
1393  {
1394  SCIP_Real guess;
1395  SCIP_Real maxguess;
1396  SCIP_CONS** conss;
1397  int nconss;
1398  int c;
1399 
1400  /* iterate over all SDP-constraints to compute the biggest guess for lambdastar */
1401  conss = SCIPgetConss(scip);
1402  nconss = SCIPgetNConss(scip);
1403  maxguess = 0.0;
1404 
1405  for (c = 0; c < nconss; c++)
1406  {
1407  /* only check the SDP constraints */
1408  if ( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(conss[c])), "SDP") == 0 )
1409  {
1410  SCIP_CALL( SCIPconsSdpGuessInitialPoint(scip, conss[c], &guess) );
1411  if ( (! SCIPisInfinity(scip, maxguess) ) && SCIPisGT(scip, guess, maxguess) )
1412  maxguess = guess;
1413  }
1414  }
1415 
1416  SCIP_CALL( SCIPsdpiComputeLambdastar(relaxdata->sdpi, maxguess) );
1417  }
1418  }
1419 
1420  if ( retcode == SCIP_PARAMETERUNKNOWN )
1421  {
1422  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL,
1423  "SDP Solver <%s>: lambdastar setting not available -- SCIP parameter has no effect.\n",
1424  SCIPsdpiGetSolverName());
1425  }
1426  else
1427  {
1428  SCIP_CALL( retcode );
1429  }
1430 
1431  SCIP_CALL( SCIPgetBoolParam(scip, "relaxing/SDP/sdpinfo", &sdpinfo) );
1432  retcode = SCIPsdpiSetIntpar(relaxdata->sdpi, SCIP_SDPPAR_SDPINFO, (int) sdpinfo);
1433  if ( retcode == SCIP_PARAMETERUNKNOWN )
1434  {
1435  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL,
1436  "SDP Solver <%s>: sdpinfo setting not available -- SCIP parameter has no effect.\n",
1437  SCIPsdpiGetSolverName());
1438  }
1439  else
1440  {
1441  SCIP_CALL( retcode );
1442  }
1443 
1444  SCIP_CALL( SCIPgetIntParam(scip, "relaxing/SDP/sdpsolverthreads", &nthreads) );
1445  /* only try to set nthreads if the value differs from the default to prevent unnecessary warning messages for unknown parameter */
1446  if ( nthreads != DEFAULT_SDPSOLVERTHREADS )
1447  {
1448  retcode = SCIPsdpiSetIntpar(relaxdata->sdpi, SCIP_SDPPAR_NTHREADS, nthreads);
1449  if ( retcode == SCIP_PARAMETERUNKNOWN )
1450  {
1451  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL,
1452  "SDP Solver <%s>: nthreads setting not available -- SCIP parameter has no effect.\n",
1453  SCIPsdpiGetSolverName());
1454  }
1455  else
1456  {
1457  SCIP_CALL( retcode );
1458  }
1459  }
1460 
1461  SCIP_CALL( SCIPgetIntParam(scip, "relaxing/SDP/slatercheck", &slatercheck) );
1462  retcode = SCIPsdpiSetIntpar(relaxdata->sdpi, SCIP_SDPPAR_SLATERCHECK, slatercheck);
1463  if ( retcode == SCIP_PARAMETERUNKNOWN )
1464  {
1465  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL,
1466  "SDP Solver <%s>: slatercheck setting not available -- SCIP parameter has no effect.\n",
1467  SCIPsdpiGetSolverName());
1468  }
1469  else
1470  {
1471  SCIP_CALL( retcode );
1472  }
1473 
1474  /* initialize objective limit in case it was set in an earlier optimize call */
1475  SCIP_CALL( SCIPsdpiSetRealpar(relaxdata->sdpi, SCIP_SDPPAR_OBJLIMIT, SCIPsdpiInfinity(relaxdata->sdpi)) );
1476 
1477  return SCIP_OKAY;
1478 }
1479 
1481 static
1482 SCIP_DECL_RELAXCOPY(relaxCopySdp)
1483 {
1484  assert( scip != NULL );
1485  assert( relax != NULL );
1486  assert(strcmp(SCIPrelaxGetName(relax), RELAX_NAME) == 0);
1487 
1488  SCIP_CALL( SCIPincludeRelaxSdp(scip) );
1489 
1490  return SCIP_OKAY;
1491 }
1492 
1494 static
1495 SCIP_DECL_RELAXEXIT(relaxExitSdp)
1496 {
1497  SCIP_RELAXDATA* relaxdata;
1498 
1499  assert( scip != NULL );
1500  assert( relax != NULL );
1501 
1502  relaxdata = SCIPrelaxGetData(relax);
1503  assert( relaxdata != NULL );
1504 
1505  SCIPdebugMessage("Exiting Relaxation Handler.\n");
1506 
1507  if ( relaxdata->displaystat && SCIPgetSubscipDepth(scip) == 0 )
1508  {
1509  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "\nSDP iterations:\t\t\t\t%6d\n", relaxdata->sdpiterations);
1510  if ( relaxdata->sdpcalls )
1511  {
1512  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Average SDP-iterations:\t\t\t%6.2f \n", (SCIP_Real) relaxdata->sdpiterations / (SCIP_Real) relaxdata->sdpcalls );
1513  }
1514  if ( relaxdata->sdpinterfacecalls )
1515  {
1516  if ( strcmp(SCIPsdpiGetSolverName(), "SDPA") == 0 )
1517  {
1518  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'fastest settings' solved:\t%6.2f \n", 100.0 * (SCIP_Real) relaxdata->solvedfast / (SCIP_Real) relaxdata->sdpinterfacecalls);
1519  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'medium settings' solved:\t%6.2f \n", 100.0 * (SCIP_Real) relaxdata->solvedmedium / (SCIP_Real) relaxdata->sdpinterfacecalls);
1520  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'stable settings' solved:\t%6.2f \n", 100.0 * (SCIP_Real) relaxdata->solvedstable / (SCIP_Real) relaxdata->sdpinterfacecalls);
1521  }
1522  else
1523  {
1524  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'default formulation' solved:\t%6.2f \n", 100.0 * (SCIP_Real) relaxdata->solvedfast / (SCIP_Real) relaxdata->sdpinterfacecalls);
1525  }
1526  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage penalty formulation used:\t%6.2f \n", 100.0 * (SCIP_Real) relaxdata->solvedpenalty / (SCIP_Real) relaxdata->sdpinterfacecalls);
1527  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);
1528  }
1529  if ( relaxdata->slatercheck )
1530  {
1531  if ( relaxdata->sdpinterfacecalls )
1532  {
1533  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);
1534  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);
1535  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);
1536 
1537  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);
1538  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);
1539  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);
1540  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);
1541  }
1542  if ( relaxdata->nslaterholds )
1543  {
1544  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'fastest settings' with primal and dual slater holding:\t%6.2f \n",
1545  100.0 * (SCIP_Real) relaxdata->stablewslater / (SCIP_Real) relaxdata->nslaterholds);
1546  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'stable settings' with primal and dual slater holding:\t%6.2f \n",
1547  100.0 * (SCIP_Real) relaxdata->unstablewslater / (SCIP_Real) relaxdata->nslaterholds);
1548  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'penalty' with primal and dual slater holding:\t%6.2f \n",
1549  100.0 * (SCIP_Real) relaxdata->penaltywslater / (SCIP_Real) relaxdata->nslaterholds);
1550  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'computed infeasible lower bound' with primal and dual slater holding:\t%6.2f \n",
1551  100.0 * (SCIP_Real) relaxdata->boundedwslater / (SCIP_Real) relaxdata->nslaterholds);
1552  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'unsolved' with primal and dual slater holding:\t%6.2f \n",
1553  100.0 * (SCIP_Real) relaxdata->unsolvedwslater / (SCIP_Real) relaxdata->nslaterholds);
1554  }
1555  if ( relaxdata->nnoslater )
1556  {
1557  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'fastest settings' with either primal or dual slater not holding:\t%6.2f \n",
1558  100.0 * (SCIP_Real) relaxdata->stablenoslater / (SCIP_Real) relaxdata->nnoslater);
1559  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'stable settings' with either primal or dual slater not holding:\t%6.2f \n",
1560  100.0 * (SCIP_Real) relaxdata->unstablenoslater / (SCIP_Real) relaxdata->nnoslater);
1561  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'penalty' with either primal or dual slater not holding:\t%6.2f \n",
1562  100.0 * (SCIP_Real) relaxdata->penaltynoslater / (SCIP_Real) relaxdata->nnoslater);
1563  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'computed infeasible lower bound' with either primal or dual slater not holding:\t%6.2f \n",
1564  100.0 * (SCIP_Real) relaxdata->boundednoslater / (SCIP_Real) relaxdata->nnoslater);
1565  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'unsolved' with either primal or dual slater not holding:\t%6.2f \n",
1566  100.0 * (SCIP_Real) relaxdata->unsolvednoslater / (SCIP_Real) relaxdata->nnoslater);
1567  }
1568  if ( relaxdata->nslaterinfeasible )
1569  {
1570  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'fastest settings' with slater check showing infeasibility:\t%6.2f \n",
1571  100.0 * (SCIP_Real) relaxdata->stableinfeasible / (SCIP_Real) relaxdata->nslaterinfeasible);
1572  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'stable settings' with slater check showing infeasibility:\t%6.2f \n",
1573  100.0 * (SCIP_Real) relaxdata->unstableinfeasible / (SCIP_Real) relaxdata->nslaterinfeasible);
1574  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'penalty' with slater check showing infeasibility:\t%6.2f \n",
1575  100.0 * (SCIP_Real) relaxdata->penaltyinfeasible / (SCIP_Real) relaxdata->nslaterinfeasible);
1576  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'computed infeasible lower bound' with slater check showing infeasibility:\t%6.2f \n",
1577  100.0 * (SCIP_Real) relaxdata->boundedinfeasible / (SCIP_Real) relaxdata->nslaterinfeasible);
1578  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Percentage 'unsolved' with slater check showing infeasibility:\t%6.2f \n",
1579  100.0 * (SCIP_Real) relaxdata->unsolvedinfeasible / (SCIP_Real) relaxdata->nslaterinfeasible);
1580  }
1581 #ifdef SLATERSOLVED_ABSOLUTE
1582  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of nodes with primal and dual slater holding:\t%d \n", relaxdata->nslaterholds);
1583  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of nodes with 'fastest settings' and primal and dual slater holding:\t%d \n", relaxdata->stablewslater);
1584  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of nodes with 'stable settings' and primal and dual slater holding:\t%d \n", relaxdata->unstablewslater);
1585  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of nodes with 'penalty' and primal and dual slater holding:\t%d \n", relaxdata->penaltywslater);
1586  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);
1587  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of nodes with 'unsolved' and primal and dual slater holding:\t%d \n", relaxdata->unsolvedwslater);
1588 
1589  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of nodes with either primal or dual slater not holding:\t%d \n", relaxdata->nnoslater);
1590  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);
1591  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);
1592  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of nodes with 'penalty' and either primal or dual slater not holding:\t%d \n", relaxdata->penaltynoslater);
1593  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);
1594  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of nodes with 'unsolved' and either primal or dual slater not holding:\t%d \n", relaxdata->unsolvednoslater);
1595 
1596  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of infeasible nodes:\t%d \n", relaxdata->nslaterinfeasible);
1597  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of infeasible nodes with 'fastest settings':\t%d \n", relaxdata->stableinfeasible);
1598  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of infeasible nodes with 'stable settings':\t%d \n", relaxdata->unstableinfeasible);
1599  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of infeasible nodes with 'penalty':\t%d \n", relaxdata->penaltyinfeasible);
1600  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of infeasible nodes with 'computed infeasible lower bound':\t%d \n", relaxdata->boundedinfeasible);
1601  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Number of infeasible nodes with 'unsolved':\t%d \n", relaxdata->unsolvedinfeasible);
1602 #endif
1603  }
1604  }
1605 
1606  if ( relaxdata->varmapper != NULL )
1607  {
1608  SCIP_CALL( SCIPsdpVarmapperFree(scip, &(relaxdata->varmapper)) );
1609  }
1610 
1611  relaxdata->objval = 0.0;
1612  relaxdata->origsolved = FALSE;
1613  relaxdata->probingsolved = FALSE;
1614  relaxdata->feasible = FALSE;
1615  relaxdata->sdpiterations = 0;
1616  relaxdata->sdpcalls = 0;
1617  relaxdata->sdpinterfacecalls = 0;
1618  relaxdata->lastsdpnode = 0;
1619  SCIP_CALL( SCIPsdpiClear(relaxdata->sdpi) );
1620 
1621  return SCIP_OKAY;
1622 }
1623 
1625 static
1626 SCIP_DECL_RELAXFREE(relaxFreeSdp)
1627 {/*lint --e{715}*/
1628  SCIP_RELAXDATA* relaxdata;
1629 
1630  relaxdata = SCIPrelaxGetData(relax);
1631  assert(relaxdata != NULL);
1632 
1633  if ( relaxdata->sdpi != NULL )
1634  {
1635  SCIP_CALL( SCIPsdpiFree(&(relaxdata->sdpi)) );
1636  }
1637 
1638  SCIPfreeMemory(scip, &relaxdata);
1639 
1640  SCIPrelaxSetData(relax, NULL);
1641 
1642  return SCIP_OKAY;
1643 }
1644 
1646 SCIP_RETCODE SCIPincludeRelaxSdp(
1647  SCIP* scip
1648  )
1649 {
1650  SCIP_RELAXDATA* relaxdata = NULL;
1651  SCIP_RELAX* relax;
1652  SCIP_SDPI* sdpi;
1653 
1654  assert( scip != NULL );
1655 
1656  /* create SDP-relaxator data */
1657  SCIP_CALL( SCIPallocMemory(scip, &relaxdata) );
1658  SCIP_CALL( SCIPsdpiCreate(&sdpi, SCIPgetMessagehdlr(scip), SCIPblkmem(scip), SCIPbuffer(scip)) );
1659 
1660  relaxdata->sdpi = sdpi;
1661  relaxdata->lastsdpnode = -1;
1662 
1663  /* include relaxator */
1664  SCIP_CALL( SCIPincludeRelaxBasic(scip, &relax, RELAX_NAME, RELAX_DESC, RELAX_PRIORITY, RELAX_FREQ, TRUE, relaxExecSdp, relaxdata) );
1665  assert( relax != NULL );
1666 
1667  /* include additional callbacks */
1668  SCIP_CALL( SCIPsetRelaxInitsol(scip, relax, relaxInitSolSdp) );
1669  SCIP_CALL( SCIPsetRelaxExit(scip, relax, relaxExitSdp) );
1670  SCIP_CALL( SCIPsetRelaxFree(scip, relax, relaxFreeSdp) );
1671  SCIP_CALL( SCIPsetRelaxCopy(scip, relax, relaxCopySdp) );
1672 
1673  /* add parameters for SDP-solver */
1674  SCIP_CALL( SCIPaddRealParam(scip, "relaxing/SDP/sdpsolvergaptol",
1675  "the stopping criterion for the duality gap the sdpsolver should use",
1676  &(relaxdata->sdpsolvergaptol), TRUE, DEFAULT_SDPSOLVERGAPTOL, 1e-20, 0.001, NULL, NULL) );
1677 
1678  SCIP_CALL( SCIPaddRealParam(scip, "relaxing/SDP/sdpsolverfeastol",
1679  "the feasibility tolerance for the SDP solver",
1680  &(relaxdata->sdpsolverfeastol), TRUE, SCIPsdpiGetDefaultSdpiSolverFeastol(), 1e-17, 0.001, NULL, NULL) );
1681 
1682  SCIP_CALL( SCIPaddRealParam(scip, "relaxing/SDP/penaltyparam",
1683  "the starting value of the penalty parameter Gamma used for the penalty formulation if the "
1684  "SDP solver didn't converge; set this to a negative value to compute the parameter depending on the given problem", &(relaxdata->penaltyparam),
1685  TRUE, DEFAULT_PENALTYPARAM, -1.0, 1e+20, NULL, NULL) );
1686 
1687  SCIP_CALL( SCIPaddRealParam(scip, "relaxing/SDP/maxpenaltyparam",
1688  "the maximum value of the penalty parameter Gamma used for the penalty formulation if the "
1689  "SDP solver didn't converge; set this to a negative value to compute the parameter depending on the given problem", &(relaxdata->maxpenaltyparam),
1690  TRUE, DEFAULT_MAXPENALTYPARAM, -1.0, 1e+20, NULL, NULL) );
1691 
1692  SCIP_CALL( SCIPaddIntParam(scip, "relaxing/SDP/npenaltyincr",
1693  "maximum number of times the penalty parameter will be increased if the penalty formulation failed", &(relaxdata->npenaltyincr), TRUE,
1694  SCIPsdpiGetDefaultSdpiSolverNpenaltyIncreases(), 0, INT_MAX, NULL, NULL) );
1695 
1696  SCIP_CALL( SCIPaddRealParam(scip, "relaxing/SDP/lambdastar",
1697  "the parameter lambda star used by SDPA to set the initial point;"
1698  "set this to a negative value to compute the parameter depending on the given problem", &(relaxdata->lambdastar),
1699  TRUE, DEFAULT_LAMBDASTAR, -1.0, 1e+20, NULL, NULL) );
1700 
1701  SCIP_CALL( SCIPaddIntParam(scip, "relaxing/SDP/slatercheck",
1702  "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 "
1703  "every problem not satisfying primal and dual Slater condition", &(relaxdata->slatercheck), TRUE, DEFAULT_SLATERCHECK, 0, 2, NULL, NULL) );
1704 
1705  SCIP_CALL( SCIPaddBoolParam(scip, "relaxing/SDP/sdpinfo",
1706  "Should the SDP solver output information to the screen?",
1707  &(relaxdata->sdpinfo), TRUE, DEFAULT_SDPINFO, NULL, NULL) );
1708 
1709  SCIP_CALL( SCIPaddBoolParam(scip, "relaxing/SDP/objlimit",
1710  "Should an objective limit be given to the SDP-Solver?",
1711  &(relaxdata->objlimit), TRUE, DEFAULT_OBJLIMIT, NULL, NULL) );
1712 
1713  SCIP_CALL( SCIPaddBoolParam(scip, "relaxing/SDP/resolve",
1714  "Should the relaxation be resolved after bound-tightenings were found during propagation (outside of probing)?",
1715  &(relaxdata->resolve), TRUE, DEFAULT_RESOLVE, NULL, NULL) );
1716 
1717  SCIP_CALL( SCIPaddBoolParam(scip, "relaxing/SDP/tightenvb",
1718  "Should Big-Ms in varbound-like constraints be tightened before giving them to the SDP-solver ?",
1719  &(relaxdata->tightenvb), TRUE, DEFAULT_TIGHTENVB, NULL, NULL) );
1720 
1721  SCIP_CALL( SCIPaddBoolParam(scip, "relaxing/SDP/displaystatistics",
1722  "Should statistics about SDP iterations and solver settings/success be printed after quitting SCIP-SDP ?",
1723  &(relaxdata->displaystat), TRUE, DEFAULT_DISPLAYSTAT, NULL, NULL) );
1724 
1725  SCIP_CALL( SCIPaddIntParam(scip, "relaxing/SDP/settingsresetfreq",
1726  "frequency for resetting parameters in SDP solver and trying again with fastest settings (-1: never, 0: only at depth settingsresetofs);"
1727  "currently only supported for SDPA",
1728  &(relaxdata->settingsresetfreq), TRUE, DEFAULT_SETTINGSRESETFREQ, -1, INT_MAX, NULL, NULL) );
1729 
1730  SCIP_CALL( SCIPaddIntParam(scip, "relaxing/SDP/settingsresetofs",
1731  "frequency offset for resetting parameters in SDP solver and trying again with fastest settings; currently only supported for SDPA",
1732  &(relaxdata->settingsresetofs), TRUE, DEFAULT_SETTINGSRESETOFS, 0, INT_MAX, NULL, NULL) );
1733 
1734  SCIP_CALL( SCIPaddIntParam(scip, "relaxing/SDP/sdpsolverthreads",
1735  "number of threads the SDP solver should use (-1 = number of cores); currently only supported for MOSEK",
1736  &(relaxdata->sdpsolverthreads), TRUE, DEFAULT_SDPSOLVERTHREADS, -1, INT_MAX, NULL, NULL) );
1737 
1738 
1739  /* add description of SDP-solver */
1740  SCIP_CALL( SCIPincludeExternalCodeInformation(scip, SCIPsdpiGetSolverName(), SCIPsdpiGetSolverDesc()) );
1741 
1742  return SCIP_OKAY;
1743 }
1744 
1745 
1746 /* external functions */
1747 
1756 SCIP_RETCODE SCIPrelaxSdpGetPrimalBoundVars(
1757  SCIP_RELAX* relax,
1758  SCIP_Real* lbvars,
1759  SCIP_Real* ubvars,
1760  int* arraylength
1762  )
1763 {
1764  SCIP_RELAXDATA* relaxdata;
1765 
1766  assert( relax != NULL );
1767  assert( lbvars != NULL );
1768  assert( ubvars != NULL );
1769  assert( arraylength != NULL );
1770  assert( *arraylength >= 0 );
1771 
1772  relaxdata = SCIPrelaxGetData(relax);
1773  assert( relaxdata != NULL );
1774 
1775  SCIP_CALL( SCIPsdpiGetPrimalBoundVars(relaxdata->sdpi, lbvars, ubvars, arraylength) );
1776 
1777  return SCIP_OKAY;
1778 }
1779 
1781 SCIP_RETCODE SCIPrelaxSdpRelaxVal(
1782  SCIP_RELAX* relax,
1783  SCIP_Bool* success,
1784  SCIP_Real* objval
1785  )
1786 {
1787  SCIP_RELAXDATA* relaxdata;
1788 
1789  assert( relax != NULL );
1790  assert( success != NULL );
1791  assert( objval != NULL );
1792 
1793  relaxdata = SCIPrelaxGetData(relax);
1794  assert( relaxdata != NULL );
1795 
1796  *success = relaxdata->origsolved;
1797  *objval = relaxdata->objval;
1798 
1799  return SCIP_OKAY;
1800 }
1801 
1803 SCIP_RETCODE SCIPrelaxSdpGetRelaxSol(
1804  SCIP* scip,
1805  SCIP_RELAX* relax,
1806  SCIP_Bool* success,
1807  SCIP_Real* solarray,
1808  int* sollength
1809  )
1810 {
1811  SCIP_RELAXDATA* relaxdata;
1812 
1813  assert( relax != NULL );
1814  assert( success != NULL );
1815  assert( solarray != NULL );
1816 
1817  relaxdata = SCIPrelaxGetData(relax);
1818  assert( relaxdata != NULL );
1819 
1820  *success = relaxdata->origsolved;
1821 
1822  if ( *sollength >= SCIPgetNVars(scip) )
1823  {
1824  SCIP_CALL( SCIPsdpiGetSol(relaxdata->sdpi, NULL, solarray, sollength) );
1825  }
1826  else
1827  {
1828  SCIPdebugMessage("Called SCIPrelaxSdpGetRelaxSol with an array that wasn't big enough, needed length %d, given %d!\n", SCIPgetNVars(scip), *sollength);
1829  *sollength = SCIPgetNVars(scip);
1830  }
1831 
1832  return SCIP_OKAY;
1833 }
1834 
1836 long int SCIPrelaxSdpGetSdpNode(
1837  SCIP_RELAX* relax
1838  )
1839 {
1840  assert( relax != NULL );
1841  assert( SCIPrelaxGetData(relax) != NULL );
1842 
1843  return SCIPrelaxGetData(relax)->lastsdpnode;
1844 }
1845 
1847 SCIP_Bool SCIPrelaxSdpSolvedOrig(
1848  SCIP_RELAX* relax
1849  )
1850 {
1851  SCIP_RELAXDATA* relaxdata;
1852 
1853  assert( relax != NULL );
1854 
1855  relaxdata = SCIPrelaxGetData(relax);
1856 
1857  assert( relaxdata != NULL );
1858  assert( relaxdata->sdpi != NULL );
1859 
1860  return relaxdata->origsolved && SCIPsdpiSolvedOrig(relaxdata->sdpi);
1861 }
1862 
1864 SCIP_Bool SCIPrelaxSdpSolvedProbing(
1865  SCIP_RELAX* relax
1866  )
1867 {
1868  SCIP_RELAXDATA* relaxdata;
1869 
1870  assert( relax != NULL );
1871 
1872  relaxdata = SCIPrelaxGetData(relax);
1873 
1874  assert( relaxdata != NULL );
1875  assert( relaxdata->sdpi != NULL );
1876 
1877  return relaxdata->probingsolved;
1878 }
1879 
1881 SCIP_Bool SCIPrelaxSdpIsFeasible(
1882  SCIP_RELAX* relax
1883  )
1884 {
1885  assert( relax != NULL );
1886  assert( SCIPrelaxGetData(relax) != NULL );
1887 
1888  return ( SCIPrelaxGetData(relax)->feasible );
1889 }
1890 
1892 int SCIPrelaxSdpGetNIterations(
1893  SCIP_RELAX* relax
1894  )
1895 {
1896  assert( relax != NULL );
1897  assert( SCIPrelaxGetData(relax) != NULL );
1898 
1899  return SCIPrelaxGetData(relax)->sdpiterations;
1900 }
1901 
1903 int SCIPrelaxSdpGetNSdpCalls(
1904  SCIP_RELAX* relax
1905  )
1906 {
1907  assert( relax != NULL );
1908  assert( SCIPrelaxGetData(relax) != NULL );
1909 
1910  return ( SCIPrelaxGetData(relax)->sdpcalls );
1911 }
1912 
1914 int SCIPrelaxSdpGetNSdpInterfaceCalls(
1915  SCIP_RELAX* relax
1916  )
1917 {
1918  assert( relax != NULL );
1919  assert( SCIPrelaxGetData(relax) != NULL );
1920 
1921  return ( SCIPrelaxGetData(relax)->sdpinterfacecalls );
1922 }
1923 
1925 int SCIPrelaxSdpGetNSdpFast(
1926  SCIP_RELAX* relax
1927  )
1928 {
1929  assert( relax != NULL );
1930  assert( SCIPrelaxGetData(relax) != NULL );
1931 
1932  return ( SCIPrelaxGetData(relax)->solvedfast );
1933 }
1934 
1936 int SCIPrelaxSdpGetNSdpMedium(
1937  SCIP_RELAX* relax
1938  )
1939 {
1940  assert( relax != NULL );
1941  assert( SCIPrelaxGetData(relax) != NULL );
1942 
1943  return ( SCIPrelaxGetData(relax)->solvedmedium );
1944 }
1945 
1947 int SCIPrelaxSdpGetNSdpStable(
1948  SCIP_RELAX* relax
1949  )
1950 {
1951  assert( relax != NULL );
1952  assert( SCIPrelaxGetData(relax) != NULL );
1953 
1954  return ( SCIPrelaxGetData(relax)->solvedstable );
1955 }
1956 
1958 int SCIPrelaxSdpGetNSdpPenalty(
1959  SCIP_RELAX* relax
1960  )
1961 {
1962  assert( relax != NULL );
1963  assert( SCIPrelaxGetData(relax) != NULL );
1964 
1965  return ( SCIPrelaxGetData(relax)->solvedpenalty );
1966 }
1967 
1969 int SCIPrelaxSdpGetNSdpUnsolved(
1970  SCIP_RELAX* relax
1971  )
1972 {
1973  assert( relax != NULL );
1974  assert( SCIPrelaxGetData(relax) != NULL );
1975 
1976  return ( SCIPrelaxGetData(relax)->unsolved );
1977 }
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:1482
SCIPsdpVarmapperAddVars
SCIP_RETCODE SCIPsdpVarmapperAddVars(SCIP *scip, SdpVarmapper *varmapper, int nvars, SCIP_VAR **vars)
Definition: SdpVarmapper.c:108
allVarsFixed
static SCIP_Bool allVarsFixed(SCIP *scip)
Definition: relax_sdp.c:996
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:1958
SCIP_SDPSOLVERSETTING
enum SCIP_SDPSolverSetting SCIP_SDPSOLVERSETTING
Definition: type_sdpi.h:78
SCIP_DECL_RELAXEXIT
static SCIP_DECL_RELAXEXIT(relaxExitSdp)
Definition: relax_sdp.c:1495
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:1969
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:1020
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:1183
SCIPrelaxSdpGetNSdpStable
int SCIPrelaxSdpGetNSdpStable(SCIP_RELAX *relax)
Definition: relax_sdp.c:1947
SCIPrelaxSdpGetNSdpMedium
int SCIPrelaxSdpGetNSdpMedium(SCIP_RELAX *relax)
Definition: relax_sdp.c:1936
SCIPsdpVarmapperCreate
SCIP_RETCODE SCIPsdpVarmapperCreate(SCIP *scip, SdpVarmapper **varmapper, int size)
Definition: SdpVarmapper.c:53
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:1781
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:1626
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:225
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:1914
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:1903
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:1864
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:1836
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:1925
SCIPrelaxSdpSolvedOrig
SCIP_Bool SCIPrelaxSdpSolvedOrig(SCIP_RELAX *relax)
Definition: relax_sdp.c:1847
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:1892
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:1803
SCIPsdpVarmapperFree
SCIP_RETCODE SCIPsdpVarmapperFree(SCIP *scip, SdpVarmapper **varmapper)
Definition: SdpVarmapper.c:80
SCIPrelaxSdpGetPrimalBoundVars
SCIP_RETCODE SCIPrelaxSdpGetPrimalBoundVars(SCIP_RELAX *relax, SCIP_Real *lbvars, SCIP_Real *ubvars, int *arraylength)
Definition: relax_sdp.c:1756
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:1881
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:1646
cons_savedsdpsettings.h
constraint handler for saving SDP settings
Generated on Thu Aug 31 2017 15:48:00 for SCIP-SDP by   doxygen 1.8.7