\( \varepsilon \)-Constraint Method Class More...

#include <Epsilon.h>

Public Member Functions
	Epsilon (int _p)
	Constructor of the Epsilon class. More...

	~Epsilon (void)
	Destructor of the Epsilon class. More...

void	mainLoop (char *fileName)
	Main loop of the method. More...

Protected Member Functions
int	findMaxAreaBox ()
	Determine the rectangle with the largest volume-based measure. More...

bool	epsilonModel (int k, const int rhs, int obj)
	Two stage \( \varepsilon \)-constraint formulation. More...

void	getParameters (char *fileName)
	Read multiobjective discrete optimization problem instance. More...

bool	checkEfficient (int *obj)
	Control whether a new nondominated solution is obtained or not. More...

void	updateList (int num, int *obj)
	Update the rectangle list \( L \) considering the nondominated solution \( y \in \mathbb{R}^{p} \) where \( y \notin \mathcal{Y}_{N} \). More...

void	removeBox (int num, int rhs, int obj)
	Remove rectangles that do not need to be searched. More...

bool	obtainBounds ()
	Calculate the boundaries of the initial search space. More...

Protected Attributes
int	p
	Number of objective functions. More...

int	counter
	Number of solved models. Number of calls of two-stage formulation. More...

int	number
	Number of constraints in the problem instance. More...

int	delta
	Tolerance for the \( \varepsilon \)-Constraint formulation. More...

int	numeff
	Number of nondominated solutions. More...

IloEnv	env
	Environment object. More...

IloCplex	cplex
	Cplex object. More...

vector< IloExpr >	objs
	Objective functions of the problem instance, \( f_j(x) \) for all \( j \in \{1, \ldots, p \} \). More...

IloExpr	allobj
	Convex combination of all objective functions with unit weight coefficients, \( z = \displaystyle \sum _{j=1}^p f_j(x) \). More...

IloConstraintArray	cons
	Set of constraints of the problem. More...

bool	found
	Flag for the nondominated solution. Let \( x^* \) be the optimal solution of two-stage formulation. If \( f(x^*) \notin \mathcal{Y}_N \), than true. Otherwise, false. More...

deque< Efficient * >	effset
	Set of nondominated solutions, \( \mathcal{Y}_N \). More...

deque< Box * >	boxes
	Set of rectangles, \( L \). More...

deque< Box * >	T_box
	Temporary rectangle set \( T \) which is used for rectangular subdivision. More...

int	sizeb
	Number of rectangles, \( \|L\|\). More...

int	sizet
	Number of rectangles in the temporary rectangle list. More...

IloModel	epsmodel
	Model object for the two-stage formulation. More...

IloObjective	objfunc
	Objective function for the first and second formulation. More...

deque< IloRange >	range_obj
	Cplex range object for the objective functions which is used to define upper and lower bounds on the objective functions. More...

deque< int >	liste
	Indexes of the removed rectangles. More...

vector< vector< IloNumVar > >	varArray
	The list of variables. More...

vector< vector< IloNum > >	numArray
	Variable coefficients in the objective functions. More...

int *	ideal
	Ideal point, \( y^I \in \mathbb{R}^p \). More...

int *	upper
	Upper bound for the objective functions, \( y^U \). More...

Detailed Description

\( \varepsilon \)-Constraint Method Class

In this class, a nondominated set enumeration method is implemented for multiobjective discrete optimization problems with any number of objective functions \(( p \ge 2) \). Algorithm searches \( (p-1)\)-dimensional space exhaustively by using \( (p-1)\)-dimensional rectangles. In each iteration, rectangle \( R_i \) with the largest volume-based measure is picked from the list \( L\). Then two-stage formulation is solved with the upper vertex of \(R_i \). Two-stage formulation is given below.
\( \begin{array}{lll} P(u_i) & \min & \displaystyle f_k(x) \\ \displaystyle & \mbox{s.t.} & f_j(x) \le u_{ij} \quad j \in \{1,\ldots,p\} \setminus \{ k \}\\ \displaystyle & & x \in \mathcal{X} \end{array} \)
Let \( x' \) be the optimal solution of \( P(u_i) \). Second-stage optimization problem is as follows.

\( \begin{array}{lll} Q(u_i) & \min & \displaystyle \sum_{j=1}^p f_j(x) \\ \displaystyle & \mbox{s.t.} & f_j(x) \le u_{ij} \quad j \in \{1,\ldots,p\} \setminus \{k\} \\ \displaystyle & & f_k(x) \le f_k(x') \\ \displaystyle & & x \in \mathcal{X} \end{array} \)
Let \( x^* \) be the optimal solution of the two-stage formulation. \( x^* \) is an efficient solution and \( f(x^*) \in \mathbb{R}^p \) is the resulting nondominated solution. Depending on \( f(x^*) \), three following conditions occur.

\( x^* \neq \emptyset \mbox{ and } f(x^*) \nsubseteq Y_N \). A new efficient solution is obtained.
- updateList \(\left(k,\; f(x^*) \right)\)
- removeBox \( \left(k, \; u_i, \; f(x^*) \right)\)
\( x^* \neq \emptyset \mbox{ and } f(x^*) \subseteq Y_N \). Obtained efficient solution has already found.
- removeBox \( \left (k, \; u_i, \; f(x^*) \right ) \)
\( x^* = \emptyset \). Two-stage \( P_(u^i) \) model returns an infeasible solution for \( R_i \).
- removeBox \( \left (k, \; u_i, \; y^I \right ) \)

Algorithm is terminated when the list \( L \) is empty.

Constructor & Destructor Documentation

Epsilon::Epsilon ( int _p )

Constructor of the Epsilon class.

Parameters of the algorithm (number of nondominated solutions, counter for the number of solved models, number of constraints etc.) are set to their initial value. Cplex parameters are initialized.

Parameters

_p	Number of objective functions.

Epsilon::~Epsilon ( void )

Destructor of the Epsilon class.

This function is the destructor of the Epsilon class. In this function, allocated objects in the constructor class are deallocated.

Member Function Documentation

bool Epsilon::checkEfficient ( int * obj )

protected

Control whether a new nondominated solution is obtained or not.

This function controls whether the input nondominated solution \( f(x^*) \) is a new solution or not. If the nondominated solution is new, than \( f(x^*) \) is added to the nondominated solutions list, \( \mathcal{Y}_N = \mathcal{Y}_N \cup \{f(x^*)\}\) and function returns true, else returns false.

Parameters

obj	Obtained nondominated solution by using two-stage \( \varepsilon \)-constraint formulation.

Returns: If \( f(x^*) \notin \mathcal{Y}_N \), than true, else false.

bool Epsilon::epsilonModel	(	int	k,
		const int *	rhs,
		int *	obj
	)

protected

Two stage \( \varepsilon \)-constraint formulation.

This function solves two-stage \( \varepsilon \)-constraint formulation with the upper vertex of the largest volume-based measure \( R_i \).

Parameters

	k	Objective function index that taken into objective function in the \( \varepsilon \)-constraint formulation.
	rhs	Upper vertex \( u_i \) of the rectangle \( R_i \).
[out]	obj	This parameter shows the resulting nondominated solution if first-stage is feasible with the given right-hand-side vector.

Returns: If the model is feasible, true; otherwise, false.

int Epsilon::findMaxAreaBox ( )

protected

Determine the rectangle with the largest volume-based measure.

This function determines the rectangle \( R_i \) that has the largest volume-based measure. \( R_i = \displaystyle {\arg\max}_{R_s\in L} (R_s \rightarrow A) \).

Returns: Index of a rectangle with the largest volume-based measure in \( L \).

void Epsilon::getParameters ( char * fileName )

protected

Read multiobjective discrete optimization problem instance.

This function imports MODO problem instance via MPS or LP file. The objective function of the MPS or LP file is skipped. First \( p \) constraints of the model represents objective functions of the problem, i.e. \( f_j(x) \) for all \( j \in \{1,\ldots,p \}\). The remaining rows of the model are the constraints, i.e. the feasible set \( \mathcal{X} \), of the problem.

Parameters

fileName Name of the mps or lp file.

void Epsilon::mainLoop ( char * fileName )

Main loop of the method.

This is the main loop of the method. Firstly, model parameters are imported. Then, the search space is initialized with the rectangle \( R(\bar{y}^I,\bar{y}^U) \). In each iteration, a rectangle is picked from the list \( L \), and two-stage formulation is solved with the upper vertex the rectangle. Depending on the result of the two-stage formulation, three possible cases may occur, and all of them are handled into the while loop. When the list \( L \) is empty, algorithm is terminated.

Parameters

fileName Name of the mps or lp file.

bool Epsilon::obtainBounds ( )

protected

Calculate the boundaries of the initial search space.

This function controls whether the set of constraints \( \mathcal{X} \) has a feasible solution. Additionally, in this function boundaries of the initial rectangle are determined. Briefly, the ideal point \( y^I \) and upper bounds for objective functions \( y^U \) are determined.

Returns: If \( \mathcal{X} \neq \emptyset\), return true. Otherwise, return false.

void Epsilon::removeBox	(	int	num,
		int *	rhs,
		int *	obj
	)

protected

Remove rectangles that do not need to be searched.

Remove rectangles that lies on \( R(rhs,obj)\). In each iteration, this method is called exactly once. If two-stage formulation is feasible than \( rhs(j) = u_{ij} \) and \( obj(j) = f_j(x^*)\) for all \( j \in \{1,\ldots,p\} \setminus \{k\}\). For the infeasibility case, \( rhs(j) = u_{ij} \) and \( obj(j) = y_j^I \) for all \( j \in \{1,\ldots,p\} \setminus \{k\}\).

Parameters

num	Objective function index that taken into objective function in the \( \varepsilon \)-constraint formulation.
rhs	Upper vertex of the rectangle that defines the unnecessary search space.
obj	Lower vertex of the rectangle that defines the unnecessary search space.

void Epsilon::updateList	(	int	num,
		int *	obj
	)

protected

Update the rectangle list \( L \) considering the nondominated solution \( y \in \mathbb{R}^{p} \) where \( y \notin \mathcal{Y}_{N} \).

In this method, all rectangles in the list are controlled to apply rectangular division process. For all \( R_s \in L \), if \( (R_s \rightarrow l_j) < f_j(x^*) < (R_s \rightarrow u_j) \), then split the rectangle \( R_s \) along the \( j^{th}\) axis where \( j \in \{1,\ldots,p\} \setminus \{k\}\).

Parameters

num	Objective function index that taken into objective function in the \( \varepsilon \)-constraint formulation.
obj	New nondominated solution.

Member Data Documentation

IloExpr Epsilon::allobj

protected

Convex combination of all objective functions with unit weight coefficients, \( z = \displaystyle \sum _{j=1}^p f_j(x) \).

deque<Box*> Epsilon::boxes

protected

Set of rectangles, \( L \).

IloConstraintArray Epsilon::cons

protected

Set of constraints of the problem.

int Epsilon::counter

protected

Number of solved models. Number of calls of two-stage formulation.

IloCplex Epsilon::cplex

protected

Cplex object.

int Epsilon::delta

protected

Tolerance for the \( \varepsilon \)-Constraint formulation.

deque<Efficient*> Epsilon::effset

protected

Set of nondominated solutions, \( \mathcal{Y}_N \).

IloEnv Epsilon::env

protected

Environment object.

IloModel Epsilon::epsmodel

protected

Model object for the two-stage formulation.

bool Epsilon::found

protected

Flag for the nondominated solution. Let \( x^* \) be the optimal solution of two-stage formulation. If \( f(x^*) \notin \mathcal{Y}_N \), than true. Otherwise, false.

int* Epsilon::ideal

protected

Ideal point, \( y^I \in \mathbb{R}^p \).

deque<int> Epsilon::liste

protected

Indexes of the removed rectangles.

vector<vector<IloNum> > Epsilon::numArray

protected

Variable coefficients in the objective functions.

int Epsilon::number

protected

Number of constraints in the problem instance.

int Epsilon::numeff

protected

Number of nondominated solutions.

IloObjective Epsilon::objfunc

protected

Objective function for the first and second formulation.

Note: Objective functions of first and second stage are different (see \( P(u_i) \) and \( Q(u_i) \)). Hence, \( \mathtt{setExpr} \) (Cplex library) method is used to modify the objective function.

vector<IloExpr> Epsilon::objs

protected

Objective functions of the problem instance, \( f_j(x) \) for all \( j \in \{1, \ldots, p \} \).

int Epsilon::p

protected

Number of objective functions.

deque<IloRange> Epsilon::range_obj

protected

Cplex range object for the objective functions which is used to define upper and lower bounds on the objective functions.

Note: In each iteration bounds on the objective functions are changing while feasible set same. Hence, bounds on the objective functions are modified by using \( \mathtt{setUB} \) method. Initially, lower and upper bounds on the objective functions are \( y^I \) and \( y^U \).

int Epsilon::sizeb

protected

Number of rectangles, \( |L|\).

int Epsilon::sizet

protected

Number of rectangles in the temporary rectangle list.

deque<Box*> Epsilon::T_box

protected

Temporary rectangle set \( T \) which is used for rectangular subdivision.

int* Epsilon::upper

protected

Upper bound for the objective functions, \( y^U \).

vector<vector<IloNumVar> > Epsilon::varArray

protected

The list of variables.

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

Epsilon.h

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation