benders decomposition

[Víctor Hugo Hinojosa M]

Hi folks,

I'm studying a dynamic transmission expansion planning applied to power systems, so I'd like to know if there is an algorithm using a benders decomposition.

The optimization problem is mixed-integer so that I'm thinking to separate the binary and the real problems in order to solve with benders cut. I hope you can give some comments about this idea.

Regards,

Vh

[John Hedengren]

Victor, 

The MATLAB and Python interfaces of APMonitor enable you to implement this technique. Bender's decomposition is not built into APMonitor.

In the case of Bender's decomposition, the key operations are (1) adding constraints (2) detecting unbounded solutions and (3) constructing the unbounded ray.

Bender's decomposition also involves creating and maintaining a subproblem that generates the constraints you add. That subproblem depends on the specific model being solved. You may find it easier to use the low-level Matlab operations found here:

http://www.mathworks.com/matlabcentral/fileexchange/35720-minlp--mixed-integer-nonlinear-programming

I hope this helps. 

Best regards, 

John Hedengren

 

Sent on a Sprint Samsung Galaxy S® 5

--
--
APMonitor user's group e-mail list.
- To post a message, send email to apmo...@googlegroups.com
- To unsubscribe, send email to apmonitor+...@googlegroups.com
- Visit this group at http://groups.google.com/group/apmonitor

---
You received this message because you are subscribed to the Google Groups "apmonitor" group.
To unsubscribe from this group and stop receiving emails from it, send an email to apmonitor+...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Víctor Hugo Hinojosa M]

Dear John,

Thank you so much for the information.

My idea is to implement a benders model to dynamic expansion planning. Right now, I've programmed a B&B model applied to static transmission expansion planning model using an interior-point primal-dual algorithm to solve the nonlinear model. In addition, we've included the power losses using a quadratic function. I'm using APMonitor to validate the B&B solution, and both solutions considering losses are the same. Our next step is to implement a benders decomposition to figure out the dynamic decision model.

I hope we can exchange some ideas about this proposal. Besides we want to know if the APMonitor interface can show the Lagrange multipliers for both constraints (equality and inequality).

Have a great day.

Vh

[John Hedengren]

Victor,

 

I’ll be glad to work with you on this. APMonitor converts inequality constraints into equality constraints with slack variables. Lagrange multipliers for constraints are available is you set diaglevel to 2 and retrieve the file ‘apm_lam.txt’. Below is some code that should work to retrieve the Lagrange multipliers:

 

apm_option(s,a,’nlc.diaglevel’,2);

apm(s,a,’solve’);

apm_get(s,a,’apm_lam.txt’)

 

You’ll have the apm_lam.txt file in your working directory that will contain all of your Lagrange multipliers.

 

Let me know if you have any additional questions.

 

Best regards,

 

John Hedengren

[sau...@iimidr.ac.in]

Dear Sirs

I am trying to implement Benders decomposition to solve a MINLP using Python+ Gekko. My subproblem is an NLP. Please suggest how to obtain the dual variable values (of the variable bounds) from the NLP solution to pass on to Master problem. I am attaching the code to my subproblem for reference. Please help me out.

