Scippy

GCG

Branch-and-Price & Column Generation for Everyone

Data Structures | Macros | Functions
solver_mip.c File Reference

Detailed Description

pricing solver solving the pricing problem as a sub-MIP, using SCIP

Author
Gerald Gamrath
Martin Bergner
Christian Puchert

Definition in file solver_mip.c.

#include <assert.h>
#include <string.h>
#include "solver_mip.h"
#include "scip/cons_linear.h"
#include "scip/cons_knapsack.h"
#include "gcg.h"
#include "pricer_gcg.h"
#include "pub_solver.h"
#include "scip/scipdefplugins.h"
#include "pub_gcgcol.h"

Go to the source code of this file.

Data Structures

struct  GCG_SolverData
 

Macros

#define SOLVER_NAME   "mip"
 
#define SOLVER_DESC   "pricing solver solving the pricing problem as a sub-MIP, using SCIP"
 
#define SOLVER_PRIORITY   0
 
#define SOLVER_HEURENABLED   TRUE
 
#define SOLVER_EXACTENABLED   TRUE
 
#define DEFAULT_CHECKSOLS   TRUE
 
#define DEFAULT_STARTNODELIMIT   1000LL
 
#define DEFAULT_STARTSTALLNODELIMIT   100LL
 
#define DEFAULT_STARTGAPLIMIT   0.2
 
#define DEFAULT_STARTSOLLIMIT   10
 
#define DEFAULT_NODELIMITFAC   1.0
 
#define DEFAULT_STALLNODELIMITFAC   1.0
 
#define DEFAULT_GAPLIMITFAC   0.8
 
#define DEFAULT_SOLLIMITFAC   1.0
 
#define DEFAULT_SETTINGSFILE   "-"
 
#define solverInitMip   NULL
 
#define solverExitMip   NULL
 
#define solverUpdateMip   NULL
 

Functions

static SCIP_RETCODE createColumnFromRay (SCIP *pricingprob, int probnr, GCG_COL **newcol)
 
static SCIP_RETCODE resolvePricingWithoutPresolving (SCIP *pricingprob)
 
static SCIP_RETCODE checkSolNew (SCIP *pricingprob, SCIP_SOL **sols, int idx, SCIP_Bool *isnew)
 
static GCG_PRICINGSTATUS getPricingstatus (SCIP *pricingprob)
 
static SCIP_Bool solutionHasInfiniteValue (SCIP *pricingprob, SCIP_SOL *sol)
 
static SCIP_RETCODE getColumnsFromPricingprob (SCIP *scip, SCIP *pricingprob, int probnr, SCIP_Bool checksols)
 
static SCIP_RETCODE solveProblem (SCIP *scip, SCIP *pricingprob, int probnr, GCG_SOLVERDATA *solverdata, SCIP_Real *lowerbound, GCG_PRICINGSTATUS *status)
 
static GCG_DECL_SOLVERFREE (solverFreeMip)
 
static GCG_DECL_SOLVERINITSOL (solverInitsolMip)
 
static GCG_DECL_SOLVEREXITSOL (solverExitsolMip)
 
static GCG_DECL_SOLVERSOLVE (solverSolveMip)
 
static GCG_DECL_SOLVERSOLVEHEUR (solverSolveHeurMip)
 
SCIP_RETCODE GCGincludeSolverMip (SCIP *scip)
 

Macro Definition Documentation

◆ SOLVER_NAME

#define SOLVER_NAME   "mip"

Definition at line 51 of file solver_mip.c.

◆ SOLVER_DESC

#define SOLVER_DESC   "pricing solver solving the pricing problem as a sub-MIP, using SCIP"

Definition at line 52 of file solver_mip.c.

◆ SOLVER_PRIORITY

#define SOLVER_PRIORITY   0

Definition at line 53 of file solver_mip.c.

◆ SOLVER_HEURENABLED

#define SOLVER_HEURENABLED   TRUE

indicates whether the heuristic solving method of the solver should be enabled

Definition at line 54 of file solver_mip.c.

◆ SOLVER_EXACTENABLED

#define SOLVER_EXACTENABLED   TRUE

indicates whether the exact solving method of the solver should be enabled

Definition at line 55 of file solver_mip.c.

◆ DEFAULT_CHECKSOLS

#define DEFAULT_CHECKSOLS   TRUE

should solutions be checked extensively

Definition at line 57 of file solver_mip.c.

◆ DEFAULT_STARTNODELIMIT

#define DEFAULT_STARTNODELIMIT   1000LL

start node limit for heuristic pricing

Definition at line 58 of file solver_mip.c.

◆ DEFAULT_STARTSTALLNODELIMIT

#define DEFAULT_STARTSTALLNODELIMIT   100LL

start stalling node limit for heuristic pricing

Definition at line 59 of file solver_mip.c.

◆ DEFAULT_STARTGAPLIMIT

#define DEFAULT_STARTGAPLIMIT   0.2

start gap limit for heuristic pricing

Definition at line 60 of file solver_mip.c.

◆ DEFAULT_STARTSOLLIMIT

