Help on convex quadratic IP with cut generation


#1

Hi,

I am solving a convex quadratic integer programming problem,

min f( x , y )
s.t. Ax + By <= b
      y being integral vector

where f is a convex quadratic function.

I have a set of valid inequalites for the feasible region (x,y) lives in, and I have defined a valid CutGeneration function for them.

The question is, when I use piecewise linear approximation of f some of my user cuts are used during solving.

m = Model( solver = gurobi() )

@variable x
@variable y , Bin
@variable c

@constraint of  Ax + By <=b
@constraint c >= linear_approximation_f(x,y)

@objective Min c

function CutGeneration
if...
  println("User cut!")
  @usercut(  ax + by <= d )
end

The output log is like

Cutting planes:
  User: 8
  Gomory: 11
  Cover: 7
  Implied bound: 278
  Clique: 1
  MIR: 85
  Flow cover: 156
  GUB cover: 9

When I move to exactly solve quadratic objective in epigraph form

# everything is the same, except exact form of f is used
m = Model( solver = gurobi() )

@variable x
@variable y , Bin
@variable c

@constraint of  Ax + By <=b
@constraint c >= f(x,y)

@objective Min c

function CutGeneration
if...
  println("User cut!")
  @usercut( ax + by <= d)
end

During solving process, julia is really printing the sentences user cut! , which means the cut generation function correctly goes to the step of add user cut.

But the output log is like

Cutting planes:
  Gomory: 5
  Cover: 7
  Implied bound: 97
  MIR: 49
  Flow cover: 90
  GUB cover: 6
  Zero half: 3

Can someone help me on what happend ?

I put convex objective into epigraph form because later I have to implement another cutting plane on the epigraph of f in space (x,y,c).


#2

It’s difficult to comment on Gurobi internals, but maybe your user cuts are redundant in the second model, so they are not added to the model?


#3

The feasible region of (x,y) are the same for both models. I am quite sure it is not redundant.

So is it better that I pose this problem to a website that is more related to gurobi ?


#4

So is it better that I pose this problem to a website that is more related to gurobi ?

Maybe, but then be prepared to provide example code in Python or some other supported language.