# SCIP

Solving Constraint Integer Programs

## Detailed Description

Primal heuristic based on ideas published in the papers "A Decomposition Heuristic for Mixed-Integer Supply Chain Problems" by Martin Schmidt, Lars Schewe, and Dieter Weninger, and "Exploiting user-supplied Decompositions inside Heuristics" by Katrin Halbig, Adrian Göß and Dieter Weninger.

The penalty alternating direction method (PADM) heuristic is a construction heuristic which additionally needs a user decomposition with linking variables only.

PADM splits the problem into several sub-SCIPs according to the decomposition, whereby the linking variables get copied and the difference is penalized. Then the sub-SCIPs are solved on an alternating basis until they arrive at the same values of the linking variables (ADM-loop). If they don't reconcile after a couple of iterations, the penalty parameters are increased (penalty-loop) and the sub-SCIPs are solved again on an alternating basis.

#include <assert.h>
#include <string.h>
#include "blockmemshell/memory.h"
#include "scip/cons_linear.h"
#include "scip/debug.h"
#include "scip/heur_padm.h"
#include "scip/heuristics.h"
#include "scip/pub_cons.h"
#include "scip/pub_tree.h"
#include "scip/pub_heur.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_select.h"
#include "scip/pub_sol.h"
#include "scip/pub_var.h"
#include "scip/scipdefplugins.h"
#include "scip/scip_branch.h"
#include "scip/scip_cons.h"
#include "scip/scip_copy.h"
#include "scip/scip_dcmp.h"
#include "scip/scip_general.h"
#include "scip/scip_heur.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_nodesel.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_randnumgen.h"
#include "scip/scip_sol.h"
#include "scip/scip_solve.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_table.h"
#include "scip/scip_timing.h"
#include "scip/scip_tree.h"
#include "scip/scip_var.h"

Go to the source code of this file.

## Data Structures

struct  Block

struct  set

struct  blockinfo

## Macros

#define HEUR_DESC   "penalty alternating direction method primal heuristic"

#define HEUR_DISPCHAR   SCIP_HEURDISPCHAR_LNS

#define HEUR_PRIORITY   70000

#define HEUR_FREQ   0

#define HEUR_FREQOFS   0

#define HEUR_MAXDEPTH   -1

#define HEUR_TIMING   SCIP_HEURTIMING_BEFORENODE | SCIP_HEURTIMING_AFTERNODE

#define HEUR_USESSUBSCIP   TRUE

#define COUPLINGSIZE   3

#define DEFAULT_MINNODES   50LL

#define DEFAULT_MAXNODES   5000LL

#define DEFAULT_NODEFAC   0.8

#define DEFAULT_PENALTYIT   100

#define DEFAULT_GAP   2.0

## Typedefs

typedef struct Problem PROBLEM

typedef struct Block BLOCK

typedef struct set SET

typedef struct blockinfo BLOCKINFO

## Functions

static SCIP_DECL_HASHKEYEQ (indexesEqual)

static SCIP_DECL_HASHKEYVAL (indexesHashval)

static SCIP_RETCODE initBlock (PROBLEM *problem)

static SCIP_RETCODE freeBlock (BLOCK *block)

static SCIP_RETCODE initProblem (SCIP *scip, PROBLEM **problem, int nblocks)

static SCIP_RETCODE freeProblem (PROBLEM **problem, int nblocks)

static SCIP_RETCODE createSubscip (SCIP *scip, SCIP **subscip)

static SCIP_RETCODE copyToSubscip (SCIP *scip, SCIP *subscip, const char *name, SCIP_CONS **conss, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, int nconss, SCIP_Bool useorigprob, SCIP_Bool *success)

static SCIP_RETCODE blockCreateSubscip (BLOCK *block, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_CONS **conss, int nconss, SCIP_Bool useorigprob, SCIP_Bool *success)