def SP(Y,Z):
    m = GEKKO()
    m.DIAGLEVEL = 2
    # initialize variables:
    x = [0 for i in cetps]
    p = [0 for i in cetps]
    f = [0 for i in cetps]
    for i in cetps:
        x[i-1]=m.Var()
        p[i-1]=m.Var()
        f[i-1]=m.Var()
    ## calculting upper and lowe bounds on Xi values:
    ub = [0 for i in cetps]
    lb = [0 for i in cetps]
    eb = [0 for i in cetps]
    for i in cetps:
        ub[i-1] = K1_i
        lb[i-1] = K2_i
        eb[i-1] = K3_i

    ##Setting
    for i in cetps:
        x[i-1].value = ub[i-1] ##initial value
        x[i-1].lower = lb[i-1]
        x[i-1].upper = ub[i-1]
        p[i-1].upper = eb[i-1]
        p[i-1].lower = eb[i-1]
    #objective:
    m.Obj(0.682*sum(f[i-1]*pow(p[i-1],0.8340) for i in cetps) + sum(x[i-1] for i in cetps))

    for i in cetps:
        if ub[i-1] > 0:
            m.Equation(f[i-1] >= pow(x[i-1],-0.3565))
        else:
            m.Equation(f[i-1] == 0)

    #Set global options
    m.options.IMODE = 3 #steady state optimization

    #solve simulation
    m.solve()

    #Results:
    X = {}
    P = {}
    U = {} #dual variable for the upper bound on x
    V = {} #dual variable for the lower bound on x
    W = {} #dual variable for the equality constraint on p-variable
    for i in cetps:
        U[i] = 0
        V[i] = 0
        W[i] = 0
    for i in cetps:
        X[i] = x[i-1].value[0]
        P[i] = p[i-1].value[0]
        print "X-i ", X[i]
        print "P-i ", P[i]
 #### How to obtain the dual values???

    XPD = {}
    XPD[1] = X
    XPD[2] = P

best regards

Saurabh 

[John Hedengren]

Dear Saurabh,

 

You can access Lagrange multipliers if the solver reports them. If you set the diagnostic level to 2 and look in your run directory, there is a file called apm_lam.txt that contains the Lagrange multipliers.

 

    m.options.IMODE = 3 #steady state optimization

    m.options.SOLVER = 1 # APOPT solver

    m.options.DIAGLEVEL = 2 # diagnostic level

    #solve simulation

    m.solve()

 

    # retrieve lagrange multipliers from apm_lam.txt

    print(m.path)  # apm_lam.txt is in local directory

 

However, some solvers do not report the Lagrange multipliers so I recommend using the APOPT solver because it does report the Lagrange multipliers and solves MINLPs. You’ll need to parse the apm_lam.txt file in Python, unfortunately.

 

Best regards,

 

John Hedengren

[Saurabh Chandra]

Dear Dr. Hedengren

thanks a lot for your help. I am able to run my Bender's decomposition algorithm for the MINLP I am working on. The results are good. I added some lines of code to parse the lagrangian multipliers (LMs). The suggested file name was not found, although the LMs were recorded in a csv file, named results.csv, in a directory described by the m.path command.

    m.options.IMODE = 3 #steady state optimization
    m.options.solver = 1 #APOPT solver
    m.options.DIAGLEVEL = 2 #diagnostic level
   
    m.solve(disp=False)
    ##print(m.path)
    results = open(str(m.path)+"/results.csv") # to extract the file which holds LMs
    res = csv.reader(results, delimiter=',') # it is a csv file with the name results.csv

best regards

Saurabh 

- To unsubscribe, send email to apmonitor+unsubscribe@googlegroups.com

- Visit this group at http://groups.google.com/group/apmonitor

---
You received this message because you are subscribed to the Google Groups "apmonitor" group.

To unsubscribe from this group and stop receiving emails from it, send an email to apmonitor+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--
--
APMonitor user's group e-mail list.
- To post a message, send email to apmo...@googlegroups.com

- To unsubscribe, send email to apmonitor+unsubscribe@googlegroups.com

- Visit this group at http://groups.google.com/group/apmonitor

---
You received this message because you are subscribed to the Google Groups "apmonitor" group.

To unsubscribe from this group and stop receiving emails from it, send an email to apmonitor+unsubscribe@googlegroups.com.

[Saurabh Chandra]

Dear sirs

Sorry for bothering again. I am still not sure with the working of Lagrangian multipliers in NLP using Gekko. The suggested csv file in my last mail does not contain LMs. I cannot find the file apm_lam.txt in the local directory accessed through the path. Please suggest me how to get this file. I am attaching the list of files available in the path folder.

folder address: c:\users\saurabh\appdata\local\temp\tmpepgcoygk_model0

best regards

Saurabh 

[Logan Beal]

Since the apm_lam.txt file is rarely used and is only available with higher diagnostic levels, GEKKO does not automatically retrieve this file from the server. Retrieving it is possible, but would require some effort. Instead, since you're using Windows, I recommend a local solve. This way you will have all the files created by the executable. 

