Originally posted by: SystemAdmin

Hi everybody,

I hope the following will not be considered off topic here.

Assume you have an infeasible lp which is solved by subgradient or any thing similar in lagrangian relaxation.
Again assume that the cause of infeasibility is a set of capacity constraints.

How does one make a connection between the LR multipliers and the dual rays (extreme or non-extreme) corresponding to this infeasibility and what is actually the best termination criteria for the subgradient under such conditions?

Any comment is highly appreciated.
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

Shouldn't each set of optimal Lagrange multipliers be identical to a dual ray?
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

This is indeed the case for the feasible problems that the dual multipliers are actually optimal dual solution
but could not find any proof in the literature proving that this also holds for the infeasible problem.

The same as you, my guess is that it is indeed but I cannot find any proof to it in literature.
There also possbility to addd variables and make the problem always feasible but it does not prove anything.
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

> Shahin G wrote:
> Assume you have an infeasible lp which is solved by subgradient or any thing similar in lagrangian relaxation.
> Again assume that the cause of infeasibility is a set of capacity constraints.

What specifically are you relaxing when you apply Lagrangian relaxation? If you relax all the constraints in the (infeasible) primal problem, you get an LP with no constraints that would likely be unbounded for all (?) multiplier values. Or are you assuming that all primal variables have finite bounds? Or relaxing a subset of constraints?

/Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

Hi Paul,

Thanks for your comment.
>>What specifically are you relaxing when you apply Lagrangian relaxation?
Actually this is also a question.

Of course all the variables are bounded -- let sat (0,1) in a particular case.

For the moment I would rather not let the subproblem becomes too easy; I would consider the capacity constraint and/or the flow conservation on the intermediate nodes to be relaxed and rest be kept (includes the source and sink and some side constraints)
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

Shahin,

I gave this some thought (that's why the response was slow -- I needed to find some free time) but did not get very far. I'm also not entirely sure I'm understanding your question. So I'll give my opinion on what might or might be the actual question. :-)

Suppose we start with a linear program containing two sets of constraints, which I'll designate C1 and C2, and suppose that the LP is infeasible. If we just solve it the usual way, we'll find a dual ray that identifies one subset of (C1 union C2) which is inconsistent. (There may of course be multiple inconsistent sets.)

Now suppose instead that we relax C2 into the objective, using some Lagrange multipliers. Assume that the original objective is minimization, and so we maximize the optimal value of the relaxed LP with respect to the multipliers. Three possibilities occur: (a) C1 is itself inconsistent; (b) C2 is internally inconsistent; or (c) C1 is consistent, C2 is consistent, but (C1 union C2) is inconsistent.

In the first case, the relaxed LP is infeasible (for any choice of multipliers), and we get a dual ray that identifies an inconsistent subset of C1. In the second and third cases, the relaxed LP is feasible (and, for simplicity, I'll assume the feasible region is bounded), so for any multiplier choice we get an optimal solution of the relaxed problem, but the outer (maximization) problem is unbounded. That is, we find a sequence of multipliers for which the optimal value of the relaxed LP tends toward infinity. Passing to a subsequence if necessary, we can assume that the optimal vertex of the relaxed LP is identical for all multipliers in the sequence, which means that the same subset C2' of C2 is being violated every time.

What I don't see is any distinction of the second and third cases here. We've identified a subset C2' which is either internally inconsistent or inconsistent with C1, but I don't know which. We can determine if C2' is internally inconsistent by optimizing the original objective function over C2', and we can determine a subset of C1 that is inconsistent with C2' by optimizing the original objective function over the union of C1 and C2'. I don't see any way, though, to pin that down using just the results of the relaxation.

/Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

Paul, Thanks for your valuable comments.
In fact, I also couldn't get anywhere more than this(if even up to this ;) ).
Even worst, I still have difficulties to computationally conclude if the problem (LP or MIP) is actually feasible or infeasible (assuming that we don't know if the problem is feasible or infeasible). Just think of subgradient as a black-box solver (user has no information of the problem).
I am still searching for a valid termination criteria which is valid when either the problem is feasible or infeasible (Assuming that we dont know any upper bound).
Also regarding the rays: if infeasibility is proven, how to get the rays. where this ray is actually obtained.

These are still bothering.
#DecisionOptimization
#MathematicalProgramming-General