Functions & Optimization

Part 3 of 8 · Previous: Operators · Index · Next: Algebra

13. Functions

Function type

$$f:A\to B$$

Read:

$f$ is a function from set $A$ to set $B$.

• $A$: domain
• $B$: codomain

Example:

$$\ell :\mathcal{P}\to \mathbb{N}$$

may mean:

$\ell$ maps every path to its integer length.

Mapping notation

$$x\mapsto x^2$$

Read:

Map $x$ to $x^2$.

Together:

$$f:\mathbb{R}\to \mathbb{R},x\mapsto x^2$$

Function composition

$$(f\circ g)(x)=f(g(x))$$

Read from right to left:

1. apply $g$;
2. then apply $f$.

---

14. Piecewise definitions

A function can have different definitions in different cases:

$$f(x)=\{\begin{array}{ll}0,& x<0,\\ x,& x\ge 0.\end{array}$$

Read:

• $f(x)=0$ when $x<0$;
• $f(x)=x$ when $x\ge 0$.

The function:

$$\max (0,x)$$

can also be written:

$$\max (0,x)=\{\begin{array}{ll}0,& x<0,\\ x,& x\ge 0.\end{array}$$

---

15. Indicator functions

$$1[P]$$

or:

$$1_P$$

means:

$$1[P]=\{\begin{array}{ll}1,& P\text{ is true},\\ 0,& P\text{ is false}.\end{array}$$

Example:

$$\sum _{a}1[\text{ant }a\text{ occupies room }v]\le 1$$

Read:

Count all ants occupying room $v$; that count must be at most one.

Indicator functions are common in:

• algorithms;
• probability;
• combinatorics;
• integer programming;
• graph optimization.

---

16. Common optimization form

A mathematical optimization problem often looks like:

$$\begin{array}{rl}\text{minimize}& f(x)\\ \text{subject to}& g(x)\le 0,\\ & x\in S.\end{array}$$

Terminology:

• $x$: decision variable;
• $f(x)$: objective function;
• $g(x)\le 0$: constraint;
• $S$: feasible domain;
• feasible solution: a value satisfying every constraint;
• optimal solution: a feasible value producing the best objective.

Compact form:

$$\underset{\begin{array}{c}x\in S\\ g(x)\le 0\end{array}}{\min }f(x)$$

---

17. Reading a Lem-in optimization formula

Consider:

$$T(\mathcal{P})=\underset{\begin{array}{c}{x}_i\in {\mathbb{N}}_0\\ {\sum }_i{x}_i=N\end{array}}{\min }\underset{i:x_i>0}{\max }(d_i+x_i-1)$$

Left-hand side

$$T(\mathcal{P})$$

means:

Completion time obtained with path family $\mathcal{P}$.

Outer minimum

$$\min$$

means:

Choose the best allocation.

Constraints below the minimum

$$x_i\in {\mathbb{N}}_0$$

means every $x_i$ is a nonnegative integer.

$$\sum _i{x}_i=N$$

means all $N$ ants are assigned.

Inner maximum

$$\underset{i:x_i>0}{\max }$$

means:

Among paths receiving at least one ant, find the one that finishes last.

Path completion expression

$$d_i+x_i-1$$

means:

• $d_i$: time for the first ant;
• $x_i-1$: additional turns for the remaining ants.

Full translation

The completion time is the smallest possible finishing time of the slowest used path, considering every valid way to distribute all $N$ ants among the paths.

---

18. Reading the capacity formula

$$T(\mathcal{P})=\min \left\{\tau \in \mathbb{N}:\sum _{P_i\in \mathcal{P}}\max (0,\tau -d_i+1)\ge N\right\}$$

Translation by component

$$\tau \in \mathbb{N}$$

Candidate completion turn $\tau$ must be a natural number.

$$\max (0,\tau -d_i+1)$$

Number of ants path $i$ can deliver by turn $\tau$.

$$\sum _{P_i\in \mathcal{P}}$$

Add this capacity for every compatible path.

$$\ge N$$

There must be enough total capacity for all $N$ ants.

$$\min \{\cdots \}$$

Choose the earliest deadline satisfying the condition.

Full translation

$T(\mathcal{P})$ is the earliest integer turn at which the combined capacity of the compatible paths is sufficient to deliver all $N$ ants.

---