Soft Constraints

In many cases modelers wish to relax certain constraints: violation of these constraints is allowed but is associated with a well-defined penalty. The constraints that are allowed to be violated are called soft constraints and the constraints that continue to hold are called hard constraints.

In this section we present a mathematical formulation of soft constraints, give an example of how soft constraints can be modeled with GAMS EMP and introduce the EMP annotations specific to soft constraints.

# Soft Constraints: Mathematical Formulation

A general formulation of a constrained minimization problem is:

$$\begin{array}{ll} \textrm{Min}_{x \in \mathbb{R}^n} & f(x) \tag{2} \\ \textrm{s.t.} & c_i(x) \leq 0, \quad \forall i \in \mathcal{I}, \\ \end{array}$$

where $$f$$ and the functions $$c_i$$ are smooth, real-valued functions on a subset of $$\mathbb{R}^n$$ and $$\mathcal{I}$$ is a finite set of indices. Note that in this problem all feasible solutions must satisfiy all constraints $$c_i$$.

Now assume that some constraints are allowed to be violated (i.e. made soft), while the remaining constraints continue to hold for all feasible solutions. The soft constraints are associated with a penalty function that is added to the objective function. Since we have a minimization problem, the effect will be a balance or compromise between competing goals: minimizing the objective and minimizing the penalty functions.

Note
The penalty terms for soft constraints are added to the objective function in a minimization problem and subtracted in a maximization problem.

Let $$\mathcal{L} \in \mathcal{I}$$ be the set of indices for the soft constraints: this imples $$\mathcal{M} := \mathcal{I} \setminus \mathcal{L}$$ is the index set for the hard constraints. Problem (2) becomes:

$$\begin{array}{ll} \textrm{Min}_{x \in \mathbb{R}^n} & f(x) + \sum_{i \in \mathcal{L}} w_i \, g_i\, (c_i(x)) \tag{3} \\ \textrm{s.t.} & c_i(x) \leq 0, \quad \forall i \in \mathcal{M}, \\ \end{array}$$

where the penalty functions $$g_i$$ are real-valued functions of $$c_i(x)$$, $$i \in \mathcal{L}$$. As we will see later, EMP has implementations of the following penalty functions: absolute value, least squares, and the maximum of a term and zero. Further, $$w_i$$ is a multiplier associated with each penalty term, also called the weight. The weights facilitate prioritizing soft constraints: the weight of more important constraints will be greater than the weight of lesser constraints.

# Soft Constraints with EMP: A Simple Example

The following simple example is adapted from the JAMS solver manual:

$$\begin{array}{ll} \textrm{Min}_{x_1, x_2} & -x_1^2 \tag {4} \\ \textrm{s.t.} & \log (x_1) = 1 \\ & x_2^2 \geq 2 \\ & 3x_1 + x_2 \leq 5 \\ & x_1, \, x_2 \geq 0 \\ \end{array}$$

This problem can be formulated in GAMS as follows:

Positive Variables x1, x2;
Variables          obj;

Equations f0 "objective function", f1, f2, f3;

f0..   obj       =e= -sqr(x1);
f1..   log(x1)   =e= 1;
f2..   sqr(x2)   =g= 2;
f3..   3*x1 + x2 =l= 5;

Model m /all/;

x1.l = 1; x2.l = 1;

solve m using NLP min obj;


Note that this problem has no feasible solution. Thus we choose to relax the first two constraints by adding a penalty for their violation to the objective function. We also weight the relative importance or priority of the objective and the violations of these two constraints by introducing weights to go with these penalty functions. The resulting problem reads as follows:

$$\begin{array}{ll} \textrm{Min}_{x_1, x_2} & -x_1^2 + 5 \, \| {\log(x_1)-1} \|^2 + 2 \, \textrm{max}(x_2^2 - 2,0) \tag{5} \\ \textrm{s.t.} & 3x_1 + x_2 \leq 5 \\ & x_1, \, x_2 \geq 0 \\ \end{array}$$

Note that the first constraint is replaced by a least squares penalty of $$(log(x_1)-1)$$ with a weight of 5 and the second constraint by the penalty term $$\textrm{max}(x_2^2 - 2,0)$$ with a weight of 2. However, the "max" penalty makes the objective function non-smooth. To rectify this, we implement the "max" penalty by introducing a new variable $$v$$ that, due to its bounds and the direction of optimization, will take the value $$\textrm{max}(x_2^2 - 2,0)$$ at the solution. The result is:

$$\begin{array}{ll} \textrm{Min}_{x_1, x_2,v} & -x_1^2 + 5 \, \| {\log(x_1)-1} \|^2 + 2v \tag {6} \\ \textrm{s.t.} & 3x_1 + x_2 \leq 5 \\ & x_1, \, x_2 \geq 0 \\ & v \geq x_2^2 - 2 \\ & v \geq 0 \\ \end{array}$$

This reformulation could of course be implemented directly in GAMS using standard GAMS syntax, but the EMP solution is easier to create and maintain, to read and understand, and to scale upwards as problem size and complexity increase. For the latter, we can simply add the following EMP annotations and updated solve statement (to specify solution as an EMP) to the GAMS code above:

File soft / '%emp.info%' /;
put soft;
$onput adjustequ f1 sqr 5 f2 maxz 2$offput
putclose;
solve m using EMP min obj;


Note that the EMP annotations contain three lines: the first line, containing the EMP keyword adjustequ , indicates that the lines that follow specify soft constraints, i.e. equations to be converted to penalty terms; the second line specifies the name of the first soft constraint f1, the penalty function to use, and - optionally - the weight; and similarly the third line specifies the name of the second soft constraint f2, the penalty function to use, and the weight.

The solver JAMS will use the information in the EMP annotations to automatically reformulate problem (4) as problem (6) and pass it along to an NLP subsolver. The EMP Summary produced by JAMS will contain the following line:

--- EMP Summary
...
...


This output reflects that indeed two constraints were "adjusted", i.e. converted to penalty terms in the objective function.

# EMP Syntax for Soft Constraints

The EMP framework provides the following general syntax to specify constraints that are converted to soft constraints:

AdjustEqu equ abs|sqr|maxz {weight}
{equ abs|sqr|maxz {weight}}


The EMP keyword AdjustEqu indicates that the lines that follow specify equations that are "adjusted": they are moved from constraints to penalty terms in the objective function. Equ is the name of the equation to penalize, while the three EMP keywords that follow indicate the penalty function to use. If not specified, the weight used defaults to 1. For an example, see above or the model [SIMPENLP] in the GAMS EMP Model Library.