Introduction to Domain Reduction

Consider the following problem:
\begin{equation} \begin{aligned} P:= \min_{x_1,x_2} & f(x_1,x_2) \\ \text{s.t. } & x_1x_2 \leq 1,\\ & -10x_1-x_2 \leq -6,\\ & x_1 \in [0,1.5],\\ & x_2 \in [1,4]. \end{aligned} \end{equation}
The feasible region for this problem corresponds to the red area in Figure 1 (denoted as \(\Omega\)).

Notice that although the range of the variable \(x_1\) is originally \([0,1.5]\), the feasible region in the figure only admits values of \(x_1\) between \(0.2\) and \(1\) (red dashed lines in Figure 1). Knowing this, it is then logical to change the bounds of \(x\) in the original problem from \(x_1 \in [0,1.5]\) to \(x_1 \in [0.2,1]\) (i.e., tightening the bounds of \(x_1\)).

This change will make other calculations and techniques used by Octeract Engine more effective (e.g., relaxations and branching).


Figure 1: domain reduction
Figure 1.

In general, for a problem \(\min_{x \in \Omega} f(x)\) we would like to find the tightest bounds for each variable \(x_i\), i.e., find the lower bound \(l_i^\star = \min_{x \in \Omega} x_i\), and upper bound \(u_i^\star = \max_{x \in \Omega} x_i\).

However, unlike our previous example, it is not easy to solve the problems \(\min_{x \in \Omega} x_i\) and \(\max_{x \in \Omega} x_i\), and a different approach is required. Feasibility based bounds tightening (FBBT) , Optimisation based bounds tightening (OBBT) and Constraint propagation (CP), are the algorithmic techniques used by Octeract Engine to approach this important task.

Was this helpful?
Please make sure you fill the comments section before sending.

Thank you for your comments.
Please contact us if you need any further support.
dr/dr1000