Optimisation is the minimisation or maximisation of a function subject to constraints on its variables, we use the notation:

• $x$ is the vector of variables (unknowns / parameters)
• $f_0$ is the objective function, (scalar) function of $x$ that we want to maximise or minimise
• $f_i$ and $h_i$ are constraint functions, scalar functions of $x$ that define certain equations and inequalities that the unknown vector $x$ must satisfy

A general form of an optimisation problem: ${\min }_{(x_1,\dots ,x_n)\in C}{f}_0(x_1,x_2,\dots ,x_n)$ subject to:

Linear Programming

Linear programming is the ‘planning of activities to obtain an optimal result’ given the objective function and constraints are linear. Solutions are highly structured and can be rapidly obtained.

A linear programming model consists of:

• a set of decision variables
• a (linear) objective function
• a set of (linear) constraints

Algorithms for solving linear programming

• Graphical method
• Simplex method
• Interior-point method

Commercial software packages: CPLEX, MINOS, GIPALS Open access packages: GLPK (GNU Linear Prog. Kit), LP Solve

We say a linear program is feasible if there is an assignment of values to variables $x_1,\dots ,x_n$ that satisfies all constraints. Otherwise, it is infeasible. The set of all feasible solutions is called the feasible region.

A bounded region is an assignment of values to variables $x_1,\dots ,x_n$ for that $f(x)$ is the maximum (or minimum) among all feasible assignments (we call this the optimal solution). If a programme has some feasible solution, but no optimal solution, we call it unbounded.

Setting up a linear program

1. Determine and label decision variables
2. Determine objective and use decision variables to write an expression for the objective function
3. Determine the constraints - feasible region
   1. Determine explicit constraints and write functional expression for each of them
   2. Determine implicit contraints (e.g. non-negativity constraints)

Graphical method to solve linear program

1. Setup LP problem
2. Construct the graph Plot the graph and constraint lines
3. Identify feasible region Region of the graph that satisfies all constraints.
4. Find optimum point

Example: Bakery Factory

Formulating as a Linear Program:

1. Decision Variables $x$: number of caramel cookies sold daily $y$: number of chocolate chip cookies sold daily
2. Objective Function $f(x,y)=0.88x+0.75y\text{ where }x\text{ and }y\text{ are non-negative}$
3. Constraints $80\le x\le 120$ $120\le y\le 140$ $x+y\ge 240$

So our LP is ${\max }_{x,y\ge 0}f(x,y)=0.88x+0.75y$ Subject to the constraints listed above.

So we want to make 120 caramel cookies and 140 chocolate cookies to maximise profit. The maximum revenue generated in a day is £210.6

Example: no feasible solutions

Example: multiple optimal solutions

Example: unbounded region

Integer and mixed integer programming

When all variables are restricted to integer values (integer linear programming, ILP) then the problem is computationally hard: there are no polynomial time algorithms known.

While linear programming itself is easy and there are known polynomial time algorithms.

If we allow both real and integer variables (mixed integer linear programming, Mixed ILP) then the computational complexity grows with the number of integer variables.

A problem with a small (constant) number of binary variables may be computationally easy, but if the number of binary variables is a fixed fraction (e.g. 25%) of all variables, then the problem is NP-hard.

Example: Maximum Flow LP

Flow network

A flow network is a graph $G=(V,E,c,s,t)$ where:

• $V$ is a set of $n$ nodes
• $E$ is a set of $m$ edges (links)
• For each $(u,v)\in E$, $c(u,v)\ge 0$ is the capacity of edge $(u,v)$ If $(u,v)\notin E$, then for convenience we define $c(u,v)=0$
• There are two distinguished nodes: source $s$ and sink $t$ where $s\ne t$

Link to original

Maximum flow problem

The maximum flow problem is where for a given flow network, we find the flow of the maximum possible value (maximises net flow from source).

Link to original

Specific Example

Our decision variables are $f_{a,b},f_{a,s},f_{b,d},\dots$ ($f_{v,w}$ is flow on edge $(v,w)$)

Maximise $f_{s,b}+fs,h+f_{s,c}-f_{a,s}$ Subject to:

