1. Home
  2. Docs
  3. Math blog
  4. Domain Reduction
  5. Introduction

Introduction

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.

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 some of the algorithmic techniques implemented in Octeract Engine to approach this important task.

How can we help?