Relaxing Constraints

[arun lila]

Thanks

In my  VRPTW problem at some location the time window constraints are not feasible, I want an answer which can relax the constraint only for those location which are time window infeasible, 

How can I do that , is there any process in cplex to just say relax wherever it is unfeasible. and at the location where we can have feasible solution should be feasible always.

Also it should try to violate the limit as minimum as it can. 

Thanks

Arun Lila

[Paul]

If you are using the CPLEX interactive optimizer, or one of the CPLEX programming APIs, you can use FeasOpt to find a minimal relaxation that is feasible. I don't think it can be invoked from AMPL, though.

Paul

[Robert Fourer]

It is a common question to determine "which constraints are infeasible" in some sense.  Seldom is one constraint infeasible in itself, however.  It could happen for example that there are solutions that are feasible for constraint A and not feasible for constraint B, and there are other solutions that are feasible for constraint B and not feasible for constraint A.  So you have to make a choice of which constraint to relax.

 

You can ask CPLEX to decide which constraints to relax, and how to relax them optimally, by using the feasopt and feasoptobj options described on page 33 of

 

   www.ampl.com/BOOKLETS/amplcplex122userguide.pdf

 

These don't provide any specific guidance as to CPLEX's choice of relaxed constraints, however.

 

Instead you may want to adjust your formulation to give your own guidance, by changing your time window constraints into "elastic" constraints.  This is done by adding a variable to each constraint that represents the amount of infeasibility in that constraint, and that has a large coefficient in the objective function.  Then the feasopt mechanism is not needed.  If a feasible solution is possible, CPLEX will find it; but if it is not possible, CPLEX will find a minimum-penalty solution violating some time-window constraint.  (Each large coefficient can be viewed as a penalty per unit of feasibility violation, or as a bound on the corresponding dual value.)

 

(Section 17.2 of the AMPL book describes a way to do the same thing using piecewise-linear terms.)

 

Bob Fourer

4...@ampl.com

 

From: am...@googlegroups.com [mailto:am...@googlegroups.com]

On Behalf Of arun lila
Sent: Friday, January 18, 2013 2:39 AM
To: am...@googlegroups.com
Subject: [AMPL 6481] Relaxing Constraints