Friday, March 19, 2010

A conic quadratic representable set.

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
 

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

  1. It easy to find a feasible solution.
  2. There is huge gap between the LP relaxation and the feasible solution.
  3. It is hard to close the gap. A huge number of nodes is required and the standard cuts works poorly.
Then leads to the question. What is good cuts for this type of problems?