Lagrangian Relaxation

[Steven Harrod]

Does anyone have an example of Lagrangian relaxation implemented in AMPL?
--
Steven Harrod
College of Business/QAOM
University of Cincinnati
859 225 1572

[Robert Fourer]

See the "trnloc2" problems at www.ampl.com/NEW/LOOP2.

 

Bob Fourer

4...@ampl.com

 

 

---

From: am...@googlegroups.com [mailto:am...@googlegroups.com] On Behalf Of Steven Harrod
Sent: Sunday, April 02, 2006 10:17 AM
To: AMPL Modeling Language
Subject: [AMPL 315] Lagrangian Relaxation

[wale.a...@covenantuniversity.edu.ng]

Hi Bob. I want to use the AMPL to solve a problem using Lagrangian Relaxation. The challenge is I want to use subgradient optimization to solve it. I have a bout three subproblems from the relaxation. Can you please help me out. Also do you have an explanatory note on the coding of "trnloc2" problems. My email address is vjad...@gmail.com. Thank you

[AMPL Optimization]

The "trnloc2" problems use a simple form of the subgradient optimization method as described in this reference:

M. Held, P. Wolfe and H.D. Crowder, "Validation of Subgradient Optimization."
Mathematical Programming 6 (1974) 62–88.

The attached lecture notes describe the same method, and also (on pages 8-9) the application that is seen in the "trnloc2" examples.

Bob Fourer
am...@googlegroups.com

=======

[Olawale Adeleke]

Thank you Bob for your timely response and your thought on the questions raised.

I will do as instructed and get back to you in case of any further assistance.

Olawale Adeleke.

--
You received this message because you are subscribed to a topic in the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/ampl/F6CHsiRnBrQ/unsubscribe.
To unsubscribe from this group and all its topics, send an email to ampl+uns...@googlegroups.com.
To post to this group, send email to am...@googlegroups.com.
Visit this group at https://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.

[Olawale Adeleke]

Hi Bob. Please can you help me with the full text of the paper you mentioned in your last mail. 

I mean "M. Held, P. Wolfe and H.D. Crowder, "Validation of Subgradient Optimization. Mathematical Programming 6 (1974) 62–88."

Thank you.

[Olawale Adeleke]

Good-day Bob. 

Thanks again for your quick response to my former mail. Please I need your help urgently on the attached. I am new to AMPL-CPLEX. I have tried the direct coding of my model on the ampl and it worked and gave the desired results. However, I want to solve a relaxed form of the same problem with the use of subgradient optimization but I am encountering some difficulties. The desired result is not coming forth.

In the model, constraint_1 was relaxed. There are two .dat files. One is a simple case, the other is a bit larger. The main issue is with the run file. I will appreciate any assistance on how to get a good solution.

The .run, .mod and .dat files are as attached. 

[Robert Fourer]

When you get messages like

presolve, constraint constraint_4['P5']:
all variables eliminated, but lower bound = 3e-08 > 0
presolve, constraint constraint_4['P4']:
all variables eliminated, but lower bound = 4e-08 > 0
presolve, constraint constraint_3['P5']:
all variables eliminated, but upper bound = -3.9e-07 < 0
Setting $presolve_eps >= 3.6e-08 might help.

it means that AMPL's presolve phase is simplifying three of the constraints to invalid inequalities: 3e-08 <= 0, 4e-08 <= 0, and -3.9e-07 >= 0. This proves that there is no feasible solution to within the tolerances used by presolve. However presolve is also telling you that if you increase the value of the presolve_eps tolerance then it will ignore these slight infeasibilities and it might accept the reduced problem and pass it to the solver. The presolve_eps option is an AMPL option, not a CPLEX option, so to increase its value to, for example, 8.0e-07, you would say:

option presolve_eps 8.0e-07;

Alternatively you could try setting

option presolve 0;

which turns off AMPL's presolve entirely and leaves it to the solve to do any presolving. You are also getting the error message

Error at _cmdno 27 executing "let" command
(file ../slr.run, line 76, offset 2145):
can't compute 99.6373/0

because in the statement "let step := scale * (UB - Lagrangian) / norm;" the value of norm is zero.

Bob Fourer
am...@googlegroups.com

=======

[Robert Fourer]

I will mail a copy directly, since the publisher has not publicly released it.

Bob Fourer
am...@googlegroups.com

=======

From: am...@googlegroups.com [mailto:am...@googlegroups.com] On Behalf Of Olawale Adeleke
Sent: Saturday, February 27, 2016 2:48 AM
To: am...@googlegroups.com
Subject: Re: [AMPL 11465] Lagrangian Relaxation

[Olawale Adeleke]

Thanks Bob. I do appreciate all your kind assistance.