ILP -- Integer Linear Programming

ILP (Integer Linear Programming) is the OTAWA class set dedicated to solving ILP optimization problems. More...

Classes
class	otawa::ilp::AbstractConstraint
	Constraint generated by AbstractSystem. More...
class	otawa::ilp::AbstractSystem
	This class provides a convenient way to handle ILP systems in OTAWA. More...
class	otawa::ilp::Constraint
	This class is used to represent constraints in an ILP system with the following form: More...
class	otawa::ilp::Expression
	An expression allows to represent a sum of terms and may be used to represent the value of an aliased variable. More...
class	otawa::ilp::var
	Encapsulation for ilp::Var pointers for {ilp} expr user-fiendly interface. More...
class	otawa::ilp::cons
	Encapsulation for ilp::Constraint pointers for {ilp} expr user-fiendly interface. More...
class	otawa::ilp::model
	Encapsulation for ilp::System pointers for {ilp} expr user-fiendly interface. More...
class	otawa::ilp::System
	An ILP system is a colletion of ILP constraint that may maximize or minimize some object function. More...
class	otawa::ilp::Var
	A variable is an identifier used for performing ILP computation. More...
class	otawa::ilp::Alias
	An alias is a specific variable that represents an expressions. More...

Functions
var	otawa::ilp::x (Var *v)
	Convert an ilp::Var * to a var. More...

Detailed Description

ILP (Integer Linear Programming) is the OTAWA class set dedicated to solving ILP optimization problems.

For example, IPET module uses it to compute WCET. ILP problem try to optimize (maximize or minimize) a linear expression under a set of constraints. Constrains are made of linear expressions separated by a comparator (one of =, <, <=, >, >=).

ILP System

Basically, an ILP problem is represented by an ilp::System object. This object allows to define the optimization direction (maximize or minimize), the objective expression and to create Constraint.

Both objective expression and ilp::Constraint are made of sums of ilp::Term. A term is the multiplication of a variable by a floating-point coefficient.

As the set basic ILP classis (Constraint, Constraint and Term) are not very developer-friendly, we advice to use the expr programming model described below.

expr Interface

The expr interface allows writing C++ code that mimics mathematical way to write linear expression in ILP and to improve readability of code generating constraints. For example, the constraint "3 x + 5 y <= 10" will be written:

#include <otawa/ilp/expr.h>

model m(...);
var x(m), y(m);
m() + 3 * x + 5 * y <= 10;

The model construction accepts as argument a pointer of ilp::System.

If a sum of variables is needed at the left of the constraint, use the following form:

cons s = m();
for(i = 0; i < N; i++)
        s += v[i];
s <= 10;

If a sum of variables is needed at the right, use the following form:

cons c = m() + 10 == 0.;
for(i = 0; i < N; i++)
        c += v[i];

To get an ILP system, you can use the Manager::newILPSystem() method for example.

In fact, a constraint is built in two phases. In the first phase, the constraint object itself is built in the system and stored in an ilp::cons object after "m()". Addition of following terms will be accumulated at the left of the created constraint. As soon as the inequality operator is applied, the ilp::cons switches its state and the following additions of terms will be accumulated in the right part of the constraint. This techniques allows to handle efficiently the build of the constraint.

A side-effect of this techniques is that literal accumulation of terms on the right is completely inefficient. An object of type ilp:Expression that stores a list of terms is built and may duplicate itself according to the evaluation order of the right-side terms:

m() + 3 <= 4 * x + 5 * y;

A better form would be:

(m() + 3 <= 4 * x) + 5 * y;

As readability has been lost, simply reversing the constraint may prevent this issue:

m() + 4 * x + 5 * y >= 3;

ILP Plugin

OTAWA does not provide its own ILP solver but proposes plugin connecting with well-known off-the-shelf solvers like lp_solve or CPlex. The ILP plugins are usual plugins of OTAWA but must implements the class ilp::ILPPlugin.

Function Documentation

var otawa::ilp::x ( ilp::Var *  v )

inline

Convert an ilp::Var * to a var.

Useful to work-around C++ conversion limitations when the variable is stored in a property.

Parameters

v	Variable to convert.

Returns

Converted variable.

Referenced by otawa::ipet::BasicConstraintsBuilder::addEntryConstraint(), otawa::ets::ACSComputation::applyProcess(), otawa::ipet::BasicConstraintsBuilder::processBB(), otawa::cat::CATConstraintBuilder::processLBlockSet(), and otawa::ipet::BasicConstraintsBuilder::processWorkSpace().