[Tutorial] Lagrange Relaxation

In solving a problem, it is often difficult to obtain the optimal solution due to strict constraints, making it computationally expensive. Lagrange Relaxation is a method that loosens some particular constraints of the problem with the objective to optimize the findings. This is done by introducing Lagrange multipliers for those relaxed constraints. The solution to the problem with the relaxed constraints is then used as the boundary (both upper and lower) for the original problem.

The Aliens problem from IOI 2016 brought significant attention for this method, making it also known as Aliens' Trick. Ever since, this method has started to gain popularity among competitive programmers. In this blog, we will delve deeper into this method; especially in solving the Aliens problem. If you are not familiar with the Convex Hull Trick yet, I suggest you to read my blog here.

Motivational Problem: IOI 2016 - Aliens

We have a low-resolution photo of a remote planet's area, which is divided into an

m×m grid consisting of $n$ points that we are interested in. Our satellite, passing over the main diagonal of the grid, can take high-resolution photos of square areas. Each square's opposite corners must be on the grid's main diagonal. The satellite can take at most $k$ high-resolution photos. Our task is to choose up to $k$ square areas to photograph ensuring:

1. Every cell with a point of interest is captured.
2. The total number of photographed cells is minimized.

We want to find the smallest possible total number of photographed cells.

Constraints

• $1\le k\le n\le 10^5$
• $1\le m\le 10^6$

Subtasks

no.	points	$n$	$m$	$k$
1 - 3	$25$	$\le 500$	$\le 1000$
4	$16$	$\le 4000$
5	$19$	$\le 50000$		$\le 100$
6	$40$

On contest score distribution

Naive Dynamic Programming (25 points)

Notice that due to constraint of "each square's opposite corners must be on the grid's main diagonal", we can always interchange the value of

ri​ and $c_i$ as the new point is a reflection point across the main diagonal. As a result, the order of $r_i$ and $c_i$ is irrelevant. For each point $i$, visualize it as a segment that spans the range $[l_i,r_i]=[\min (r_i,c_i),\max (r_i,c_i)]$. Consequently, a photo that covers a point $(a,a)$ to $(b,b)$ will capture point $i$ if and only if $a\le l_i\le r_i\le b$.

Further, this observation indicates that capturing a point

j ($i<j$) will also encompass point $i$ if $l_j\le l_i\le r_i\le c_j$. With that, we may simply discard point $i$. After such eliminations, all remaining points will have the property: for points $i$ and $j$ ($i<j$), $r_i<r_j$ and $c_i<c_j$.

Let

dpi,j​ denotes the minimum cost to cover first $i$ points with at most $j$ photos. Then,

Here is a breakdown of the components:

• The ${\text{dp}}_{t,j-1}$ represents the cost of capturing the first $t$ points using $j-1$ photos. Then, we aim to cover the point $t+1$ up to point $i$ using $1$ photo.
• The expression $(r_i-l_{t+1}+1{)}^2$ calculates the cost of capturing the point $t+1$ up to point $i$ using $1$ photo.
• The $\max (r_t-l_{t+1}+1,0{)}^2$ part is accounted to an overcharging cost due to the overlap between point $t$ and point $t+1$. Hence, it is substracted to correct the cost.

This dynamic programming solution works in

O(n2k).

Convex Hull Trick (60 points)

We had:

Our dynamic programming can be expressed as:

where:

• $m_{t,j-1}=-2(l_{t+1}-1)$
• $x_{i,j}=r_i$
• $c_{t,j-1}={\text{dp}}_{t,j-1}+(l_{t+1}-1{)}^2-\max (r_t-l_{t+1}+1,0{)}^2$
• $C_{i,j}=r_i^2$

This Convex Hull Trick approach runs about an

O(kn) armortized time. Note that it is not $\mathcal{O}(kn\log n)$ as we can use a $\text{std::deque}$ instead of a $\text{std::vector}$ here, given that the point queries are in increasing order.

Lagrange Relaxation (100 points)

The following solution idea is inspired by and adapted from the official solution.

Denote

