CODEWITHSUNDEEP
mathematical-optimizationcplexnonlinear-optimizationquadratic-programming
statBeginner
statBeginner

Reputation: 849

CPLEX: Benders Decomposition with Quadratic Term in the Outer Optimization

The problem is cross posted at : IBM CPLEX Forum

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

min_x (f(x) + min_u(g(u)))

where g(u) 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. 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 structure of the problem is

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[i]],
                          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)

One of the issues that really surprises me is that if coefficients of all the quadratic terms are set to 0, essentially making the problem the same as before, even then solve() returns a message saying "No Solution Exists".

Upvotes: 0

Views: 285

Answers (1)

Harald Held
Harald Held

Reputation: 1

Verify Beta value:

Check the value set for beta. If the value is smaller then 0 convex and CPLEX will not be able to handle it.

Upvotes: 0

Related Questions