#define DEFAULT_STARTSOLLIMIT   10

start solution limit for heuristic pricing

Definition at line 61 of file solver_mip.c.

◆ DEFAULT_NODELIMITFAC

#define DEFAULT_NODELIMITFAC   1.0

factor by which to increase node limit for heuristic pricing (1.0: add start limit)

Definition at line 62 of file solver_mip.c.

◆ DEFAULT_STALLNODELIMITFAC

#define DEFAULT_STALLNODELIMITFAC   1.0

factor by which to increase stalling node limit for heuristic pricing (1.0: add start limit)

Definition at line 63 of file solver_mip.c.

◆ DEFAULT_GAPLIMITFAC

#define DEFAULT_GAPLIMITFAC   0.8

factor by which to decrease gap limit for heuristic pricing (1.0: subtract start limit)

Definition at line 64 of file solver_mip.c.

◆ DEFAULT_SOLLIMITFAC

#define DEFAULT_SOLLIMITFAC   1.0

factor by which to increase solution limit for heuristic pricing (1.0: add start limit)

Definition at line 65 of file solver_mip.c.

◆ DEFAULT_SETTINGSFILE

#define DEFAULT_SETTINGSFILE   "-"

settings file to be applied in pricing problems

Definition at line 66 of file solver_mip.c.

◆ solverInitMip

#define solverInitMip   NULL

initialization method of pricing solver (called after problem was transformed and solver is active)

Definition at line 501 of file solver_mip.c.

◆ solverExitMip

#define solverExitMip   NULL

deinitialization method of pricing solver (called before transformed problem is freed and solver is active)

Definition at line 504 of file solver_mip.c.

◆ solverUpdateMip

#define solverUpdateMip   NULL

Definition at line 561 of file solver_mip.c.

Function Documentation

◆ createColumnFromRay()

static SCIP_RETCODE createColumnFromRay ( SCIP *  pricingprob,
int  probnr,
GCG_COL **  newcol 
)
static

extracts ray from pricing problem

Parameters
pricingprobpricing problem SCIP data structure
probnrproblem number
newcolcolumn pointer to store new column

Definition at line 99 of file solver_mip.c.

References GCGcreateGcgCol().

Referenced by solveProblem().

◆ resolvePricingWithoutPresolving()

static SCIP_RETCODE resolvePricingWithoutPresolving ( SCIP *  pricingprob)
static

solves the pricing problem again without presolving

Parameters
pricingprobpricing problem to solve again

Definition at line 156 of file solver_mip.c.

Referenced by solveProblem().

◆ checkSolNew()

static SCIP_RETCODE checkSolNew ( SCIP *  pricingprob,
SCIP_SOL **  sols,
int  idx,
SCIP_Bool *  isnew 
)
static

checks whether the given solution is equal to one of the former solutions in the sols array

Parameters
pricingprobpricing problem SCIP data structure
solsarray of solutions
idxindex of the solution
isnewpointer to store whether the solution is new

Definition at line 173 of file solver_mip.c.

Referenced by getColumnsFromPricingprob().

◆ getPricingstatus()

static GCG_PRICINGSTATUS getPricingstatus ( SCIP *  pricingprob)
static

get the status of the pricing problem

Parameters
pricingprobpricing problem SCIP data structure

Definition at line 232 of file solver_mip.c.

References GCG_PRICINGSTATUS_INFEASIBLE, GCG_PRICINGSTATUS_OPTIMAL, GCG_PRICINGSTATUS_SOLVERLIMIT, GCG_PRICINGSTATUS_UNBOUNDED, and GCG_PRICINGSTATUS_UNKNOWN.

Referenced by solveProblem().

◆ solutionHasInfiniteValue()

static SCIP_Bool solutionHasInfiniteValue ( SCIP *  pricingprob,
SCIP_SOL *  sol 
)
static

check whether a column contains an infinite solution value

Parameters
pricingprobpricing problem SCIP data structure
solsolution to be checked

Definition at line 294 of file solver_mip.c.

Referenced by getColumnsFromPricingprob().

◆ getColumnsFromPricingprob()

static SCIP_RETCODE getColumnsFromPricingprob ( SCIP *  scip,
SCIP *  pricingprob,
int  probnr,
SCIP_Bool  checksols 
)
static

transforms feasible solutions of the pricing problem into columns

Parameters
scipmaster problem SCIP data structure
pricingprobpricing problem SCIP data structure
probnrproblem number
checksolsshould solutions be checked extensively

Definition at line 316 of file solver_mip.c.

References checkSolNew(), GCGcreateGcgColFromSol(), GCGpricerAddCol(), and solutionHasInfiniteValue().

Referenced by solveProblem().

◆ solveProblem()

static SCIP_RETCODE solveProblem ( SCIP *  scip,
SCIP *  pricingprob,
int  probnr,
GCG_SOLVERDATA *  solverdata,
SCIP_Real *  lowerbound,
GCG_PRICINGSTATUS *  status 
)
static

solves the given pricing problem as a sub-SCIP

