An iterative rounding heuristic, tailored for nonconvex MINLPs. More...

#include <CouenneIterativeRounding.hpp>

Inheritance diagram for Couenne::CouenneIterativeRounding:

Collaboration diagram for Couenne::CouenneIterativeRounding:

Public Member Functions
	CouenneIterativeRounding ()
	Default constructor. More...

	CouenneIterativeRounding (Bonmin::OsiTMINLPInterface nlp, OsiSolverInterface cinlp, CouenneProblem *couenne, Ipopt::SmartPtr< Ipopt::OptionsList > options)
	Constructor with model and Couenne problems. More...

	CouenneIterativeRounding (const CouenneIterativeRounding &other)
	Copy constructor. More...

virtual	~CouenneIterativeRounding ()
	Destructor. More...

virtual CbcHeuristic *	clone () const
	Clone. More...

CouenneIterativeRounding &	operator= (const CouenneIterativeRounding &rhs)
	Assignment operator. More...

void	setNlp (Bonmin::OsiTMINLPInterface nlp, OsiSolverInterface cinlp)
	Set the minlp solver. More...

void	setCouenneProblem (CouenneProblem *couenne)
	Set the couenne problem to use. More...

void	resetModel (CbcModel *model)
	Does nothing. More...

int	solution (double &objectiveValue, double *newSolution)
	Run heuristic, return 1 if a better solution than the one passed is found and 0 otherwise. More...

void	setMaxRoundingIter (int value)
	Set maximum number of iterations for each rounding phase. More...

void	setMaxFirPoints (int value)
	Set maximum number of points that we try to round in F-IR. More...

void	setMaxTime (double value)
	Set maximum CPU time for the heuristic at each node. More...

void	setMaxTimeFirstCall (double value)
	Set maximum CPU time for the heuristic at the root node only. More...

void	setOmega (double value)
	Set the value for omega, the multiplicative factor for the minimum log-barrier parameter mu used by F-IR whenever we need to generate a new NLP feasible point (in the interior of the feasible region) More...

void	setBaseLbRhs (int value)
	Set the base value for the rhs of the local branching constraint in the I-IR heuristic. More...

void	setAggressiveness (int value)
	Set aggressiveness of heuristic. More...

Static Public Member Functions
static void	registerOptions (Ipopt::SmartPtr< Bonmin::RegisteredOptions >)
	initialize options to be read later More...

Private Member Functions
bool	areEqual (double a, double b)
	Check if two double precision numbers are equal, up to some tolerance. More...

int	feasibilityIR (double &objectiveValue, double *newSolution)

int	improvementIR (double &objectiveValue, double newSolution, const double startingSolution)

void	setMilp ()
	Set the milp solver at the root. More...

int	computeIntAtBound (const double *x)
	Compute number of integer variables at one of their bounds at a given point x. More...

int	computeIntAtBound (const double *x, double &avgBoundSize)
	Compute number of integer variables at one of their bounds at a given point x and average distance between the bounds of variables at one of their bounds. More...

void	writeLB (OsiRowCut &cut, const double *x, char sense, double rhs)
	Write down a local branching constraint, as an OsiRowCut. More...

int	branchToCut (const double x, OsiSolverInterface solver, std::vector< int > &previousBranches)
	Branch on a random variable to cut given solution; returns var index. More...

bool	solveMilp (OsiSolverInterface *milp, double maxTime)
	Solve the MILP contained in milp to feasibility, or report failure. More...

Private Attributes
Bonmin::OsiTMINLPInterface *	nlp_
	Pointer to a dynamic nlp solver interface. More...

OsiSolverInterface *	cinlp_
	Pointer to the original NLP solver interface. More...

OsiClpSolverInterface *	milp_
	Pointer to a milp solver interface. More...

int	maxRoundingIter_
	Maximum number of iterations in the main loop. More...

int	maxFirPoints_
	Maximum number of iterations in the outer loop for feasibility. More...

double	maxTime_
	Max CPU time to run the heuristic. More...

double	maxTimeFirstCall_
	Max CPU time to run the heuristic when no other solution is known. More...

