|
|
 | | From: | AM | | Subject: | Total infeasibility | | Date: | 13 Jan 2005 09:51:49 -0800 |
|
|
 | I have an infeasible LP for which I can find a solution that minimizes
the sum of primal infeasibilities or the sum of dual infeasibilities.
I'm curious to look at a basic solution that minimizes the sum of both.
But as the implication/scale/units of the primal and dual variables
are different, I'm not sure if simply minimizing the collective sum
would be ok. I'm looking for a total infeasibility metric that scales
one or the other so that they are both measured on the same
scale/units. Any thoughts? Thanks.
|
|
| | From: | Paul A. Rubin | | Subject: | Re: Total infeasibility | | Date: | Thu, 13 Jan 2005 15:49:18 -0500 |
|
|
| AM wrote:
> I have an infeasible LP for which I can find a solution that minimizes
> the sum of primal infeasibilities or the sum of dual infeasibilities.
They're both infeasible? This can of course happen, but usually the
dual of an infeasible primal is unbounded, not infeasible.
> I'm curious to look at a basic solution that minimizes the sum of both.
> But as the implication/scale/units of the primal and dual variables
Do you mean constraints here? The amount of violation in any constraint
would be in the units of the constraint.
> are different, I'm not sure if simply minimizing the collective sum
> would be ok.
I'm not sure it would be meaningful. For that matter, does it even make
sense to minimize the sum the primal violations? Are all primal
constraints using the same units?
> I'm looking for a total infeasibility metric that scales
> one or the other so that they are both measured on the same
> scale/units. Any thoughts? Thanks.
If you were minimizing violations in the primal only, I would advocate
assessing a cost per unit for violating each constraint ("per unit" in
the context of that constraints units) and minimizing the total
violation cost. I don't think you can get a meaningful violation "cost"
for the dual, though.
The big question is why you would be doing this in the first place?
Perhaps your reason might shed some light on a plausible weighting.
-- Paul
******************************************************************************************
Paul A. Rubin Phone:
(517) 432-3509
Department of Management Fax: (517)
432-1111
The Eli Broad Graduate School of Management E-mail: rubin@msu.edu
Michigan State University
http://www.msu.edu/~rubin/
East Lansing, MI 48824-1122 (USA)
******************************************************************************************
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. J. W. v. GOETHE
|
|
| | From: | edadk | | Subject: | Re: Total infeasibility | | Date: | 13 Jan 2005 23:06:57 -0800 |
|
|
|
AM wrote:
> I have an infeasible LP for which I can find a solution that
minimizes
> the sum of primal infeasibilities or the sum of dual infeasibilities.
> I'm curious to look at a basic solution that minimizes the sum of
both.
> But as the implication/scale/units of the primal and dual variables
> are different, I'm not sure if simply minimizing the collective sum
> would be ok. I'm looking for a total infeasibility metric that
scales
> one or the other so that they are both measured on the same
> scale/units. Any thoughts? Thanks.
Minimizing the sum infeasibility may be interesting. However, looking
at a certificate of infeasibility might be even more interesting as I
show in
E. D. Andersen.
Certificates of primal and dual infeasibility in linear programming.
Computational Optimization and Applications, 20(2):171-183, 2001.
Note the certificate is scale independent.
Erling
|
|
|