f_{a,b} + f_{a,s} - f_{c,a} &= 0 \\ f_{b,t} + f_{b,d} - f_{a,b} - f_{s,b} &= 0 \\ &\ldots \text{ are flow conservation constraints} \\ 0 \le f_{a,b} &\le 8 \\ 0 \le f_{c,a} &\le 4 \\ &\ldots \text{ are capacity constraints} \end{aligned}$$

General Approach ${\sum }_{v\in V}{f}_{sv}-{\sum }_{v\in V}{f}_{vs}$ Subject to:

Maximise

\sum_{v \in V} f_{uv} &= \sum_{v \in V} f_{uv} &&\text{ for each } u \in v - \{s,t\} \\ f_{uv} &\le h(u,v) &&\text{ for each } u,v \in V \\ f_{uv} &\ge 0 &&\text{ for each } u,v \in V \end{aligned}$$ **Objective function**: maximise net flow from the source **First set of constraints**: satisfy flow conservation for each node that is not the source nor the sink **Second set of constraints**: not allowing more flow through an edge than its capacity $h(u,v)$ **Third set of constraints**: making sure all flows are non-negative

A note on variables $n^2$ variables in our flow, with $2n^2+n-2$ constraints. We may not be able to solve this with certain software (CPLEX is limited to no. of variables you can use), a good practice is to omit variables $f_{bd}$ if $(b,d)\notin E$.

We have

Example: Minimum-cost Flow LP

Minimum-cost flow problem

In the minimum-cost flow problem, we want to find a flow that satisfies all supply and demand and has the minimum possible cost. Formally, a flow in the network $G$ is a function $f:E\to R$ assigning flows to edges, $f(v,w)$ (non-negative amount of flow on edge $v$ to $w$), which satisfies the capacity constraints and flow conservation constraints.

The input is a flow network $G=(V,E,u,c,d)$ where:

• $V$ is a set of nodes
• $E$ is a set of directed edges
• For each edge $(v,w)\in E$, $u(v,w)\ge 0$ is the capacity of edge $(v,w)$ We label each edge (x, y)
• For each node $v\in V$, (as in flow-feasibility problem) $|d(v)|$ is the (initial) supply (if $d(v)>0$) or demand (if $d(v)<0$) at $v$. 1st number on each edge, x ${\sum }_{v\in V}d(v)=0$
• For each edge $(v,w)\in E$, $c(v,w)\ge 0$ is the cost of one unit of flow on edge $(v,w)$. 2nd number on each edge, y

Link to original

Specific Example

Our decision variables are $f_{a,b},f_{a,g},f_{b,p},\dots$ ($f_{v,w}$ is flow on edge $(v,w)$)

Minimise $3f_{a,b}+f_{b,p}+2f_{a,g}+\dots$ Subject to:

f_{a,b} + f_{a,g} - f_{c,a} &= 8 \\ f_{p,e} - f_{b,p} - f_{d,p} &= -9 \\ &\ldots \text{ are flow conservation constraints} \\ 0 \le f_{a,b} &\le 8 \\ 0 \le f_{c,a} &\le 4 \\ &\ldots \text{ are capacity constraints} \end{aligned}$$

General Approach ${\sum }_{(u,v)\in V}c(u,v)f_{uv}$ Subject to:

Minimise

\sum_{v \in V} f_{uv} - \sum_{v \in V} f_{vu} &= d(u) &&\text{for each } u \in V \\ f_{uv} &\le u(u,v) &&\text{for each } u,v \in V \\ f_{uv} &\ge 0 &&\text{for each } u,v \in V \end{aligned}$$ **Objective function**: minimise total cost of flow **First set of constraints**: satisfy flow conservation for each node $u$ with net flow $d(u)$; if $d(u) > 0$, we say $u$ is a source supplying $d(u)$ units; if $d(u) < 0$, we say that $u$ is a sink with a demand of $|d(u)|$ units of flow **Second set of constraints**: not allowing more flow through an edge than its capacity **Third set of constraints**: making sure all flows are non-negative

Numeric Optimisation

Slides 27 onwards simply introduce the next few topics.

May be worth copying some examples.

Local minima are global minima (in convex optimisation)

This fact will save us time.