Slow Pitch Network Problems?
L.C.
layer of supply nodes, one layer of receiving nodes,
and no intermediate nodes. The nodes, node
capacities, and arcs are determined. The arc
capacities are essentially unlimited except, of course,
by the nodes. There are also two (traditional)
artificial nodes to balance supply and demand. These
corresponding to oversell and slack. Slack is a supply
node that may serve oversell at very low cost, and
every other node at very high cost. Oversell is a
receiving node that can receive from all non-slack
supply nodes at very high cost.
***
The problem is simply to minimize the amount
of inventory delivered to oversell, and to smear the
inventory from each warehouse to a lot of stores, and
to get integral distributions.
***
All this, we discover, can be accomplished (at least
statistically) by assigning random per-unit costs to
the arcs between connected nonslack/nonoversell
nodes and solving the problem as a minimum cost
network flow problem. (I should mention that real
receiving nodes have been subdivided into much
smaller units, which are natural in the context of the
problem. This subdivision ensures that entire stores
are not served by a single warehouse. I should also
mention that we know we can distribute rigorously
through integer quadratic programming, but there are
obvious practical problems with that solution.)
The worst problem size is about:
5,000 supply nodes
5,000 receiving nodes
450,000 arcs
(Most of our problems are 1/10 that big, but there is
one class of problems like that.)
There is a certain amount of irony in this situation.
We are seeking, after all, an optimal solution to a
randomly-generated problem. **All we really want to
do is minimize assignment to oversell and smear stuff
around.** Some of these problems, even the big ones,
run very quickly on our licensed relaxation solver.
Others require 5-10 minutes. Much depends on what
costs we happen to pull out of the hat.
Given that we have latitude in cost assignment, I was
wondering if anyone had any suggestions about how
to assign costs so that the problems will be easier to
solve. For example:
1) Fewer different costs make optimization easier.
Was wondering if randomization of the receiving
node order could substitute for random costs, or
if we would get subtle biases - say, favoring of
one supply node over another when the two
compete. This might make oversell rich in
material from certain supply nodes, and that
result would be unacceptable.
2) I *think* it might help to arrange the costs so
that the cost difference between any two arcs is
integral and unique. The size of the costs in this
scheme can become large, though.
We just learned how to produce these numbers, so
naturally management wants quajillions of them
instantly and in real time ? I gotta play ball, so it
might as well be slow pitch! I'd appreciate any help
anyone might offer.
Thanks and Regards,
-Larry Curcio
Lutz Tautenhahn
it seems to me, the only reason, why you have to
do the optimization is because of the oversell.
So the easiest way would be to remove the
2 artificial nodes from your model. Then you have
to use corrected supply values, so that supply s
and demand d is balanced:
s_new = s * (1 - (sum s - sum d) / sum s)
After that you wouldn't have to find the optimum,
it would be sufficient, to find any feasible solution.
> We just learned how to produce these numbers, so
If you further want to use your random numbers, then
you could apply a greedy heuristic in order to get
similar distributions to that of the original optimization.
Regards,
Lutz Tautenhahn.
Lutz Tautenhahn
I made a mistake
> s_new = s * (1 - (sum s - sum d) / sum s)
works only, if there is an arc from every supply node
to every receiving node (otherwise the transformed
problem could be infeasible). But this seems not to be the
case as you write
>> 5,000 supply nodes
>> 5,000 receiving nodes
>> 450,000 arcs
> If you further want to use your random numbers, then
> you could apply a greedy heuristic in order to get
> similar distributions to that of the original optimization.
Also the greedy heuristic will not work in this case.
Sorry, I've overseen this.
Lutz.
Mike Hennebry
L.C. <lcu...@bellatlantic.net> wrote:
>The problem is simply to minimize the amount
>of inventory delivered to oversell, and to smear the
>inventory from each warehouse to a lot of stores, and
>to get integral distributions.
Can the smear criterion be violated by a large delivery
from one warehouse to one store? If so, it might be
useful to put capacities on arcs. Note that network
problems allow parallel arcs. There may be more than
one arc with the same tail and head. This can be useful
if the cheap one has a finite capacity.
Probably a lot of the smear criteria, expressed as linear
constraints, would destroy the total integrality property.
You could solve a continous LP and use reduced costs to
Langrangeanize the smear criteria for the transportation
problem. You could reduce the deviation from the continous
optimum by putting lower bounds on the flows.
--
Mike henn...@web.cs.ndsu.NoDak.edu
"No, no: the purpose of language
is to cast spells on other people ..."
Lisa S Chabot
L.C.
Mike Hennebry wrote:
> In article <3B6BF3E3...@bellatlantic.net>,
>
> Can the smear criterion be violated by a large delivery
> from one warehouse to one store? If so, it might be
> useful to put capacities on arcs.
Nope. The smear is everything.
> Note that network
> problems allow parallel arcs. There may be more than
> one arc with the same tail and head. This can be useful
> if the cheap one has a finite capacity.
>
Alas. Our solver doesn't allow this explicitly. We do
occasionally fake it, though.
>
> Probably a lot of the smear criteria, expressed as linear
> constraints, would destroy the total integrality property.
>
Yup. We had modeled this as a minimization of chisquare
under minimum slack. That would optimize the distribution,
but it's an integer quadratic programming application (Ooch!).
> You could solve a continous LP and use reduced costs to
> Langrangeanize the smear criteria for the transportation
> problem.
??? Will have to grok this a bit more.
> You could reduce the deviation from the continous
> optimum by putting lower bounds on the flows.
Interesting thought.
Thanks very much for responding.
-Larry Curcio
Mike Hennebry
L.C. <lcu...@bellatlantic.net> wrote:
:Mike Hennebry wrote:
:> Probably a lot of the smear criteria, expressed as linear
:> constraints, would destroy the total integrality property.
:>
:
:Yup. We had modeled this as a minimization of chisquare
:under minimum slack. That would optimize the distribution,
:but it's an integer quadratic programming application (Ooch!).
:
:> You could solve a continous LP and use reduced costs to
:> Langrangeanize the smear criteria for the transportation
:> problem.
:
:??? Will have to grok this a bit more.
:
:> You could reduce the deviation from the continous
:> optimum by putting lower bounds on the flows.
If you can get a continuous solution, you can get an
integer solution very near it. Take the floors of flows
in the continous solution. Use them as lower bounds in
the transportation problem. The problem is guaranteed
to be feasible.
The idea behind Langrangeanization is to remove a complicating
constraint and try to enforce it with a penalty in the objective
function. Getting integers out of a transportaion problem
pretty much requires a linear objective. In that light,
try this:
minimize obj(x)
subject to:
x in T
x >= 0
where T is the set defined by the transportation problem equalities
and obj is any concave objective function.
Once one has an optimimum x,
minimize (1-2frac(x))y
subject to:
y in T
ceil(x) >= y >= floor(x)
A basic optimum is a feasible solution that is close to x.
Since x solves it, it is guaranteed to be feasible.
The objective function works because each element of y is
allowed at most two possible values.
Y is not guaranteed to be an integer feasible solution as
close as possible to x. Y has more stringent bounds than x.
A similar method would work. The direct approach would
involve a lot of parallel arcs with unit capacities. Probably
most of them could be lumped if it was done carefully.
Defining carefully is left as an exercise to the reader.
BTW please do not grok. I would not like to end up like the
planet between Mars and Jupiter.
L.C.
Mike Hennebry wrote:
>The idea behind Langrangeanization is to remove a complicating
>constraint and try to enforce it with a penalty in the objective
>function.
OK. A penalty as in a Lagrange multiplier... equivalent to LP
etc. I see. Breakfast hadn't quite kicked in yet. Thanks and
sorry for the confusion.
Just a remark for no particular reason.... In school, they never
taught us just how big solvable LP problems can be. I had no
idea, for example, that the number of constraints could be on
the order of 10^5. Nor did I have any idea that a production
computer program might be asked to solve tens of thousands
of these (I'm referring to a simpler problem, BTW) in a few
minutes. When LP works, it's miraculous.
Regards,
-Larry Curcio