int	numInitialRows_
	Number of rows in the original convexification. More...

int	numSol_
	Number of solutions last time the heuristic was called. More...

int	numIntegers_
	Number of integer variables in the original model. More...

double *	colLower_
	Pointer to original column lower and upper bounds of the reformulated problem, i.e. More...

double *	colUpper_

double *	colLowerNlp_
	Pointer to column lower and upper bounds of the original problem, i.e. More...

double *	colUpperNlp_

CbcHeuristic **	heuristics_
	Heuristics for the MILP. More...

int	numHeuristics_

double	startTime_
	Starting time for the heuristics. More...

double	endTime_
	Maximum allowed time for current run. More...

double	omega_
	Multiplication factor for log barrier parameter in F-IR; see in the paper. More...

int	baseLbRhs_
	Base value for the rhs of the local branching constraint it I-IR. More...

CouenneProblem *	couenne_
	Pointer to a couenne representation of the problem. More...

Detailed Description

An iterative rounding heuristic, tailored for nonconvex MINLPs.

It solves a sequence of MILPs and NLPs for a given number of iterations, or until a better solution is found.

Definition at line 36 of file CouenneIterativeRounding.hpp.

Constructor & Destructor Documentation

Couenne::CouenneIterativeRounding::CouenneIterativeRounding ( )

Default constructor.

Definition at line 26 of file CouenneIterativeRounding.cpp.

Couenne::CouenneIterativeRounding::CouenneIterativeRounding	(	Bonmin::OsiTMINLPInterface *	nlp,
		OsiSolverInterface *	cinlp,
		CouenneProblem *	couenne,
		Ipopt::SmartPtr< Ipopt::OptionsList >	options
	)

Constructor with model and Couenne problems.

Definition at line 39 of file CouenneIterativeRounding.cpp.

Couenne::CouenneIterativeRounding::CouenneIterativeRounding ( const CouenneIterativeRounding & other )

Copy constructor.

Definition at line 82 of file CouenneIterativeRounding.cpp.

Couenne::CouenneIterativeRounding::~CouenneIterativeRounding ( )

virtual

Destructor.

Definition at line 182 of file CouenneIterativeRounding.cpp.

Member Function Documentation

CbcHeuristic * Couenne::CouenneIterativeRounding::clone ( ) const

virtual

Clone.

Definition at line 130 of file CouenneIterativeRounding.cpp.

CouenneIterativeRounding & Couenne::CouenneIterativeRounding::operator= ( const CouenneIterativeRounding & rhs )

Assignment operator.

Definition at line 135 of file CouenneIterativeRounding.cpp.

void Couenne::CouenneIterativeRounding::setNlp	(	Bonmin::OsiTMINLPInterface *	nlp,
		OsiSolverInterface *	cinlp
	)

Set the minlp solver.

Definition at line 199 of file CouenneIterativeRounding.cpp.

void Couenne::CouenneIterativeRounding::setCouenneProblem ( CouenneProblem * couenne )

inline

Set the couenne problem to use.

Definition at line 62 of file CouenneIterativeRounding.hpp.

void Couenne::CouenneIterativeRounding::resetModel ( CbcModel * model )

inline

Does nothing.

Definition at line 67 of file CouenneIterativeRounding.hpp.

int Couenne::CouenneIterativeRounding::solution	(	double &	objectiveValue,
		double *	newSolution
	)

Run heuristic, return 1 if a better solution than the one passed is found and 0 otherwise.

objectiveValue Best known solution in input and value of solution found in output newSolution Solution found by heuristic.

Definition at line 345 of file CouenneIterativeRounding.cpp.

void Couenne::CouenneIterativeRounding::setMaxRoundingIter ( int value )

inline

Set maximum number of iterations for each rounding phase.

Definition at line 79 of file CouenneIterativeRounding.hpp.

void Couenne::CouenneIterativeRounding::setMaxFirPoints ( int value )

inline

Set maximum number of points that we try to round in F-IR.

Definition at line 84 of file CouenneIterativeRounding.hpp.

void Couenne::CouenneIterativeRounding::setMaxTime ( double value )

inline

Set maximum CPU time for the heuristic at each node.

Definition at line 89 of file CouenneIterativeRounding.hpp.

void Couenne::CouenneIterativeRounding::setMaxTimeFirstCall ( double value )

inline

Set maximum CPU time for the heuristic at the root node only.

Definition at line 94 of file CouenneIterativeRounding.hpp.

void Couenne::CouenneIterativeRounding::setOmega ( double value )

inline

Set the value for omega, the multiplicative factor for the minimum log-barrier parameter mu used by F-IR whenever we need to generate a new NLP feasible point (in the interior of the feasible region)

Definition at line 102 of file CouenneIterativeRounding.hpp.

void Couenne::CouenneIterativeRounding::setBaseLbRhs ( int value )

inline

Set the base value for the rhs of the local branching constraint in the I-IR heuristic.

The actual rhs is then computed depending on current variable bounds

Definition at line 109 of file CouenneIterativeRounding.hpp.

void Couenne::CouenneIterativeRounding::setAggressiveness ( int value )

Set aggressiveness of heuristic.

Three levels, that sets various parameters accordingly.

The levels are: 0: maxRoundingIter = 5, maxTimeFirstCall = 300, maxFirPoints = 5, maxTime = 60 1: maxRoundingIter = 10, maxTimeFirstCall = 300, maxFirPoints = 5, maxTime = 120 2: maxRoundingIter = 20, maxTimeFirstCall = 1000, maxFirPoints = 5, maxTime = 300

Definition at line 319 of file CouenneIterativeRounding.cpp.

void Couenne::CouenneIterativeRounding::registerOptions ( Ipopt::SmartPtr< Bonmin::RegisteredOptions > roptions )

static

initialize options to be read later

Definition at line 1175 of file CouenneIterativeRounding.cpp.

bool Couenne::CouenneIterativeRounding::areEqual	(	double	a,
		double	b
	)

inlineprivate

Check if two double precision numbers are equal, up to some tolerance.

Definition at line 181 of file CouenneIterativeRounding.hpp.

int Couenne::CouenneIterativeRounding::feasibilityIR	(	double &	objectiveValue,
		double *	newSolution
	)

private

Definition at line 406 of file CouenneIterativeRounding.cpp.

int Couenne::CouenneIterativeRounding::improvementIR	(	double &	objectiveValue,
		double *	newSolution,
		const double *	startingSolution
	)

private

Definition at line 712 of file CouenneIterativeRounding.cpp.

void Couenne::CouenneIterativeRounding::setMilp ( )

private

Set the milp solver at the root.

Definition at line 219 of file CouenneIterativeRounding.cpp.

int Couenne::CouenneIterativeRounding::computeIntAtBound ( const double * x )

private

Compute number of integer variables at one of their bounds at a given point x.

Definition at line 1019 of file CouenneIterativeRounding.cpp.

int Couenne::CouenneIterativeRounding::computeIntAtBound	(	const double *	x,
		double &	avgBoundSize
	)

private

Compute number of integer variables at one of their bounds at a given point x and average distance between the bounds of variables at one of their bounds.

Definition at line 1031 of file CouenneIterativeRounding.cpp.

void Couenne::CouenneIterativeRounding::writeLB	(	OsiRowCut &	cut,
		const double *	x,
		char	sense,
		double	rhs
	)

private

Write down a local branching constraint, as an OsiRowCut.

Definition at line 1047 of file CouenneIterativeRounding.cpp.

int Couenne::CouenneIterativeRounding::branchToCut	(	const double *	x,
		OsiSolverInterface *	solver,
		std::vector< int > &	previousBranches
	)

private

Branch on a random variable to cut given solution; returns var index.

Definition at line 1132 of file CouenneIterativeRounding.cpp.

bool Couenne::CouenneIterativeRounding::solveMilp	(	OsiSolverInterface *	milp,
		double	maxTime
	)

private

Solve the MILP contained in milp to feasibility, or report failure.

Definition at line 1077 of file CouenneIterativeRounding.cpp.

Member Data Documentation