static SCIP_RETCODE createAndSplitProblem (SCIP *scip, SCIP_CONS **sortedconss, int nconss, int *consssize, int nblocks, PROBLEM **problem, SCIP_Bool useorigprob, SCIP_Bool *success)

static SCIP_RETCODE assignLinking (SCIP *scip, SCIP_DECOMP *newdecomp, SCIP_VAR **vars, SCIP_CONS **sortedconss, int *varlabels, int *conslabels, int nvars, int nconss, int nlinkconss)

static SCIP_RETCODE reuseSolution (SCIP *subscip, BLOCK *block)

static SCIP_RETCODE reoptimize (SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *sol, SCIP_VAR **vars, int nvars, SCIP_VAR **linkvars, int nlinkvars, SCIP_SOL **newsol, SCIP_Bool *success)

static SCIP_RETCODE scalePenalties (PROBLEM *problem, SET *linkvartoblocks, SET *blocktolinkvars, SCIP_HASHTABLE *htable, SCIP_Real maxpenalty)

static SCIP_RETCODE getTimeLeft (SCIP *scip, SCIP_Real *time)

## ◆ HEUR_NAME

Definition at line 84 of file heur_padm.c.

Referenced by SCIP_DECL_HEURCOPY(), SCIP_DECL_HEUREXEC(), and SCIPincludeHeurPADM().

## ◆ HEUR_DESC

 #define HEUR_DESC   "penalty alternating direction method primal heuristic"

Definition at line 85 of file heur_padm.c.

## ◆ HEUR_DISPCHAR

 #define HEUR_DISPCHAR   SCIP_HEURDISPCHAR_LNS

Definition at line 86 of file heur_padm.c.

## ◆ HEUR_PRIORITY

 #define HEUR_PRIORITY   70000

Definition at line 87 of file heur_padm.c.

## ◆ HEUR_FREQ

 #define HEUR_FREQ   0

Definition at line 88 of file heur_padm.c.

## ◆ HEUR_FREQOFS

 #define HEUR_FREQOFS   0

Definition at line 89 of file heur_padm.c.

## ◆ HEUR_MAXDEPTH

 #define HEUR_MAXDEPTH   -1

Definition at line 90 of file heur_padm.c.

## ◆ HEUR_TIMING

 #define HEUR_TIMING   SCIP_HEURTIMING_BEFORENODE | SCIP_HEURTIMING_AFTERNODE

Definition at line 91 of file heur_padm.c.

## ◆ HEUR_USESSUBSCIP

 #define HEUR_USESSUBSCIP   TRUE

does the heuristic use a secondary SCIP instance?

Definition at line 92 of file heur_padm.c.

## ◆ COUPLINGSIZE

 #define COUPLINGSIZE   3

Definition at line 94 of file heur_padm.c.

Referenced by reuseSolution(), and SCIP_DECL_HEUREXEC().

## ◆ DEFAULT_MINNODES

 #define DEFAULT_MINNODES   50LL

Definition at line 95 of file heur_padm.c.

## ◆ DEFAULT_MAXNODES

 #define DEFAULT_MAXNODES   5000LL

Definition at line 96 of file heur_padm.c.

## ◆ DEFAULT_NODEFAC

 #define DEFAULT_NODEFAC   0.8

Definition at line 97 of file heur_padm.c.

Definition at line 98 of file heur_padm.c.

## ◆ DEFAULT_PENALTYIT

 #define DEFAULT_PENALTYIT   100

Definition at line 99 of file heur_padm.c.

## ◆ DEFAULT_GAP

 #define DEFAULT_GAP   2.0

Definition at line 100 of file heur_padm.c.

## ◆ PROBLEM

 typedef struct Problem PROBLEM

data related to one problem (see below)

Definition at line 107 of file heur_padm.c.

## ◆ BLOCK

 typedef struct Block BLOCK

data related to one block

## ◆ SET

 typedef struct set SET

set data structure

