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's gravatar image

Petter
236
accept rate: 0%


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.

link

answered 14 Jan '16, 14:42

Ed%20Klotz's gravatar image

Ed Klotz
23623
accept rate: 11%

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's gravatar image

Petter
236
accept rate: 0%

edited 07 Jan '16, 16:03

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

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's gravatar image

Petter
236
accept rate: 0%

edited 10 Jan '16, 13:05

Matthew%20Saltzman's gravatar image

Matthew Salt... ♦
4.7k310

Charnes-Cooper transformation to linearize a linear-fractional programming problem: https://en.wikipedia.org/wiki/Linear-fractional_programming#Transformation_to_a_linear_program

link

answered 14 Jan '16, 16:08

Rob%20Pratt's gravatar image

Rob Pratt
1.2k26
accept rate: 28%

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.

link

answered 14 Jan '16, 14:29

Ed%20Klotz's gravatar image

Ed Klotz
23623
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
Your answer
toggle preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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:

×231
×4

Asked: 07 Jan '16, 11:54

Seen: 1,266 times

Last updated: 14 Jan '16, 18:21

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