• Uncategorized
  • 2

Quick Tip: Problem Transformations for Linear Optimization

Share

Linear Optimization (aka Linear Programming, LP) is one of the earliest improvement in Operations Research history. Despite the fact that there are more than 73 years passed since Kantorovich modeled first LP, it is still widely used in many sectors. In order to use some algorithms (ie. for Simplex, problem should be in standard form), the model should be in a certain form. In here, we will briefly show how one problem can be transformed to apply these algorithms.

1) Objective Function

A problem can be easily changed to minimization or maximization type. Assume our problem is given in the form as

\min_{x}{c}^{T}x

and we want to solve this problem as a minimization problem. All we need to do is, multiply both function and term with magical number, -1, and change min to max. So equivalent form is

-\max_{x} {-c}^{T}x

2) Constraint – Inequality direction: \geq to \leq and vice versa

A greater than or equal to (\geq) inequality can be transformed to less than or equal to (\leq), similarly using our magic number, -1. We need to multiply both sides, and change the direction.

ax \geq b \rightarrow_{-1} -ax \leq -b

3) Constraint – Inequality to Equality

While transforming an inequality to equality, we need to add a new (slack) nonnegative variable. Direction of the inequality is important, since it changes multiplier of the slack variable. For a \leq we can add a slack variable with +1 coefficient. So, if we are transforming the following equation;

a_{1}x_{1}+a_{2}x_{2} \leq b

into an equality, the new form should be

a_{1}x_{1}+a_{2}x_{2}+s =b

s \geq 0

 And for \geq inequality;

a_{1}x_{1}+a_{2}x_{2} \geq b

and we can perform transformation as;

a_{1}x_{1}+a_{2}x_{2}-s =b

s \geq 0

4) Constraint – Equality to Inequality

This time things are a little bit different. Here, we can use the logic that, an equality is the intersection of greater than or equal to and less than or equal to inequalities. Assume we have;

ax=b

and then we can write it in the following form;

ax \geq b

ax \leq b

 5) Variable – Forcing variables to be nonnegative

a) If a variable is set to be nonpositive;

x \leq 0

then it can be easily transformed to another by simply multiplying with -1. Let x'=-x and we get;

x' \geq 0

and you need to transform all x’s to -x' in constraints as well.

b) If a variable is free;

x \, free

then there is a traditional way. In this way, you need to add two nonnegative variables to define x. Let x_1, x_2 be our nonnegative variables (x_1 \geq 0, x_2 \geq 0 ) then set

x = x_1-x_2

This is meaningful, because all numbers can be written as a difference of two nonnegative number. So practically, we need to change all x’s in constraints to x_1-x_2

This transformation is especially useful if you will use Simplex Algorithm. It is because, since x_1 \, and \, x_2 are obviously dependent, they cannot be a basic variable at the same time. Therefore, for instance let say, -5, simplex will select x_1=0, x_2=5 but not x_1=2, x_2=7. So it’s a useful transformation.

Reference: Sobel, Joel. “Linear Programming Notes V Problem Transformations.” N.p., n.d. Web. 5 Sept. 2012. <http://www.econ.ucsd.edu/~jsobel/172aw02/notes5.pdf>.

Photo taken from Prof. Katta G. Murty

Sertalp Bilal Çay

PhD Candidate and Teaching Assistant in Industrial and Systems Engineering Department at Lehigh University. Researcher on Conic Optimization, Inventory Theory, Supply Chain Management and Simulation. Blog: sertalpbilal.com