## ◆ BLOCKINFO

 typedef struct blockinfo BLOCKINFO

data of one linking variable related to one block

## ◆ SCIP_DECL_HASHKEYEQ()

 static SCIP_DECL_HASHKEYEQ ( indexesEqual )
static

returns TRUE iff both keys are equal

Definition at line 157 of file heur_padm.c.

References blockinfo::block, FALSE, blockinfo::linkvaridx, blockinfo::otherblock, and TRUE.

## ◆ SCIP_DECL_HASHKEYVAL()

 static SCIP_DECL_HASHKEYVAL ( indexesHashval )
static

returns the hash value of the key

Definition at line 174 of file heur_padm.c.

## ◆ initBlock()

 static SCIP_RETCODE initBlock ( PROBLEM * problem )
static

initializes one block

Parameters
 problem problem structure

Definition at line 206 of file heur_padm.c.

Referenced by createAndSplitProblem().

## ◆ freeBlock()

 static SCIP_RETCODE freeBlock ( BLOCK * block )
static

frees component structure

Parameters
 block block structure

Definition at line 235 of file heur_padm.c.

Referenced by freeProblem().

## ◆ initProblem()

 static SCIP_RETCODE initProblem ( SCIP * scip, PROBLEM ** problem, int nblocks )
static

initializes subproblem structure

Parameters
 scip SCIP data structure problem pointer to problem structure nblocks number of blocks

Definition at line 258 of file heur_padm.c.

Referenced by createAndSplitProblem().

## ◆ freeProblem()

 static SCIP_RETCODE freeProblem ( PROBLEM ** problem, int nblocks )
static

frees subproblem structure

Parameters
 problem pointer to problem to free nblocks number of blocks in decomposition

Definition at line 288 of file heur_padm.c.

Referenced by createAndSplitProblem(), and SCIP_DECL_HEUREXEC().

## ◆ createSubscip()

 static SCIP_RETCODE createSubscip ( SCIP * scip, SCIP ** subscip )
static

creates a sub-SCIP for the given variables and constraints

Parameters
 scip main SCIP data structure subscip pointer to store created sub-SCIP

Definition at line 324 of file heur_padm.c.

Referenced by blockCreateSubscip().

## ◆ copyToSubscip()

 static SCIP_RETCODE copyToSubscip ( SCIP * scip, SCIP * subscip, const char * name, SCIP_CONS ** conss, SCIP_HASHMAP * varmap, SCIP_HASHMAP * consmap, int nconss, SCIP_Bool useorigprob, SCIP_Bool * success )
static

copies the given constraints and the corresponding variables to the given sub-SCIP

Parameters
 scip source SCIP subscip target SCIP name name for copied problem conss constraints to copy varmap hashmap used for the copy process of variables consmap hashmap used for the copy process of constraints nconss number of constraints to copy useorigprob do we use the original problem? success pointer to store whether copying was successful

Definition at line 372 of file heur_padm.c.

Referenced by blockCreateSubscip().

## ◆ blockCreateSubscip()

 static SCIP_RETCODE blockCreateSubscip ( BLOCK * block, SCIP_HASHMAP * varmap, SCIP_HASHMAP * consmap, SCIP_CONS ** conss, int nconss, SCIP_Bool useorigprob, SCIP_Bool * success )
static

creates the subscip for a given block

Parameters
 block block structure varmap variable hashmap used to improve performance consmap constraint hashmap used to improve performance conss constraints contained in this block nconss number of constraints contained in this block useorigprob do we use the original problem? success pointer to store whether the copying process was successful

Definition at line 433 of file heur_padm.c.

Referenced by createAndSplitProblem().

## ◆ createAndSplitProblem()

 static SCIP_RETCODE createAndSplitProblem ( SCIP * scip, SCIP_CONS ** sortedconss, int nconss, int * consssize, int nblocks, PROBLEM ** problem, SCIP_Bool useorigprob, SCIP_Bool * success )