Parameters
scipmaster problem SCIP data structure
pricingprobpricing problem SCIP data structure
probnrproblem number
solverdatasolver data structure
lowerboundpointer to store lower bound
statuspointer to store pricing problem status

Definition at line 386 of file solver_mip.c.

References GCG_SolverData::checksols, createColumnFromRay(), GCG_PRICINGSTATUS_INFEASIBLE, GCG_PRICINGSTATUS_NOTAPPLICABLE, GCG_PRICINGSTATUS_OPTIMAL, GCG_PRICINGSTATUS_SOLVERLIMIT, GCG_PRICINGSTATUS_UNBOUNDED, GCG_PRICINGSTATUS_UNKNOWN, GCGpricerAddCol(), getColumnsFromPricingprob(), getPricingstatus(), and resolvePricingWithoutPresolving().

Referenced by GCG_DECL_SOLVERSOLVE(), and GCG_DECL_SOLVERSOLVEHEUR().

◆ GCG_DECL_SOLVERFREE()

static GCG_DECL_SOLVERFREE ( solverFreeMip  )
static

destructor of pricing solver to free user data (called when SCIP is exiting)

Definition at line 483 of file solver_mip.c.

References GCGsolverGetData(), and GCGsolverSetData().

◆ GCG_DECL_SOLVERINITSOL()

static GCG_DECL_SOLVERINITSOL ( solverInitsolMip  )
static

solving process initialization method of pricing solver (called when branch and bound process is about to begin)

Definition at line 508 of file solver_mip.c.

References GCG_SolverData::curgaplimit, GCG_SolverData::curnodelimit, GCG_SolverData::cursollimit, GCG_SolverData::curstallnodelimit, GCGgetNPricingprobs(), GCGmasterGetOrigprob(), GCGsolverGetData(), GCG_SolverData::startgaplimit, GCG_SolverData::startnodelimit, GCG_SolverData::startsollimit, and GCG_SolverData::startstallnodelimit.

◆ GCG_DECL_SOLVEREXITSOL()

static GCG_DECL_SOLVEREXITSOL ( solverExitsolMip  )
static

solving process deinitialization method of pricing solver (called before branch and bound process data is freed)

Definition at line 540 of file solver_mip.c.

References GCG_SolverData::curgaplimit, GCG_SolverData::curnodelimit, GCG_SolverData::cursollimit, GCG_SolverData::curstallnodelimit, GCGgetNPricingprobs(), GCGmasterGetOrigprob(), and GCGsolverGetData().

◆ GCG_DECL_SOLVERSOLVE()

static GCG_DECL_SOLVERSOLVE ( solverSolveMip  )
static

solving method for pricing solver which solves the pricing problem to optimality

Definition at line 565 of file solver_mip.c.

References GCGsolverGetData(), GCG_SolverData::settingsfile, and solveProblem().

◆ GCG_DECL_SOLVERSOLVEHEUR()

static GCG_DECL_SOLVERSOLVEHEUR ( solverSolveHeurMip  )
static

heuristic solving method of mip solver

Definition at line 602 of file solver_mip.c.

References GCG_SolverData::curgaplimit, GCG_SolverData::curnodelimit, GCG_SolverData::cursollimit, GCG_SolverData::curstallnodelimit, GCG_SolverData::gaplimitfac, GCG_PRICINGSTATUS_UNKNOWN, GCGsolverGetData(), GCG_SolverData::nodelimitfac, GCG_SolverData::sollimitfac, solveProblem(), GCG_SolverData::stallnodelimitfac, GCG_SolverData::startgaplimit, GCG_SolverData::startnodelimit, GCG_SolverData::startsollimit, and GCG_SolverData::startstallnodelimit.

◆ GCGincludeSolverMip()

SCIP_RETCODE GCGincludeSolverMip ( SCIP *  scip)

creates the mip solver for pricing problems and includes it in GCG

Parameters
scipSCIP data structure

Definition at line 677 of file solver_mip.c.

References GCG_SolverData::checksols, DEFAULT_CHECKSOLS, DEFAULT_GAPLIMITFAC, DEFAULT_NODELIMITFAC, DEFAULT_SETTINGSFILE, DEFAULT_SOLLIMITFAC, DEFAULT_STALLNODELIMITFAC, DEFAULT_STARTGAPLIMIT, DEFAULT_STARTNODELIMIT, DEFAULT_STARTSOLLIMIT, DEFAULT_STARTSTALLNODELIMIT, GCG_SolverData::gaplimitfac, GCGmasterGetOrigprob(), GCGpricerIncludeSolver(), GCG_SolverData::nodelimitfac, GCG_SolverData::settingsfile, GCG_SolverData::sollimitfac, SOLVER_DESC, SOLVER_EXACTENABLED, SOLVER_HEURENABLED, SOLVER_NAME, SOLVER_PRIORITY, solverExitMip, solverInitMip, solverUpdateMip, GCG_SolverData::stallnodelimitfac, GCG_SolverData::startgaplimit, GCG_SolverData::startnodelimit, GCG_SolverData::startsollimit, and GCG_SolverData::startstallnodelimit.

Referenced by GCGincludeMasterPlugins().