# What are the best modelling tricks for linear programming?

 1 This community wiki asks everyone to share important, useful, surprising or efficient modelling tricks when setting up a linear program. I’ll share a few myself in order to get started. This question is marked "community wiki". asked 07 Jan '16, 11:54 Petter 23●7 accept rate: 0%

 2 Petter's modeling of absolute values extends to modeling of more general objectives involving minimizing the maximum. When you minimize |x| in the objective, your are minimizing the maximum of x and -x. This extends to minimizing the maximum of an arbitrary number of linear expressions, i.e. min max {c1'x, c2'x,...,cn'x} can be expressed as min w s.t. w >= c1'x w >= c2'x ... w >= cn'x Petter considered the specific case of n = 2, x and cj being vectors of dimension 1, c1 = 1 and c2 = -1. Maximin expressions work in the analogous way. answered 14 Jan '16, 14:42 Ed Klotz 236●2●3 accept rate: 11%
 1 The non-linear term $$|x|$$ can be added to the objective function of a linear program as follows: Add $$w$$ to the objective function. Add the two constraints $$w \ge x$$ and $$w \ge -x$$. This only works for minimization. Maximization problems can have $$-|x|$$ added in the analogous way. link This answer is marked "community wiki". answered 07 Jan '16, 11:54 Petter 23●7 accept rate: 0% 2 as a note, this only works for minimization problems (07 Jan '16, 13:21) Andreas That is correct. I’ll update the answer. (07 Jan '16, 16:01) Petter 3 A common alternative is to use two nonnegative variables and one equality: minimize $$w^+ + w^-$$, with constraint $$w^+-w^-=x$$. (11 Jan '16, 12:18) Rob Pratt
 1 The K largest terms of a vector $$x$$ can be optimized in the following way (for a minimization problem): Introduce new variables $$v\ge 0$$ with the same size as $$x$$ and a scalar $$q$$. Add $$Kq + \sum_i v_i$$ to the objective function. Add constraints $$v_i \le x_i + q$$ for all $$i$$. This is from a comment by Michael Grant here. link This answer is marked "community wiki". answered 07 Jan '16, 11:55 Petter 23●7 accept rate: 0% Matthew Salt... ♦ 4.7k●3●10
 1 Charnes-Cooper transformation to linearize a linear-fractional programming problem: https://en.wikipedia.org/wiki/Linear-fractional_programming#Transformation_to_a_linear_program answered 14 Jan '16, 16:08 Rob Pratt 1.2k●2●6 accept rate: 28%
 0 Consider solving the dual LP instead, then using the dual variables of the optimal dual solution to obtain the answer of interest. In general, the run times of the simplex and barrier algorithm depend more on the number of rows in the constraint matrix than the number of columns. So, if your LP has a small aspect ratio (i.e., it has significantly more constraints than variables), solving the dual model can be more efficient. Specific to the barrier algorithm, dense columns can pose challenges to performance in a way that dense rows do not, so solving the dual LP can help if the primal has dense columns but lacks dense rows. answered 14 Jan '16, 14:29 Ed Klotz 236●2●3 accept rate: 11% Why is this not normally done automatically by the solver? Or is it done by some? (14 Jan '16, 16:56) Petter 1 CPLEX has a presolve dual parameter that accomplishes this. By default, it uses some of the logic I described to decide which LP to solve, as well as some other criteria. You can also set this parameter to either force or forbid CPLEX from solving the dual model. Unfortunately this currently only applies to LPs, so it won't help for QPs or QCPs. Regarding node LPs of a MIP solve, it only applies when the barrier method is used (which has other disadvantages due to lack of restarts). I believe that some or all of the other commercial solves have this feature too. (14 Jan '16, 18:21) Ed Klotz
 toggle preview community wiki

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

Asked: 07 Jan '16, 11:54

Seen: 1,385 times

Last updated: 14 Jan '16, 18:21

### Related questions

OR-Exchange! Your site for questions, answers, and announcements about operations research.