Question $1[36]$

$($a$)$ Within the context of an optimisation problem, explain the meaning of each of the following problem

components: $[6]$

i$.$ An objective function,

ii$.$ The decision variables,

iii. The constraints.

$($b$)$ A variety of different classes of optimisation problems exist and it is important to be able classify a

given problem as belonging to one of these classes before attempting to solve the problem, because

algorithms for solving optimisation problems are typically tailored for certain classes of problems.

Provide a concise description for each of the following classes of optimisation problems. $[16]$

i$.$ Combinatorial optimisation problems,

ii$.$ Integer programming problems,

iii. Linear programming problems,

iv$.$ Nonlinear programming problems,

v$.$ Quadratic programming problems,

vi$.$ Mixed integer programming problems,

vii. Robust optimisation problems,

viii. Stochastic programming problems.

$($c$)$ Complete the following diagram by associating each of the problem classes in $($b$)$ above with one of

the $($leaf$)$ categories in the following classification tree: $[8]$

Optimisation

Stochastic Deterministic

Continuous Discrete

$($d$)$ Describe the differences $($in terms of solution quality returned and execution speed$)$ between the following three types of algorithms for solving optimisation problems: $[6]$

i$.$ An exact algorithm,

ii$.$ An approximate algorithm $($such as a heuristic or metaheuristic$),$

iii. An approximation algorithm.

Question $2[26]$

Consider the following examples of real$-$world optimisation problems. For each problem, define appropriate

decision variables, and formulate the objective function and constraints mathematically. Finally, classify the

optimisation problem according as belonging to one of the classes mentioned in Question $1($b$).$ You are not

required to solve the problems.

$($a$)$ WooD$$ecor manufactures two types of wooden d$$ecor items: Floating shelves and rails. A floating shelf

sells for R$500$ and is manufactured from R$200$ worth of raw materials. Each floating shelf manufactured

increases WooD$$ecor$$s variable labour and overhead costs by R$250.$ A rail sells for R$450$ and is manufactured from R$220$ worth of raw materials. Each rail manufactured increases WooD$$ecor$$s variable

labour and overhead costs by R$200.$ The manufacturing of wooden floating shelves and rails requires

two types of skilled labour: Carpentry labour and finishing labour. A floating shelve requires $3$ hours

of finishing labour and $1\mathrm{.}5$ hours of carpentry labour, while a rail requires $1\mathrm{.}5$ hours of finishing labour

and $1\mathrm{.}5$ hours of carpentry labour. Each week, WooD$$ecor can obtain all the raw materials it requires,

but only $150$ finishing hours and $120$ carpentry hours are available each week. Demand for rails is

unlimited, but at most $30$ floating shelves are bought each week. WooD$$ecor wishes to maximise its

weekly profit $($revenues less costs$).$ Formulate an optimisation problem that will inform of WooD$$ecor

how to go about maximising its weekly profit. $[10]$

$($b$)$ Investo is considering four investment options. Investment $1$ is expected to yield a net present value

$($NPV$)$ of R$12000$; investment $2,$ an NPV of R$16500$; investment $3,$ an NPV of R$9000$; and investment

$4,$ an NPV of R$6000.$ Investing in an investment requires a certain cash outflow at the present time:

Investment $1,$ R$3750$; investment $2,$ R$5250$; investment $3,$ R$3000$; and investment $4,$ R$2250.$ Investo

can either invest fully in an investment, or not at all $($fractions of investments are not possible$).$

Currently, R$10500$ is available for investment and Investo cannot invest in more than two options.

Formulate an optimisation problem whose solution will inform Investo how to maximize the NPV

obtained from the investments selected. $[10]$

$($c$)$ Suppose you aim to firstly, find high$-$quality hyper$-$parameter values for a one layer perceptron, i$.$e$.$

standard feedforward neural network comprising one hidden layer. Secondly, you want to optimise the

neural network architecture, specifically the hidden layer. Propose appropriate decision variables and

one or more objective function to achieve this aim. $[6]$

Question $3[10]$

The complexity of an optimisation problem relates to the computational effort expended by the best algorithm available for solving the problem. In order to formalise this notion, each optimisation problem is

associated with underlying decision problem $($posed as a yes$-$no question$),$ which can be categorised into

different complexity classes, of which the most prominent are P and NP$.$

$($a$)$ Provide a concise definition for each of the following complexity classes for decision problems associated

with optimisation problems: $[8]$

i$.$ The complexity class P$,$

ii$.$ The complexity class NP$,$

iii. The complexity class NP$-$complete,

iv$.$ The complexity class NP$-$hard.

$($b$)$ Draw a venn$-$diagram illustrating the inclusion and exclusion relationships between the complexity

classes in $($a$)$ above. $[2]$

Question $4[8]$

$($This question is only applicable to O