static

creates problem structure and split it into blocks

Parameters
 scip SCIP data structure sortedconss array of (checked) constraints sorted by blocks nconss number of constraints consssize number of constraints per block (and border at index 0) nblocks number of blocks problem pointer to store problem structure useorigprob do we use the original problem? success pointer to store whether the process was successful

Definition at line 505 of file heur_padm.c.

Referenced by SCIP_DECL_HEUREXEC().

 static SCIP_RETCODE assignLinking ( SCIP * scip, SCIP_DECOMP * newdecomp, SCIP_VAR ** vars, SCIP_CONS ** sortedconss, int * varlabels, int * conslabels, int nvars, int nconss, int nlinkconss )
static

copies labels to newdecomp and assigns linking constraints if possible

Parameters
 scip SCIP data structure newdecomp decomposition with (partially) assigned linking constraints vars array of variables sortedconss sorted array of constraints varlabels array of variable labels conslabels sorted array of constraint labels nvars number of variables nconss number of constraints nlinkconss number of linking constraints

Definition at line 573 of file heur_padm.c.

Referenced by SCIP_DECL_HEUREXEC().

## ◆ reuseSolution()

 static SCIP_RETCODE reuseSolution ( SCIP * subscip, BLOCK * block )
static

computes feasible solution from last stored solution of the block

Parameters
 subscip SCIP data structure block block structure

Definition at line 614 of file heur_padm.c.

Referenced by SCIP_DECL_HEUREXEC().

## ◆ reoptimize()

 static SCIP_RETCODE reoptimize ( SCIP * scip, SCIP_HEUR * heur, SCIP_SOL * sol, SCIP_VAR ** vars, int nvars, SCIP_VAR ** linkvars, int nlinkvars, SCIP_SOL ** newsol, SCIP_Bool * success )
static

reoptimizes the heuristic solution with original objective function

Since the main algorithm of padm ignores the objective function, this method can be called to obtain better solutions. It copies the main scip, fixes the linking variables at the values of the already found solution and solves the new problem with small limits.

Parameters
 scip SCIP data structure heur pointer to heuristic sol heuristic solution vars pointer to variables nvars number of variables linkvars pointer to linking variables nlinkvars number of linking variables newsol pointer to store improved solution success pointer to store whether reoptimization was successful

Definition at line 712 of file heur_padm.c.

Referenced by SCIP_DECL_HASHKEYVAL(), and SCIP_DECL_HEUREXEC().

## ◆ scalePenalties()

 static SCIP_RETCODE scalePenalties ( PROBLEM * problem, SET * linkvartoblocks, SET * blocktolinkvars, SCIP_HASHTABLE * htable, SCIP_Real maxpenalty )
static

rescales the penalty parameters

A sigmoid function is a function with an "S"-shaped graph, e.g. S(x) = x/(1+|x|). In order to avoid numerical instabilities due to large penalty parameters we rescale them using the sigmoid function S(x) = (x - shift)/(flatness + |x - shift|) * (range/2) + offset. The parameters are mapped into the more controllable interval [lowestslack, range + lowestslack].

Parameters
 problem block structure linkvartoblocks linking variable to blocks set blocktolinkvars block to linking variable set htable hashtable containing blockinfo maxpenalty maximum penalty parameter

Definition at line 875 of file heur_padm.c.

Referenced by SCIP_DECL_HEUREXEC().

## ◆ getTimeLeft()

 static SCIP_RETCODE getTimeLeft ( SCIP * scip, SCIP_Real * time )
static

returns the available time limit that is left

Parameters
 scip SCIP data structure time pointer to store remaining time

Definition at line 938 of file heur_padm.c.

Referenced by SCIP_DECL_HEUREXEC().

## ◆ SCIP_DECL_HEURCOPY()

static

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

Definition at line 965 of file heur_padm.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurPADM().