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

  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?

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.