Types and protos for combo algorithm API: More...

#include <GAP_KnapPisinger.h>

Public Member Functions
void	solve (const int blockB, const double redCost, const double origCost, vector< int > &solInd, vector< double > &solEls, double &varRedCost, double &varOrigCost)

	GAP_KnapPisinger (const int nItems, const int capacity, const int weight, const int profit)

	~GAP_KnapPisinger ()

Private Member Functions
const int	getIndexIJ (const int i, const int j) const

int	calcScaleFactor (const double *redCost, const double epsTol=1.0e-4)

Private Attributes
int	m_nItems

item *	m_items

int	m_capacity

int *	m_weight

int *	m_profit

double *	m_workDbl

Detailed Description

Types and protos for combo algorithm API:

An interface class for Pisinger's Combo Algorithm for 0-1 Knapsack Problem.

typedef int boolean; // logical variable typedef int ntype; // number of states/items typedef long itype; // item profits and weights typedef long stype; // sum of profit or weight

typedef struct { itype p; // profit itype w; // weight boolean x; // solution variable } item;

extern stype combo(item * f, item * l, stype c, stype lb, stype ub, boolean def, boolean relx); f,l : first, last item c : capacity of knapsack lb : lower bound. Solution vector is only updated if better z found ub : upper bound. When upper bound is reached terminate immediately def : should solution vector be defined or just find objective value relx: relaxed problem is solved (no more relaxations will be made) returns the objective value of the problem

See {http://www.diku.dk/~pisinger/codes.html}.

The 0-1 Knapsack Problem: max sum{j = 0..n-1} p[j] x[j] s.t. sum{j = 0..n-1} w[j] x[j] <= b x binary

Definition at line 72 of file GAP_KnapPisinger.h.

Constructor & Destructor Documentation

GAP_KnapPisinger::GAP_KnapPisinger	(	const int	nItems,
		const int	capacity,
		const int *	weight,
		const int *	profit
	)

inline

Definition at line 276 of file GAP_KnapPisinger.h.

References CoinAssertHint, m_items, m_profit, m_weight, and m_workDbl.

GAP_KnapPisinger::~GAP_KnapPisinger ( )

inline

Definition at line 295 of file GAP_KnapPisinger.h.

References m_items, m_profit, m_weight, m_workDbl, and UTIL_DELARR.

Member Function Documentation

const int GAP_KnapPisinger::getIndexIJ	(	const int	i,
		const int	j
	)		const

inlineprivate

Definition at line 83 of file GAP_KnapPisinger.h.

References m_nItems.

Referenced by solve().

int GAP_KnapPisinger::calcScaleFactor	(	const double *	redCost,
		const double	epsTol = `1.0e-4`
	)

inlineprivate

Definition at line 89 of file GAP_KnapPisinger.h.

References COIN_INT_MAX, CoinAssertDebug, m_nItems, m_workDbl, UtilFracPart(), and UtilIsZero().

Referenced by solve().

void GAP_KnapPisinger::solve	(	const int	blockB,
		const double *	redCost,
		const double *	origCost,
		vector< int > &	solInd,
		vector< double > &	solEls,
		double &	varRedCost,
		double &	varOrigCost
	)