Bonmin::OsiTMINLPInterface* Couenne::CouenneIterativeRounding::nlp_

private

Pointer to a dynamic nlp solver interface.

Definition at line 131 of file CouenneIterativeRounding.hpp.

OsiSolverInterface* Couenne::CouenneIterativeRounding::cinlp_

private

Pointer to the original NLP solver interface.

Definition at line 133 of file CouenneIterativeRounding.hpp.

OsiClpSolverInterface* Couenne::CouenneIterativeRounding::milp_

private

Pointer to a milp solver interface.

Definition at line 138 of file CouenneIterativeRounding.hpp.

int Couenne::CouenneIterativeRounding::maxRoundingIter_

private

Maximum number of iterations in the main loop.

Definition at line 141 of file CouenneIterativeRounding.hpp.

int Couenne::CouenneIterativeRounding::maxFirPoints_

private

Maximum number of iterations in the outer loop for feasibility.

Definition at line 143 of file CouenneIterativeRounding.hpp.

double Couenne::CouenneIterativeRounding::maxTime_

private

Max CPU time to run the heuristic.

Definition at line 145 of file CouenneIterativeRounding.hpp.

double Couenne::CouenneIterativeRounding::maxTimeFirstCall_

private

Max CPU time to run the heuristic when no other solution is known.

Definition at line 147 of file CouenneIterativeRounding.hpp.

int Couenne::CouenneIterativeRounding::numInitialRows_

private

Number of rows in the original convexification.

Definition at line 149 of file CouenneIterativeRounding.hpp.

int Couenne::CouenneIterativeRounding::numSol_

private

Number of solutions last time the heuristic was called.

Definition at line 151 of file CouenneIterativeRounding.hpp.

int Couenne::CouenneIterativeRounding::numIntegers_

private

Number of integer variables in the original model.

Definition at line 153 of file CouenneIterativeRounding.hpp.

double* Couenne::CouenneIterativeRounding::colLower_

private

Pointer to original column lower and upper bounds of the reformulated problem, i.e.

the linearization

Definition at line 156 of file CouenneIterativeRounding.hpp.

double* Couenne::CouenneIterativeRounding::colUpper_

private

Definition at line 157 of file CouenneIterativeRounding.hpp.

double* Couenne::CouenneIterativeRounding::colLowerNlp_

private

Pointer to column lower and upper bounds of the original problem, i.e.

the MINLP

Definition at line 160 of file CouenneIterativeRounding.hpp.

double* Couenne::CouenneIterativeRounding::colUpperNlp_

private

Definition at line 161 of file CouenneIterativeRounding.hpp.

CbcHeuristic** Couenne::CouenneIterativeRounding::heuristics_

private

Heuristics for the MILP.

Definition at line 164 of file CouenneIterativeRounding.hpp.

int Couenne::CouenneIterativeRounding::numHeuristics_

private

Definition at line 165 of file CouenneIterativeRounding.hpp.

double Couenne::CouenneIterativeRounding::startTime_

private

Starting time for the heuristics.

Definition at line 168 of file CouenneIterativeRounding.hpp.

double Couenne::CouenneIterativeRounding::endTime_

private

Maximum allowed time for current run.

Definition at line 170 of file CouenneIterativeRounding.hpp.

double Couenne::CouenneIterativeRounding::omega_

private

Multiplication factor for log barrier parameter in F-IR; see in the paper.

Definition at line 173 of file CouenneIterativeRounding.hpp.

int Couenne::CouenneIterativeRounding::baseLbRhs_

private

Base value for the rhs of the local branching constraint it I-IR.

Definition at line 175 of file CouenneIterativeRounding.hpp.

CouenneProblem* Couenne::CouenneIterativeRounding::couenne_

private

Pointer to a couenne representation of the problem.

Definition at line 178 of file CouenneIterativeRounding.hpp.

The documentation for this class was generated from the following files:

/tmp/OS-2.10.2/Couenne/src/heuristics/CouenneIterativeRounding.hpp
/tmp/OS-2.10.2/Couenne/src/heuristics/CouenneIterativeRounding.cpp

Public Member Functions

Static Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation