Task $1($Design Space Exploration using ILP solver$)$

The optimization problem stated in worksheet $1$ can be also formulated as an integer linear

programming problem. Integer Linear Programming $($ILP$)$ is a well established technique to

describe optimization problems in a mathemtical notation using a linear objective function and

linear constraints. The objective function and constraints are defined by using decision

variables, whose $($integer$-)$value should be determined by solving the optimization problem, i$.$e$.$

minimizing or maximizing the result of the objective function, while respecting all given

constraints. Although this problem is computational intractable, there are powerful tools to

solve many problems in a reasonable amount of time. In this worksheet you should:

Provide an ILP$-$fomulation for the optimization problem from worksheet $1,$ task $1($d$).$

Solve the problem using the Gurobi ILP$-$solver that can be downloaded from

Download requires a

registrations and licence. License is available for free.

In Moodle a Quick Start Guide can be downloaded that describes the license request, software

download and installation, and a getting started example that introduces into the ILP

formulation of problems and the gurobi syntax for implementing and solving the ILP problem

$($pages $23$ to $28$ of the Quick Satrt Guide$).$ Use this example as a starting point. Then solve in

the same way the optimization problem from task $1($d$).$

Tipp: it can be helpful for this optimization problem to use decision variables whose values are

restricted to be either $0$ or $1.$ Such a variable $($e$.$g$.$ DCT$\_$on$\_$P$1)$ then can represent a situation

that a particular function $($like the DCT$)$ is implemented $(=1)$ or not implemented $(=0)$ on a

specific processing element $($like on P$1).$