Constraint Optimization Problems

This chapter defines COPs (Constraint Optimization Problems) and introduces the G-problem benchmark.

COPs

A constrained optimization problem (COP) for numerical and continuous quantities in \(\mathbb{R}^d\) is defined as:

\[ \text{Minimize} \quad f(\vec{x}), \quad \vec{x} \in [\vec{a},\vec{b}] \subset \mathbb{R}^d \]\[ \text{subject to} \quad g_{i}(\vec{x}) \leq 0, \quad i=1,2,\ldots,m \]$$ \quad\qquad\qquad h_{j}(\vec{x}) = 0, \quad j=1,2,\ldots,r $$

G-Problem Benchmark

The G-problem benchmark suite originates from a CEC 2006 competition [LiangRunar06]. It is a set of 24 constrained optimization problems (COPs, G-problems) G01, …, G24 with various properties like dimension, number of equality / inequality constraints, feasibility ratio, etc. Eight of the 24 COPs have equality constraints. Although these problems were introduced as a suite in the technical report [LiangRunar06] at CEC 2006, many of them have been used by different authors earlier.

The G-problems are available in SACOBRA_Py as objects of class GCOP:

class gCOP.GCOP(name, dimension=None, mu=1e-07)

Constraint Optimization Problem Benchmark (G Function Suite)

[LiangRunar06] J. Liang, T. P. Runarsson, E. Mezura-Montes, M. Clerc, P. Suganthan, C. C. Coello, and K. Deb, “Problem definitions and evaluation criteria for the CEC 2006 special session on constrained real-parameter optimization,” Journal of Applied Mechanics, vol. 41, p. 8, 2006. http://www.lania.mx/~emezura/util/files/tr_cec06.pdf

Example: Instantiate problem G01 or G02 with

  • G01 = GCOP("G01").

  • G02 = GCOP("G02", dimension=5).

Only problems G02 and G03 have the extra parameter dimension. All other problems G01, G04, …, G24 have fixed dimensions.

Objects of class GCOP have the following useful attributes:

  • name name of the problem, given by the user as 1st argument

  • dimension input space dimension of the problem. For the scalable problems G02 and G03, the dimension should be given by the user, otherwise it will be set automatically

  • lower lower bound vector, length = input space dimension

  • upper upper bound vector, length = input space dimension

  • fn the COP functions which can be passed to SACOBRA_Py (see parameter fn in class CobraInitializer).

  • nConstraints number of constraints

  • x0 the suggested optimization starting point, may be None if not available

  • solu the best known solution(s), (only for diagnostics purposes). Can be None (not known) or a vector in case of a single solution or a matrix in case of multiple equivalent solutions (each row of the matrix is a solution). For problems with equality constraints, parameter mu allows to select between different solutions (see below).

  • fbest the objective at the best known solution(s), (only for diagnostics purposes)

  • info information about the problem, may be None if not available

Parameter mu:

For problems G05, G14, G15, G17, G21, G22 (all with equality constraints), different solutions solu can be selected via parameter mu: If mu = 1e-4 then each equality constraint has a tolerance band \(|h_j(x)| \leq 10^{-4}\). This is the feasibility definition of [LiangRunar06], it results in slightly violating solutions with somewhat better (lower) objective. But in the cases of the six G-problems above, one can find also solutions where the equality constraint violation is \(10^{-6}, 10^{-7}\) or below, at the price of slightly higher objectives. These solutions will be returned when mu=1e-6 or mu=1e-7 is set. This is useful if you want to test if your optimization procedure can also find solutions with lower constraint violation (SACOBRA: parameter EQU.muFinal in EQUoptions EQU).

[LiangRunar06] (1,2)

  1. Liang, T. P. Runarsson, E. Mezura-Montes, M. Clerc, P. Suganthan, C. C. Coello, and K. Deb, “Problem definitions and evaluation criteria for the CEC 2006 special session on constrained real-parameter optimization,” Journal of Applied Mechanics, vol. 41, p. 8, 2006. http://www.lania.mx/~emezura/util/files/tr_cec06.pdf