f(i,j) to be a function that represents our dynamic programming solution, i.e. $f(i,j)={\text{dp}}_{i,j}$. We want to relax the constraints on the number of photos taken. Let's assume we don't have the $k$ constraint and we want to apply a cost on each photo taken to make up for it. Define $\mathcal{L}(i,j,\lambda )$ to be $f(i,j)+\lambda j$, implying an additional cost of $\lambda$ for each photo taken.

For a

λ, we may define $g(i)$ to represent another optimization problem that satisfies the following:

Solving

g(n) for a given $\lambda$ allows us to obtain the minimum number of photos required to capture all $n$ points and achieve the minimum cost when each photo is charged $\lambda$ cost, let's define it as $p(\lambda )$.

A function

f(i,j) is said to be convex if it satisfies: $f(i,j-1)-f(i,j)\ge f(i,j)-f(i,j+1)$. Alternatively, we may conclude a function $f(i,j)$ to be convex if it is in the form:

and

C(x,y) is a Monge Array, i.e. $\forall x,y$, it holds $C(x,y)+C(x+1,y+1)\le C(x,y+1)+C(x+1,y)$. Claim that $f(i,j)$ is convex; then, we want to prove that $C(x,y)=(r_y-l_x+1{)}^2-\max (r_{x-1}-l_x+1,0{)}^2$ is a Monge Array.

Convexity of f(i, j)

Based on the previous observations, we have

ri​<rj​ and $c_i<c_j$ for points $i$ and $j$ when $i<j$ holds.

It is shown that

C(x,y) is a Monge Array; hence, $f(i,j)$ is convex.

Given that

f(i,j) is convex, so is $\mathcal{L}(i,j,\lambda )$. This implies:

With that we may find

λk​∈[0,m2] that satisfies $k\le p({\lambda }_k)$ and $p({\lambda }_k+1)\le k$. This can be done using binary search with $\mathcal{O}(n\log m)$ time complexity (the linear $n$ is obtained from computing $g(n)$ using Convex Hull Trick).

Last, we only need to find the exact value of

f(n,k), which is our original objective. The interval $[p({\lambda }_k+1),p({\lambda }_k)]$ signifies the range we are interested in. Considering that $\forall i\in [p({\lambda }_k+1),p({\lambda }_k)-1]:f(n,i)-f(n,i+1)$ remains constant (slope is constant), we may use linear interpolation to calculate our answer to the original problem. Let $\Delta =f(n,p({\lambda }_k))-f(n,p({\lambda }_k+1))$; then,

The overall solution operates in

O(nlogn+nlogm).

Lagrange Relaxation in General

Basic Idea

1. Decomposition of the Original Problem: Decompose the original problem into a blend of a simpler optimization problem and an added term to penalize constraint violations.

2. Lagrange Function Formulation: In the equation below,

   KaTeX can only parse string typed expression
   f(x) represents the objective function, $g(x)$ denotes the constraint equations, $b$ stands for their boundaries, and $\lambda$ acts as the Lagrange multiplier:
   $$\mathcal{L}(x,\lambda )=f(x)+\lambda (g(x)-b)$$

3. Bounds Identification: Establish both the lower and upper bounds wherein the solution to the original problem lies within the defined interval.

Importance of Convexity

1. Guaranteed Global Optima: Convexity ensures that the solution obtained from the relaxed problem, supported by Lagrange multipliers, offers a valid and global optimum bound.

2. Optimization Simplification: A convex optimization landscape simplifies the process, reducing potential local minima or maxima that can complicate the search for an optimal solution.

3. Efficient Solutions: When the Lagrange function is convex, it facilitates the efficient determination of the solution for the relaxed problem. This is important since Lagrange relaxation primarily aims to transform intricate problems into manageable sub-problems.

References

1. Chethiya Abeysinghe, "IOI 2016 - Solutions," International Olympiad in Informatics.

2. Mamnoon Siam, "Attack on Aliens," Siam's Blog. https://mamnoonsiam.github.io/posts/attack-on-aliens.html.

3. upobir, "Quadrangle Inequality Properties," Codeforces. https://codeforces.com/blog/entry/86306.

© 2023 Yohandi. All rights reserved.