Would you treat this as a binary LP problem?
ralph mellor
Any comments are appreciated. If this is the wrong group
to post to, or I am posting the wrong level of detail, please
let me know.
-----------
To get an overview, ignore the indented material.
------------
A tree with up to 100,000 leaves.
(The tree is actually the electrical distribution in a building).
The tree has up to 10 branches from trunk to leaf.
(Branching occurs at distribution panels. Leaves are mostly
things like lights, motors, etc., but a panel can be a leaf as
far as the problem I have to solve is concerned.)
0 - 10 candidate widgets associated with each tree node.
(These widgets plug in to a panel or motor or other node to
reduce the monthly electricity costs assiociated with that node
(and downstream if it's a panel).)
(If necessary, for a first release of the software, I can simplify
the candidacy to zero or one candidate widget associated with
each node. My current solution assumes this simplification.)
Each candidate widget has various attributes, most importantly
a manufacturing cost, a selling price, and a savings per month.
I need to select the best subset of the candidate widgets according to
two overall sets of constraints, and an objective function, as follows:
Path constraints.
I can pick at most one widget per trunk-leaf path.
(This is what lead me to a binary linear inequality formulation.)
I represent this constraint with equations of the form:
a + b + c ... <= 1;
where a, b, c ... are zero or one and each represents
whether or not the candidate widget associated with
node a, b, c ... is selected in the solution.
Dollar constraints.
The sum of the costs of the selected widgets must be no
more than P times the sum of the savings per month for the
selected widgets. (P is thus the project payback period in
months.)
I represent this constraint with 3 equations:
a*Costa + b*Costb + c*Costc ... = CostSum;
a*Savea + b*Saveb + c*Savec ... = SaveSum;
P*SaveSum <= CostSum;
Objective function.
A weighted combination of the sum of profit (selling price minus
manufacturing cost) and the sum of savings per month.
(Actually, I expect the objective function to be configurable,
but the one I gave here seems a good start.)
(Again, if necessary, for a first release, I can simplify the objective
function to be just a single variable, be it profit or savings per
month.)
---------------
That's it. Thanks for reading this far.
Am I really nuts to be thinking of this as an LP problem?
If I do stick with an LP way of thinking about this, do you
have any suggestions for how to find a solution that will
cope with the size of problem I have? (lp_solve did great
on my PC up to 10,000 constraints, but pushing it much
further resulted in reboots.)
A few of the things I have thought of:
1. Reduce all the path constraints to two variables.
Without fiddling, I have something like:
a + b + c + d + e <= 1;
a + b + c + d + f <= 1;
...
where a, b, c, and d are non-leaves (panels).
I could replace this with:
a + b = Z;
Z + c = Y;
Y + d = X;
X + f <= 1;
...
However, this seems rather like I'm doing the work
the solver would do anyway.
2. Use some "presolve" technique(s).
I have read that these exist. I would guess they would
be potentially highly relevant to my problem.
3. Custom code the lp solution algorithm rather than
relying on a "black box" solver like lp_solve.
Erling D.Andersen
lp_solver is likely to be outperformed by other commercial solvers as well
as some public domain solvers.
You can try MOSEK (my company makes it) at
or one of the NEOS solvers at
Erling
"ralph mellor" <ralph...@KNOWSPAMself-reference.com> wrote in message
news:edFR6.98001$I5.22...@news1.rdc1.tn.home.com...
Posted Via Usenet.com Premium Usenet Newsgroup Services
----------------------------------------------------------
** SPEED ** RETENTION ** COMPLETION ** ANONYMITY **
----------------------------------------------------------
http://www.usenet.com
Paul A. Rubin
In the spirit of the problem, I've edited the original post to reduce
the number of electrons required to send it.
ralph mellor wrote:
>
> Hi, I'm an optimization newbie.
>
> Any comments are appreciated. If this is the wrong group
> to post to, or I am posting the wrong level of detail, please
> let me know.
This is a right group, if not the right group.
[snip]
> (These widgets plug in to a panel or motor or other node to
> reduce the monthly electricity costs assiociated with that node
> (and downstream if it's a panel).)
[snip]
> Each candidate widget has various attributes, most importantly
> a manufacturing cost, a selling price, and a savings per month.
Your formulation that follows looks appropriate to me *if* the savings
per month for a widget is independent of the rest of the solution. That
strikes me as a bit iffy, at least for widgets attached to a panel
(where you say the savings extend downstream). As long as the savings
generated by a widget at location A does not depend on how much power is
still flowing there (or how much the flow there has been reduced by
other widgets), you're ok.
[snip]
> Dollar constraints.
>
> The sum of the costs of the selected widgets must be no
> more than P times the sum of the savings per month for the
> selected widgets. (P is thus the project payback period in
> months.)
>
> I represent this constraint with 3 equations:
> a*Costa + b*Costb + c*Costc ... = CostSum;
> a*Savea + b*Saveb + c*Savec ... = SaveSum;
> P*SaveSum <= CostSum;
Your inequality is backwards, but otherwise this is the right idea.
[snip]
> Objective function.
> A weighted combination of the sum of profit (selling price minus
> manufacturing cost) and the sum of savings per month.
Seems a bit odd to me -- your mixing profit (benefit to the seller) with
savings (benefit to the buyer). Oh, well, your call on that.
[snip]
>
> Am I really nuts to be thinking of this as an LP problem?
Technically, it should be an integer linear program (ILP, or IP).
[Disclaimer on what comes next: It's closing in on 6:00 pm on a Friday,
and my brain is notorious for refusing to work overtime. Read on at
your own risk.] However, I'm pretty sure that if you solve the LP
relaxation, you'll get at most two fractional values among all the
variables. That fraction (if present) will be induced by the payback
constraint, and frankly if you just round one fraction up to 1 and the
other down to 0, the violation of the payback constraint will probably
be so puny that I'm guessing nobody will care.
>
> If I do stick with an LP way of thinking about this, do you
> have any suggestions for how to find a solution that will
> cope with the size of problem I have? (lp_solve did great
> on my PC up to 10,000 constraints, but pushing it much
> further resulted in reboots.)
As someone suggested elsewhere, a commercial solver should be able to
handle an LP of this size. (If it has to be solved as an integer
program, I'd hesitate to make predictions about how large you could go
and stand the solution time. You've got a pretty nice structure -- a
lot of specially ordered set constraints and the one payback constraint
-- but IPs are funny beasts, some of the ugly ones solve quickly and
some of the pretty ones are deceptively stubborn.)
If you want to do some programming, you could try Lagrangean
relaxation. In broad stroke terms, you pick a nonnegative initial guess
for a multiplier (lambda) for the payback constraint, then (assuming
your original objective was to maximize), subtract lambda*(cost
expression - P*savings expression) from your objective. Assuming I
wrote that correctly (it's still late on Friday), this has the effect of
rewarding you if your cost comes in below the payback limit and
penalizing you if your cost exceeds the payback limit. The problem now
separates into 10,000 independent pick-a-widget problems, which can be
solved by inspection (pick the widget whose modified objective
coefficient is most positive; don't pick any if they all have
nonpositive coefficients). Now you take that solution, plug it into the
payback constraint and see how you did. If you overachieved (cost less
than limit), you use the slack to reduce the multiplier value (but not
below 0); if you violated the payback limit, you use the (negative)
slack to increase the multiplier value. Recompute the objective
coefficients and do it all again. There are various references giving
details on how to do the multiplier adjustment. If the stars are in
alignment, you might actually converge to the optimal solution. If not,
you quit after a while and decide if the best solution you've
encountered so far is good enough to slide past the boss.
Hope this helps.
-- Paul
***************************************************************************
Paul A. Rubin Phone: (517)
432-3509
Department of Management Fax: (517)
432-1111
The Eli Broad Graduate School of Management E-mail: ru...@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
ralph mellor
> [*if* savings independent of rest of solution, formulation ok]
They are (or rather, the client insists they are), provided
the path constraint is adhered to.
> > Am I really nuts to be thinking of this as an LP problem?
>
> Technically, it should be an integer linear program (ILP, or IP).
I understand the LP/IP distinction to be pretty critical,
at least in terms of solvability in a reasonable timeframe.
I take it you agree with the subject line -- you do not
suggest that I forget this sort of approach and instead
use, say, simulated annealing.*
Is this because you think, if LP/IP works, why bother
looking at alternatives, or because you think LP/IP is
clearly the right way to solve the problem, or for
some other reason?
(*I have gravitated toward simulated annealing as a fallback
if LP, er IP, doesn't work out. Not that my understanding
of simulated annealing, or its fit with my problem, is any
better than my understanding of any other optimization
approach. It's just that my instincts suggested it was
the next best bet.)
> I'm pretty sure that if you solve the LP relaxation,
> you'll get at most two fractional values among all the
> variables. That fraction (if present) will be induced
> by the payback constraint, and frankly if you just
> round one fraction up to 1 and the other down to 0,
> the violation of the payback constraint will probably
> be so puny that I'm guessing nobody will care.
Er, "solve the LP relaxation"? Does this mean "solve
an LP that is almost an IP but for a few non-integers"?
Would I solve it using an LP or an IP? If an LP, why
is the fact that it's a relaxation relevant? If I solve it
using an IP, how would I get the rounding to happen?
Would it just happen? Are you saying I should solve
it in two stages, first somehow presolve to eliminate
the non-integer aspects, then solve the remaining
problem with an IP?
> the violation of the payback constraint will probably
> be so puny that I'm guessing nobody will care.
Certainly a minor error here and there does not matter.
Indeed, this is partly why using LP/IP may be just the
wrong way to do this. I don't really need absolute
optimality.
> As someone suggested elsewhere, a commercial solver
> should be able to handle an LP of this size.
I've been quite surprised to find that there's nothing
available for a few hundred dollars. You either use
a free solver, or spend $3-5k and on up.
> (If it has to be solved as an integer program,
Presumably, if I use my current formulation, then it will
indeed have to be solved as an IP, right?
> If you want to do some programming, you could try Lagrangean
> relaxation. In broad stroke terms, you pick a nonnegative initial guess
> for a multiplier (lambda) for the payback constraint, then (assuming
> your original objective was to maximize), subtract lambda*(cost
> expression - P*savings expression) from your objective. Assuming I
> wrote that correctly (it's still late on Friday), this has the effect of
> rewarding you if your cost comes in below the payback limit and
> penalizing you if your cost exceeds the payback limit. The problem now
> separates into 10,000 independent pick-a-widget problems, which can be
> solved by inspection (pick the widget whose modified objective
> coefficient is most positive; don't pick any if they all have
> nonpositive coefficients). Now you take that solution, plug it into the
> payback constraint and see how you did. If you overachieved (cost less
> than limit), you use the slack to reduce the multiplier value (but not
> below 0); if you violated the payback limit, you use the (negative)
> slack to increase the multiplier value. Recompute the objective
> coefficients and do it all again. There are various references giving
> details on how to do the multiplier adjustment. If the stars are in
> alignment, you might actually converge to the optimal solution. If not,
> you quit after a while and decide if the best solution you've
> encountered so far is good enough to slide past the boss.
Wonderful!
ralph mellor
> [*if* savings independent of rest of solution, formulation ok]
They are (or rather, the client insists they are), provided
the path constraint is adhered to.
> > Am I really nuts to be thinking of this as an LP problem?
>
> Technically, it should be an integer linear program (ILP, or IP).
I understand the LP/IP distinction to be pretty critical,
at least in terms of solvability in a reasonable timeframe.
I take it you agree with the subject line -- you do not
suggest that I forget this sort of approach and instead
use, say, simulated annealing.*
Is this because you think, if LP/IP works, why bother
looking at alternatives, or because you think LP/IP is
clearly the right way to solve the problem, or for
some other reason?
(*I have gravitated toward simulated annealing as a fallback
if LP, er IP, doesn't work out. Not that my understanding
of simulated annealing, or its fit with my problem, is any
better than my understanding of any other optimization
approach. It's just that my instincts suggested it was
the next best bet.)
> I'm pretty sure that if you solve the LP relaxation,
> you'll get at most two fractional values among all the
> variables. That fraction (if present) will be induced
> by the payback constraint, and frankly if you just
> round one fraction up to 1 and the other down to 0,
> the violation of the payback constraint will probably
> be so puny that I'm guessing nobody will care.
Er, "solve the LP relaxation"? Does this mean "solve
an LP that is almost an IP but for a few non-integers"?
Would I solve it using an LP or an IP? If an LP, why
is the fact that it's a relaxation relevant? If I solve it
using an IP, how would I get the rounding to happen?
Would it just happen? Are you saying I should solve
it in two stages, first somehow presolve to eliminate
the non-integer aspects, then solve the remaining
problem with an IP?
> the violation of the payback constraint will probably
> be so puny that I'm guessing nobody will care.
Certainly a minor error here and there does not matter.
Indeed, this is partly why using LP/IP may be just the
wrong way to do this. I don't really need absolute
optimality.
> As someone suggested elsewhere, a commercial solver
> should be able to handle an LP of this size.
I've been quite surprised to find that there's nothing
available for a few hundred dollars. You either use
a free solver, or spend $3-5k and on up.
> (If it has to be solved as an integer program,
Presumably, if I use my current formulation, then it will
indeed have to be solved as an IP, right?
> If you want to do some programming, you could try Lagrangean
> relaxation. In broad stroke terms, you pick a nonnegative initial guess
> for a multiplier (lambda) for the payback constraint, then (assuming
> your original objective was to maximize), subtract lambda*(cost
> expression - P*savings expression) from your objective. Assuming I
> wrote that correctly (it's still late on Friday), this has the effect of
> rewarding you if your cost comes in below the payback limit and
> penalizing you if your cost exceeds the payback limit. The problem now
> separates into 10,000 independent pick-a-widget problems, which can be
> solved by inspection (pick the widget whose modified objective
> coefficient is most positive; don't pick any if they all have
> nonpositive coefficients). Now you take that solution, plug it into the
> payback constraint and see how you did. If you overachieved (cost less
> than limit), you use the slack to reduce the multiplier value (but not
> below 0); if you violated the payback limit, you use the (negative)
> slack to increase the multiplier value. Recompute the objective
> coefficients and do it all again. There are various references giving
> details on how to do the multiplier adjustment. If the stars are in
> alignment, you might actually converge to the optimal solution. If not,
> you quit after a while and decide if the best solution you've
> encountered so far is good enough to slide past the boss.
I'm certainly open to coding up an algorithm myself,
indeed it looks like the way I need to go for several
reasons.
I'll look into this lagrangean stuff and the above recipe
this weekend and see what I come up with.
Again, thanks.
--ralph
ralph mellor
> [*if* savings independent of rest of solution, formulation ok]
They are (or rather, the client insists they are), provided
the path constraint is adhered to.
> > Am I really nuts to be thinking of this as an LP problem?
>
> Technically, it should be an integer linear program (ILP, or IP).
I understand the LP/IP distinction to be pretty critical,
at least in terms of solvability in a reasonable timeframe.
I take it you agree with the subject line -- you do not
suggest that I forget this sort of approach and instead
use, say, simulated annealing.*
Is this because you think, if LP/IP works, why bother
looking at alternatives, or because you think LP/IP is
clearly the right way to solve the problem, or for
some other reason?
(*I have gravitated toward simulated annealing as a fallback
if LP, er IP, doesn't work out. Not that my understanding
of simulated annealing, or its fit with my problem, is any
better than my understanding of any other optimization
approach. It's just that my instincts suggested it was
the next best bet.)
> I'm pretty sure that if you solve the LP relaxation,
> you'll get at most two fractional values among all the
> variables. That fraction (if present) will be induced
> by the payback constraint, and frankly if you just
> round one fraction up to 1 and the other down to 0,
> the violation of the payback constraint will probably
> be so puny that I'm guessing nobody will care.
Er, "solve the LP relaxation"? Does this mean "solve
an LP that is almost an IP but for a few non-integers"?
Would I solve it using an LP or an IP? If an LP, why
is the fact that it's a relaxation relevant? If I solve it
using an IP, how would I get the rounding to happen?
Would it just happen? Are you saying I should solve
it in two stages, first somehow presolve to eliminate
the non-integer aspects, then solve the remaining
problem with an IP?
> the violation of the payback constraint will probably
> be so puny that I'm guessing nobody will care.
Certainly a minor error here and there does not matter.
Indeed, this is partly why using LP/IP may be just the
wrong way to do this. I don't really need absolute
optimality.
> As someone suggested elsewhere, a commercial solver
> should be able to handle an LP of this size.
I've been quite surprised to find that there's nothing
available for a few hundred dollars. You either use
a free solver, or spend $3-5k and on up.
> (If it has to be solved as an integer program,
Presumably, if I use my current formulation, then it will
indeed have to be solved as an IP, right?
> If you want to do some programming, you could try Lagrangean
> relaxation. In broad stroke terms, you pick a nonnegative initial guess
> for a multiplier (lambda) for the payback constraint, then (assuming
> your original objective was to maximize), subtract lambda*(cost
> expression - P*savings expression) from your objective. Assuming I
> wrote that correctly (it's still late on Friday), this has the effect of
> rewarding you if your cost comes in below the payback limit and
> penalizing you if your cost exceeds the payback limit. The problem now
> separates into 10,000 independent pick-a-widget problems, which can be
> solved by inspection (pick the widget whose modified objective
> coefficient is most positive; don't pick any if they all have
> nonpositive coefficients). Now you take that solution, plug it into the
> payback constraint and see how you did. If you overachieved (cost less
> than limit), you use the slack to reduce the multiplier value (but not
> below 0); if you violated the payback limit, you use the (negative)
> slack to increase the multiplier value. Recompute the objective
> coefficients and do it all again. There are various references giving
> details on how to do the multiplier adjustment. If the stars are in
> alignment, you might actually converge to the optimal solution. If not,
> you quit after a while and decide if the best solution you've
> encountered so far is good enough to slide past the boss.
I'm certainly open to coding up an algorithm myself,
ralph mellor
> [*if* savings independent of rest of solution, formulation ok]
They are (or rather, the client insists they are), provided
the path constraint is adhered to.
> > Am I really nuts to be thinking of this as an LP problem?
>
> Technically, it should be an integer linear program (ILP, or IP).
I understand the LP/IP distinction to be pretty critical,
at least in terms of solvability in a reasonable timeframe.
I take it you agree with the subject line -- you do not
suggest that I forget this sort of approach and instead
use, say, simulated annealing.*
Is this because you think, if LP/IP works, why bother
looking at alternatives, or because you think LP/IP is
clearly the right way to solve the problem, or for
some other reason?
(*I have gravitated toward simulated annealing as a fallback
if LP, er IP, doesn't work out. Not that my understanding
of simulated annealing, or its fit with my problem, is any
better than my understanding of any other optimization
approach. It's just that my instincts suggested it was
the next best bet.)
> I'm pretty sure that if you solve the LP relaxation,
> you'll get at most two fractional values among all the
> variables. That fraction (if present) will be induced
> by the payback constraint, and frankly if you just
> round one fraction up to 1 and the other down to 0,
> the violation of the payback constraint will probably
> be so puny that I'm guessing nobody will care.
Er, "solve the LP relaxation"? Does this mean "solve
an LP that is almost an IP but for a few non-integers"?
Would I solve it using an LP or an IP? If an LP, why
is the fact that it's a relaxation relevant? If I solve it
using an IP, how would I get the rounding to happen?
Would it just happen? Are you saying I should solve
it in two stages, first somehow presolve to eliminate
the non-integer aspects, then solve the remaining
problem with an IP?
> the violation of the payback constraint will probably
> be so puny that I'm guessing nobody will care.
Certainly a minor error here and there does not matter.
Indeed, this is partly why using LP/IP may be just the
wrong way to do this. I don't really need absolute
optimality.
> As someone suggested elsewhere, a commercial solver
> should be able to handle an LP of this size.
I've been quite surprised to find that there's nothing
available for a few hundred dollars. You either use
a free solver, or spend $3-5k and on up.
> (If it has to be solved as an integer program,
Presumably, if I use my current formulation, then it will
indeed have to be solved as an IP, right?
> If you want to do some programming, you could try Lagrangean
> relaxation. In broad stroke terms, you pick a nonnegative initial guess
> for a multiplier (lambda) for the payback constraint, then (assuming
> your original objective was to maximize), subtract lambda*(cost
> expression - P*savings expression) from your objective. Assuming I
> wrote that correctly (it's still late on Friday), this has the effect of
> rewarding you if your cost comes in below the payback limit and
> penalizing you if your cost exceeds the payback limit. The problem now
> separates into 10,000 independent pick-a-widget problems, which can be
> solved by inspection (pick the widget whose modified objective
> coefficient is most positive; don't pick any if they all have
> nonpositive coefficients). Now you take that solution, plug it into the
> payback constraint and see how you did. If you overachieved (cost less
> than limit), you use the slack to reduce the multiplier value (but not
> below 0); if you violated the payback limit, you use the (negative)
> slack to increase the multiplier value. Recompute the objective
> coefficients and do it all again. There are various references giving
> details on how to do the multiplier adjustment. If the stars are in
> alignment, you might actually converge to the optimal solution. If not,
> you quit after a while and decide if the best solution you've
> encountered so far is good enough to slide past the boss.
I'm certainly open to coding up an algorithm myself,
Lutz Tautenhahn
if you would accept an objective function
f(P*SaveSum-CostSum)=>Max
whith any monotonically increasing function f.
Then you could get the optimum with the following approach:
Use the node object with the following attributes and methods
(you should be familiar with object oriented programming):
attributes:
-children (list of pointers to node)
-WidgetMax (number)
-WidgetCost (array [0..WidgetMax-1] of numbers)
-WidgetSaving (array [0..WidgetMax-1] of numbers)
-WidgetIndex (number)
-Totals (number)
methods:
DeleteWidgets()
{ if (WidgetIndex<0)
{ for (all n in children)
n.DeleteWidgets();
}
else WidgetIndex=-1;
Totals=0;
}
Optimize(aP)
{ Totals=0;
for (all n in children)
Totals+=n.Optimize(aP);
WidgetIndex=-1;
for (i=0; i<WidgetMax; i++)
{ if (Totals<aP*WidgetSave[i]-WidgetCost[i])
{ if (WidgetIndex<0)
{ for (all n in children)
n.DeleteWidgets();
}
WidgetIndex=i;
Totals=aP*WidgetSave[i]-WidgetCost[i];
}
}
return(Totals);
}
Initialize the nodes, so that the nodes are properly connected by child
pointers. Initialize the WidgetCost and WidgetSaving array by the Widgets
which could be associated with the node. Set WidgetIndex=-1 for every node.
Now lets do the work, with the root node do:
OptimumValue=root.Optimize(P);
Regards, Lutz Tautenhahn
Paul A. Rubin
I'm not terribly diligent about checking the newsgroup, and since my
last posting the original message and my memory of it both expired, so
I'm running largely off what is written here (with more pruning -- I'm
hoping the electrons I conserve can be shipped to California, where
they're desperately needed).
ralph mellor wrote:
>
> > > Am I really nuts to be thinking of this as an LP problem?
> >
> > Technically, it should be an integer linear program (ILP, or IP).
>
> I understand the LP/IP distinction to be pretty critical,
> at least in terms of solvability in a reasonable timeframe.
Yes. IPs can take a while to solve (think "longer than remaining life
of Sol"), or they can go quickly, and in my experience size is not
necessarily a good predictor of solution time (although positively
correlated to some degree).
> I take it you agree with the subject line -- you do not
> suggest that I forget this sort of approach and instead
> use, say, simulated annealing.*
Correct. I would go with the IP model if (a) optimality is key, (b) the
payback constraint is rigid and (c) you can solve it in a reasonable
amount of time, the last being a purely empirical question. If either
not (a) or not (b), meaning that you can fudge the payback a bit, I'd
solve the LP relaxation and round.
> Is this because you think, if LP/IP works, why bother
> looking at alternatives, or because you think LP/IP is
> clearly the right way to solve the problem, or for
> some other reason?
Well, honesty compels me to start with the fact that I'm more familiar
with LP and IP than with simulated annealing (no personal experience),
genetic algorithms (limited personal experience) or tabu search (no
personal experience). However, there are three other factors pushing me
toward LP/IP. The first is that the commercial LP/IP packages have
benefited from a lot of R&D, so they're pretty fast, and in particular
faster than anything I could kludge together. Directed random search
methods (SA, GA, tabu), on the other hand, would probably require me to
roll my own code. The second is the curse of dimensionality. As the
problem gets bigger, every method takes longer, but the simplex solution
time for an "average" LP grows polynomially with problem size (it's
exponential in the worst case but apparently not typically), whereas I
suspect that directed random search times are nonpolynomial in the
dimensions of the search space. The third reason is that with LP/IP,
you know when you're done (charitably assuming, in the case of IP, that
you are still alive when the algorithm terminates), whereas with
directed random search it's more a case of quitting when you haven't
seen progress for a while and hoping you've got a winner. (LP dual
solutions also give you a sense of the most you might be suboptimal if
you terminate early; in general, I don't think you can get such a sense
from directed search.)
> (*I have gravitated toward simulated annealing as a fallback
> if LP, er IP, doesn't work out. Not that my understanding
> of simulated annealing, or its fit with my problem, is any
> better than my understanding of any other optimization
> approach. It's just that my instincts suggested it was
> the next best bet.)
Personally, if IP (or the LP relaxation) didn't work, I'd try a
heuristic based on Lagrangean relaxation. Among the directed random
search methods, I might lean toward genetic algorithms, only because
they allow bunches of node decisions to change at once, whereas
simulated annealing and tabu search would probably be set up so that at
each step only one widget changed.
> > I'm pretty sure that if you solve the LP relaxation,
> > you'll get at most two fractional values among all the
> > variables. That fraction (if present) will be induced
> > by the payback constraint, and frankly if you just
> > round one fraction up to 1 and the other down to 0,
> > the violation of the payback constraint will probably
> > be so puny that I'm guessing nobody will care.
>
> Er, "solve the LP relaxation"? Does this mean "solve
> an LP that is almost an IP but for a few non-integers"?
It means that, rather than make each widget decision variable 0 or 1,
you let them ALL float between 0 and 1, so that the model becomes an
LP. If my conjecture above is right, in the LP solution all but at most
one or two of them will come out either 0 or 1. If they all turn up
integer without exception, you are guaranteed that the LP solution is
also the optimal IP solution and you're done. If you get some
fractional values, the LP objective value is a valid bound (lower bound
if you're minimizing, upper bound if you're maximizing -- I forget which
you were doing). In a kinder universe, you would get the optimal
solution by rounding the fractions, but in this universe about all you
can hope for from rounding is that (a) the objective value is close to
optimal and (b) you came close to satisfying the payback constraint.
> Would I solve it using an LP or an IP?
The LP relaxation would be solved as an LP.
> If an LP, why
> is the fact that it's a relaxation relevant?
By dropping the integrality constraints, we loosened up the problem
(expanded the set of "feasible" solutions to include fractions). So
unless you accidentally get an integer solution anyway (which can
happen, particularly if you sacrifice a small furry animal first) (oops,
I hope PETA doesn't monitor this group), you'll get a solution that is
"superoptimal" (too good to be true, because it violates integrality
somewhere).
>If I solve it
> using an IP, how would I get the rounding to happen?
No rounding needed -- the solution algorithm in this case only considers
integer values, which is at the heart of why it takes so much longer to
solve an IP than a comparable size LP.
> Would it just happen? Are you saying I should solve
> it in two stages, first somehow presolve to eliminate
> the non-integer aspects, then solve the remaining
> problem with an IP?
Not really. I'm saying that, before trying the IP, I would solve the
LP, round manually as needed, and see if I was happy with the result.
If you solve the IP, particularly if you use a commercial solver, you'll
almost surely use a method generically known as "branch and bound" or
"branch and cut". The first step will be to solve the LP relaxation. I
know that, unless you instruct it otherwise, CPLEX will then
automatically execute a heuristic that attempts to round the LP solution
different ways to get a good (and feasible) solution to the IP. I can't
speak for other commercial solvers, but I wouldn't be surprised if they
also contained rounding heuristics. The difference between your doing
this yourself and letting an IP solver do it is that the IP solver is
likely to consider the payback constraint sacrosanct and reject any
rounded solution that violates it. I think there's a way in CPLEX to
set a tolerance for violation of constraints, but I'm not sure if you
can do it for a single constraint. Again, I don't know about other
solvers.
> > the violation of the payback constraint will probably
> > be so puny that I'm guessing nobody will care.
>
> Certainly a minor error here and there does not matter.
In that case, I would definitely try solving the LP and rounding it.
First, my conjecture is that only one or two nonintegers will crop up
needing rounding. It's easy to round them to preserve the one widget
per node requirement, so the only place you're likely to encounter a
problem is in the payback constraint, which may be violated by the
rounding. My guess, based on the number of nodes/widgets and the
charitable assumption that none of the widgets is a giant among widgets
in terms of either cost or savings, is that the violation of the payback
constraint will be small enough to be swept under the managerial rug, as
it were.
> Indeed, this is partly why using LP/IP may be just the
> wrong way to do this. I don't really need absolute
> optimality.
As noted above, one virtue of LP/IP is that it gives you a sense of how
badly your solution might be suboptimal, assuming you don't go all the
way to optimality. I don't know how to get a bound like that from any
other technique.
>
> > As someone suggested elsewhere, a commercial solver
> > should be able to handle an LP of this size.
>
> I've been quite surprised to find that there's nothing
> available for a few hundred dollars. You either use
> a free solver, or spend $3-5k and on up.
I think the free solvers drove out the cheap solvers. You can still get
some solvers fairly cheaply, I think, by getting a "student version",
but the student versions generally have limited problem capacity, and
assuredly would not handle your problem. The Solver in Excel is pretty
good at LP and not too bad at IP problems, but again I don't think it
would handle one the size of yours.
> > (If it has to be solved as an integer program,
>
> Presumably, if I use my current formulation, then it will
> indeed have to be solved as an IP, right?
Sorry, I was unclear there. You have to end up with an integer solution
for it to make sense (i.e., you can't employ fractional widgets). What
I meant was, if you have to get the optimal, no messing with the payback
constraint, integer solution, as opposed to being able to get away with
rounding the LP solution.
As I was walking out to my car the day I posted that (whenever that
was), it occurred to me that I'd glossed over a couple of key pieces.
You take your current estimate for the multiplier and use it to create a
modified objective function that incorporates both the original
objective function and a penalty/reward for violation/overachievement of
the payback constraint. So each widget variable has a new objective
coefficient which is a function of that multiplier value. The problem,
as I noted before, now decomposes into a relatively trivial task of
picking the widget with the highest payoff (or no widget if they're all
dogs) at each node, payoff being defined in terms of the modified
objective coefficients. There are two catches. One is that you could
end up with a tie for best widget at a node. The other is that you
could have a node where the best widget has a modified objective
coefficient of zero, meaning you're ambivalent about using it or not
using it. (Of course, this is effectively a tie, between the best
widget and the "null" widget.) The first point I glossed over is that
how you break such a tie has a bearing on how the solution algorithm
performs, and you don't have anyway to know the "right" way to break the
tie. The second point I glossed over, which is related to the first
point, is that the Lagrangean relaxation approach is not guaranteed to
produce the optimal solution to the IP, and in fact will not even
produce the optimal solution to the LP.
What the relaxation approach will do is produce a succession of
solutions, some of which will violate the payback constraint (if you've
set the penalty multiplier too low) and others of which will be feasible
but possibly too conservative (if you've set the penalty multiplier too
high). The value of each successive solution in the modified objective
function is a bound (upper bound if you're maximizing) on the objective
value of the optimal solution. Along the way, whenever you get a
feasible solution (or one close enough for government work, as we say
here), compare it to the other feasible solutions and keep a record of
the best one found so far. When either (a) the difference between the
objective value of the best feasible solution and the bound on the
optimal value is small enough or (b) you get tired, quit and run with
the best feasible solution found so far.
My reading of the original problem was that other than requiring either
zero or one widget to be chosen at each node, the only constraint you
had was a single payback constraint, so that Lagrangean relaxation would
involve a single multiplier. If so, I think this method has some
serious promise. First off, it should be really easy to code -- plug in
multiplier estimate, compute new objective coefficient for each widget,
choose best widget at each node, adjust multiplier, iterate. Second,
with only one multiplier, the multiplier adjustment procedure should be
easy. There's some relatively fancy "subgradient optimization"
adjustment methods out there, but with only one multiplier, you can do
it by bisection search. Start with a multiplier value of zero, which
should result in a solution that violates the payback constraint (since
you're not penalizing violations). Now pick a decently large positive
multiplier value and try again. If you don't get a payback violation,
the "best" multiplier is between 0 and this value. (If you do get a
violation, you picked too low, so now this value rather than zero
becomes a lower limit for the multiplier, and you try an even larger
one.) Once you've got lower and upper limits for the multiplier (no
payback violation at the lower limit, unacceptable payback violation at
the upper limit), try the midpoint of that interval for the multiplier.
If the solution it produces violates the payback constraint, the
midpoint replaces the lower limit, else it replaces the upper limit.
Etc., ad nauseum.
If you want more detail or have other questions, you might want to email
me directly.
HTH,
Paul
ralph mellor
> a lot of R&D [so they are going to be] faster than
> anything I could kludge together.
Yeah, that's what I was thinking. It's one of the main
reasons I liked going this route as against others.
> [excellent explanation of LP relaxation, superoptimality,
> plus mention of CPLEX constraint violation tolerance, etc]
Thanks, although it took me hours to convince
my cats that you were joking about the sacrifice.
> [More on Lagrangean relaxation]
I didn't get to that this weekend and I'm now thinking
lp_solve will suffice for my client's short term needs. I
need to get a solution asap and can always revisit this
in the weeks following release of a version 1. So, I will
follow your guidelines when I get a chance, some time
in the next few weeks/months. I'll let you and the list
know when I get the opportunity to go for it and how
I do.
> My reading of the original problem was that other
> than requiring either zero or one widget to be
> chosen at each node, the only constraint you
> had was a single payback constraint,
Correct.
> If you want more detail or have other questions,
> you might want to email me directly.
I've decided to go ahead and assume use of lp_solve
for now. I'll try going the relaxed LP route and see how
that works out.
Again, thanks for your clear and comprehensive help.
ralph mellor
> if you would accept an objective function
> f(P*SaveSum-CostSum)=>Max
> whith any monotonically increasing function f.
I wish it were that simple!
I have considered having a backup algorithm for
cases that are too large to be solved. So, it looks
like I might end up using your algorithm. If I do,
I'd like to let you know, but my software doesn't
tell me your email address. (So I don't know if
you'll ever see this anyway.)
Either way, thanks for the algorithm.
> Regards, Lutz Tautenhahn
--ralph
Lutz Tautenhahn
let's continue discussing our problem:
Paul wrote:
>... I would definitely try solving the LP and rounding it.
>First, my conjecture is that only one or two nonintegers will crop up
>needing rounding.
This was my first idea, too. But then my inspiration warned me, that
this could be not correct. And indeed, as the following example shows, this
conjecture is wrong:
Let's start with 3 nodes, a root node n_0 and 2 child nodes n_00 and
n_01. Assume a widget at n_00 is very good for the objective function, but
would violate the constraint. A widget at node_01 holds the constraint,
but is poor in the objective function. Then the LP relaxation would yield,
lets say, x_00=0.5 and x_01=0.5. Assume there are 10 child nodes under
n_00 (n_000, ..., n_009), and 10 child nodes under n_01 (n_010, ..., n_019),
which do the same amount to the constraint, but are slightly better in the
objective function. Then the LP relaxation would yield x_00=x_01=0 and
x_000=...=x_009=x_010=...=x_009=0.5 (so you have already 20 nonintegers).
Assume that each of the child nodes has again 10 children, which do the same
to the constraint, but are slightly better in the objective function, so
you would have 200 nonintegers, and so on.
You wrote:
>0 - 10 candidate widgets associated with each tree node.
Even if you would obtain the optimum for a model with widget = 1 or 0
using IP, this would probably not be the optimum solution for your problem,
because you first preselect one of 10 possible widgets which could be
associated with a node. So if you really want the optimum, you must solve
the expanded modell without preselecting a widget for a node. It probably
will take some days/years to solve a problem instance of the size you
described with IP.
Paul gives us new hope:
> ... create a
> modified objective function that incorporates both the original
> objective function and a penalty/reward for violation/overachievement of
> the payback constraint
So I'd like to improve the method from my last post.
Give the node objects another attribute:
- Profit (number)
Change the method Optimize() into this:
Optimize(aP1, aP2, aAlpha)
{ Totals=0;
for (all n in children)
Totals+=n.Optimize(aP1, aP2, aAlpha);
WidgetIndex=-1;
for (i=0; i<WidgetMax; i++)
{ TempValue = (aP1*WidgetSave[i]-WidgetCost[i])*aAlpha+
(aP2*WidgetProfit[i]+(1-aP2)*WidgetSave[i])*(1-aAlpha);
if (Totals < TempValue)
{ if (WidgetIndex<0)
{ for (all n in children)
n.DeleteWidgets();
}
WidgetIndex=i;
Totals=TempValue;
}
}
return(Totals);
}
Add two more methods to the node object:
GetConstraintValue(aP1)
{ TempValue=0;
if (WidgetIndex<0)
{ for (all n in children)
TempValue+=n.GetConstraintValue(aP1);
}
else TempValue=aP1*WidgetSave[WidgetIndex]-WidgetCost[WidgetIndex];
return(TempValue);
}
GetObjectiveValue(aP2)
{ TempValue=0;
if (WidgetIndex<0)
{ for (all n in children)
TempValue+=n.GetObjectiveValue(aP2);
}
else
TempValue=aP2*WidgetProfit[WidgetIndex]+(1-aP2)*WidgetSave[WidgetIndex];
return(TempValue);
}
Now you can do a bisection method like this:
(There was a mistake in my last post: You don't need to initialize
WidgetIndex=-1. The method does it by itself.)
root.Optimize(P1,P2,0); //constraint is not considered
if (root.GetConstraintValue(P1)>=0) //the constraint holds anyway
return(Optimum_Is_Found_ID); //you are a lucky guy
UpperBound=root.GetObjectiveValue(P2);
root.Optimize(P1,P2,1); //objective function is not considered
LowerBound=root.GetObjectiveValue(P2);
best_feassible_alpha=1;
//there is always a feassible solution, whereby no widgets are selected
alpha=0.5;
d_alpha=0.5;
for (i=0; i<10; i++)
{ d_alpha/=2;
root.Optimize(P1, P2, alpha)
if (root.GetConstraintValue(aP1)>=0) //the solution is feassible
{ TempValue=root.GetObjectiveValue(aP2);
if (LowerBound<TempValue)
{ best_feassible_alpha=alpha;
LowerBound=TempValue;
}
alpha-=d_alpha;
}
else //the solution is not feassible
alpha+=d_alpha;
}
root.Optimize(P1, P2, best_feassible_alpha);
The P2 value does the weighting of Profit and Saving and must be within
[0..1]. The objective value found by this method is equal to LowerBound.
This can, but must not be the optimum for your problem. If there exists a
solution with an objective value greater than LowerBound, then it can not
be greater than UpperBound, but possibly there is exists no solution with
an objective value equal to UpperBound. You could use the bound values
also as input for a branch & bound method, if you want to go on with IP
to improve the solution.
Regards, Lutz.
lutz.ta...@wirtschaft.tu-chemnitz.de
www.tu-chemnitz.de/~luta/
Lutz Tautenhahn
I wrote:
> Let's start with 3 nodes, a root node n_0 and 2 child nodes n_00 and
> n_01. Assume a widget at n_00 is very good for the objective function, but
> would violate the constraint. A widget at node_01 holds the constraint,
> but is poor in the objective function. Then the LP relaxation would yield,
> lets say, x_00=0.5 and x_01=0.5. Assume there are 10 child nodes under
> n_00 (n_000, ..., n_009), and 10 child nodes under n_01 (n_010, ...,
n_019),
> which do the same amount to the constraint, but are slightly better in the
> objective function. Then the LP relaxation would yield x_00=x_01=0 and
This could only happen if you would use an interior point method to solve
the problem. With simplex you would get x_000=...=x_004=x_010=...=x_014=1
and x_005=...=x_009=x_015=...=x_019=0 instead (so you have no nonintegers).
So the conjecture of Paul A. Rubin
>... I would definitely try solving the LP and rounding it.
>First, my conjecture is that only one or two nonintegers will crop up
>needing rounding.
is probably right (supposed you use the simplex method to solve the LP).
Regards, Lutz Tautenhahn