m = GEKKO(remote=False)

[Saurabh Chandra Pathak]

Dear Mr. Beal

 

Thanks for the inputs. Now, I am able to access the file apm_lam.txt by following your instructions. The issue is that it always shows 0 values for the Lagrangian multipliers. I am using this NLP:

 

Original problem:

minimize sum_ i in C:  x_i^-0.3565 * p_i^0.8340 + x_i

subject to:

    x_i <= ub_i

    x_i >= lb_i

    p_i == eb_i

    x_i, p_i >= 0

 

I have attached the python code to solve this NLP for your reference and also the Lagrangian multipliers file for the NLP, which shows all LMs to be 0. This should not be happening as some constraints do have non-zero dual values. To estimate true values of LMs, I have rerun the NLP after incrementing the RHS of different constraints, which shows changes in the value of the objective, which implies for some constraints the dual variables should be non-zero. Please suggest how can I get correct LM values of the NLP constraints.

 

Best regards

 

Saurabh Chandra

 

The following are the run prints in the Python shell.

 

('Error:', 'At line 7248 of file files.f90\nTraceback: not available, compile with -ftrace=frame or -ftrace=full\nFortran runtime error: Deallocated a bad pointer\n')

c:\users\scp\appdata\local\temp\tmp7omlb3gk_model0

X[ 1 ] = 2500.0

P[ 1 ] = 100000.0

X[ 2 ] = 2500.0

P[ 2 ] = 100000.0

SPobj= 6240.07729719

>>> ### incrementing x-ub constraint by 1

>>> ### i.e. m.Equation(x[i-1] - ub[i-1] <= 1)

>>> ================================ RESTART ================================

>>>

('Error:', 'At line 7248 of file files.f90\nTraceback: not available, compile with -ftrace=frame or -ftrace=full\nFortran runtime error: Deallocated a bad pointer\n')

c:\users\scp\appdata\local\temp\tmpiauy8lgk_model0

X[ 1 ] = 2500.0

P[ 1 ] = 100000.0

X[ 2 ] = 2500.0

P[ 2 ] = 100000.0

SPobj= 6240.07729719

>>> ### incrementing x-lb constraint rhs by 1

>>> ### i.e. m.Equation(-x[i-1] + lb[i-1] <= 1)

>>> ================================ RESTART ================================

>>>

('Error:', 'At line 7248 of file files.f90\nTraceback: not available, compile with -ftrace=frame or -ftrace=full\nFortran runtime error: Deallocated a bad pointer\n')

c:\users\scp\appdata\local\temp\tmpnck0jjgk_model0

X[ 1 ] = 2499.0

P[ 1 ] = 100000.0

X[ 2 ] = 2499.0

P[ 2 ] = 100000.0

SPobj= 6238.25423228

>>> ### incrementing p-eb constraint rhs by 1

>>> ### i.e. m.Equation(p[i-1] - eb[i-1] == 1)

>>> ================================ RESTART ================================

>>>

('Error:', 'At line 7248 of file files.f90\nTraceback: not available, compile with -ftrace=frame or -ftrace=full\nFortran runtime error: Deallocated a bad pointer\n')

c:\users\scp\appdata\local\temp\tmpofxblegk_model0

X[ 1 ] = 2500.0

P[ 1 ] = 100001.0

X[ 2 ] = 2500.0

P[ 2 ] = 100001.0

SPobj= 6240.08763943

[John Hedengren]

Dear Saurabh,

 

Attached is a script that displays the LMs. I told you earlier that it is the APOPT solver that returns the LMs but it is only the BPOPT and IPOPT solvers. I apologize for the incorrect information. If you need the LMs with the APOPT solver, I could add that to the list of development items.

 

# print Lagrange multipliers

# available with SOLVER = 2 (BPOPT) and 3 (IPOPT)

lm = np.loadtxt(m.path+'\\apm_lam.txt')

print(lm)

 

Best regards,

 

John Hedengren