heur_sdpinnerlp.c File Reference

set up inner approximation LP formulation and run heuristics More...

Go to the source code of this file.

Macros
#define	HEUR_NAME   "sdpinnerlp"
#define	HEUR_DESC   "inner approximation LP heuristic for SDPs"
#define	HEUR_DISPCHAR   '!'
#define	HEUR_PRIORITY   -1001000
#define	HEUR_FREQ   -1
#define	HEUR_FREQOFS   0
#define	HEUR_MAXDEPTH   -1
#define	HEUR_TIMING   SCIP_HEURTIMING_BEFOREPRESOL
#define	HEUR_USESSUBSCIP   TRUE /* does the heuristic use a secondary SCIP instance? */
#define	DEFAULT_STALLNODELIMIT   100L
#define	DEFAULT_MAXSIZE   10000

Functions
static	SCIP_DECL_HEURCOPY (heurCopySdpInnerlp)
static	SCIP_DECL_HEURFREE (heurFreeSdpInnerlp)
static	SCIP_DECL_HEUREXEC (heurExecSdpInnerlp)
SCIP_RETCODE	SCIPincludeHeurSdpInnerlp (SCIP *scip)

Detailed Description

set up inner approximation LP formulation and run heuristics

Author

Marc Pfetsch

The idea of this heuristic is to check whether there is a diagonally dominant solution via an LP. This is described in
Optimization over structured subsets of positive semidefinite matrices via column generation
Amir Ali Ahmadi, Sanjeeb Dash, and Georgina Hall Discrete Optimization 24 (2017) 129-151

Assume that an SDP-constraint is given as \( \sum_{j=1}^n A_j y_j - A_0 \succeq 0 \). We then consider a set of rank-1 SDP matrices \(B_1, \dots, B_t\) and write

\[ \sum_{j=1}^n A_j y_j - A_0 = \sum_{i=1}^t B_i \alpha_i,\; \alpha \geq 0. \]

We use all \(n^2\) matrices \(B_i\) that arise as \(u u^T\), where \(u\) has at most 2 nonzero entries \(\pm 1\). It can be shown that this choice suffices to represent all diagonally dominant matrices. The given constraints are actually linear in the \(y\)-variables. We set up a MIP and solve it. If it is feasible, it should provide a feasible solution for the original problem. However, often the problem is infeasible or only provides a weak solution.

We currently do not use the column generation aspect of the paper mentioned above.

Definition in file heur_sdpinnerlp.c.

Macro Definition Documentation

#define HEUR_NAME   "sdpinnerlp"

Definition at line 66 of file heur_sdpinnerlp.c.

Referenced by SCIP_DECL_HEURCOPY(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEURFREE(), and SCIPincludeHeurSdpInnerlp().

#define HEUR_DESC   "inner approximation LP heuristic for SDPs"

Definition at line 67 of file heur_sdpinnerlp.c.

Referenced by SCIPincludeHeurSdpInnerlp().

#define HEUR_DISPCHAR   '!'

Definition at line 68 of file heur_sdpinnerlp.c.

Referenced by SCIPincludeHeurSdpInnerlp().

#define HEUR_PRIORITY   -1001000

Definition at line 69 of file heur_sdpinnerlp.c.

Referenced by SCIPincludeHeurSdpInnerlp().

#define HEUR_FREQ   -1

Definition at line 70 of file heur_sdpinnerlp.c.

Referenced by SCIPincludeHeurSdpInnerlp().

#define HEUR_FREQOFS   0

Definition at line 71 of file heur_sdpinnerlp.c.

Referenced by SCIPincludeHeurSdpInnerlp().

#define HEUR_MAXDEPTH   -1

Definition at line 72 of file heur_sdpinnerlp.c.

Referenced by SCIPincludeHeurSdpInnerlp().

#define HEUR_TIMING   SCIP_HEURTIMING_BEFOREPRESOL

Definition at line 73 of file heur_sdpinnerlp.c.

Referenced by SCIPincludeHeurSdpInnerlp().

#define HEUR_USESSUBSCIP   TRUE /* does the heuristic use a secondary SCIP instance? */

Definition at line 74 of file heur_sdpinnerlp.c.

Referenced by SCIPincludeHeurSdpInnerlp().

#define DEFAULT_STALLNODELIMIT   100L

limit on number of nodes since last improving incumbent solutions

Definition at line 81 of file heur_sdpinnerlp.c.

Referenced by SCIPincludeHeurSdpInnerlp().

#define DEFAULT_MAXSIZE   10000

maximal size of the inner problem

Definition at line 82 of file heur_sdpinnerlp.c.

Referenced by SCIPincludeHeurSdpInnerlp().

Function Documentation

static SCIP_DECL_HEURCOPY ( heurCopySdpInnerlp  )

static

copy method for primal heuristic plugins (called when SCIP copies plugins)

Definition at line 99 of file heur_sdpinnerlp.c.

References HEUR_NAME, and SCIPincludeHeurSdpInnerlp().

static SCIP_DECL_HEURFREE ( heurFreeSdpInnerlp  )

static

destructor of primal heuristic to free user data (called when SCIP is exiting)

Definition at line 113 of file heur_sdpinnerlp.c.

References HEUR_NAME.

static SCIP_DECL_HEUREXEC ( heurExecSdpInnerlp  )

static

execution method of primal heuristic

Definition at line 133 of file heur_sdpinnerlp.c.

References HEUR_NAME, SCIPconsSdpGetBlocksize(), SCIPconsSdpGetFullAj(), SCIPconsSdpGetFullConstMatrix(), SCIPconsSdpGetNVars(), and SCIPconsSdpGetVars().

SCIP_RETCODE SCIPincludeHeurSdpInnerlp

(

SCIP *

scip

)

creates the innerlp heuristic for SDPs and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 470 of file heur_sdpinnerlp.c.

References DEFAULT_MAXSIZE, DEFAULT_STALLNODELIMIT, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, and HEUR_USESSUBSCIP.

Referenced by SCIP_DECL_HEURCOPY(), and SCIPSDPincludeDefaultPlugins().