Originally posted by: StatBeginner

I am trying to solve a two-stage optimization problem using benders decomposition. The basic problem looks like:

min_x (f(x) + min_y(g(y)))

where g(y) is a linear program that can be solved for a fixed value of the outer decision variable x. f(x) is a function that is linear in terms of x. I implemented the specific code using CPLEX's python API, by using callbacks and generating constraints on the fly using the callbacks. The results are as expected.

Now the problem is slightly modified and f(x) is a function that is quadratic in terms of x. However, the problem quits saying that No Solution Exists, and the callbacks are never called. This is surprising as I can't find a reason why a solution shouldn't exist. When I tried to debug the code, I find that while the callback function for cut generation is called after the "mipopt(env, lp)" function when the objective wasn't quadratic, it is not called now.

The basic structure of the problem is attached as an image, in which "u" represents the inner problem, cuts for which are generated. The only difference in the two problems (one linear and the other quadratic) is the presence of the x0^2 term in the objective.

The code for the Master Problem is:

def createMasterProblem(x,u,budget,alpha,beta)

    cpx.objective.set_sense(cpx.objective.sense.minimize)
    
    for i in range(numNodes):
        varName = "x."+str(i)
        q.append(cpx.variables.get_num())
        cpx.variables.add(obj = [alpha],
                              lb = [0.0], ub = [1], types = ["I"],
                              names = [varName])
    
        
    varName = "u"
    u.append(cpx.variables.get_num())
    cpx.variables.add(obj = [1],
                      lb = [-cplex.infinity],
                      ub = [cplex.infinity],
                      types = ["C"],
                      names = [varName])
    
    
    #add the budget constraint
    theVars = []
    theCoeffs = []
    for i in range(numNodes):
        theVars.append(x[i])
        theCoeffs.append(1)
    cpx.linear_constraints.add(lin_expr = [cplex.SparsePair(theVars,theCoeffs)],
                                   senses = ["E"], rhs = [budget])
        
    #create the quadratic part of the objective function
    qmat = [[[0, 1, 2, 3], [beta, 0.0, 0.0, 0.0]],
           [[0, 1, 2, 3], [0.0, 0.0, 0.0, 0.0]],
           [[0, 1, 2, 3], [0.0, 0.0, 0.0, 0.0]],
           [[0, 1, 2, 3], [0.0, 0.0, 0.0, 0.0]]]
    cpx.objective.set_quadratic(qmat)
    

Any ideas what might be going wrong? As a matter of fact, even if all the quadratic coefficients are set to 0 (which makes it equal to exactly the same outer problem), the problem won't find a solution, which is strange.

You should run the conflict refiner to figure out why CPLEX thinks your problem is infeasible.

I'm not a Python user, and I'm having a bit of a problem with the dimensions of qmat (4 x 2 x 4 ??). Shouldn't qmat be a square matrix?

qmat looks correct to me (although I didn't test it).  Those lists correspond to the variable indices and the associated coefficients.  See here.

Thanks, that makes sense now. I don't know much about how CPLEX solves QPs, but I do know that it (usually?) uses an interior point method. Could the budget constraint (equality) somehow bugger the IP method when it's apparently not a problem for simplex?