Assume you have the problem

min v

st. |x|^3 / y^2 <= v, y>=0

A customer asked me if that can be formulated as conic quadratic problem. Indeed it can and my solution is

z^2 <= 2ty

2t <= a

a^2 <= 2 uv

z = 2u

x <= z

-x <= z

0 <= y,t,u,v

This blog is about my work at MOSEK ApS where I am the CEO, a computer programmer and tea maker.

## Friday, March 19, 2010

### Effective cuts for mixed integer goal programs

Assume you have the problem

min c'x + ||Fx-f||_1

st. A x = b

x binary

This is sort of a goal programming model I have seen frequently. Now the typical LP formulation is

min c'x +e'(s+t)

st. F x - f = s-t

A x = b

s,t >= 0

x binary

Note this model includes continuous variables too. At least for an application I have seen then

min c'x + ||Fx-f||_1

st. A x = b

x binary

This is sort of a goal programming model I have seen frequently. Now the typical LP formulation is

min c'x +e'(s+t)

st. F x - f = s-t

A x = b

s,t >= 0

x binary

Note this model includes continuous variables too. At least for an application I have seen then

- It easy to find a feasible solution.
- There is huge gap between the LP relaxation and the feasible solution.
- It is hard to close the gap. A huge number of nodes is required and the standard cuts works poorly.

Subscribe to:
Posts (Atom)