[Coin-lpsolver] SOS in preprocessing

[John J Forrest]

Justin,

The answers to some of the questions can be found in the original paper - 
E. M. L. Beale and J. A. Tomlin, Special facilities in a general 
mathematical programming system for non-convex problems using ordered sets 
of variables, In J. Lawrence (Ed.), Proceedings of the Fifth International 
Conference on Operational Research 447-454, London: Tavistock Publications 
(1970). 9    So the weights are designed so that the code knows where to 
branch - so if an SOS1 set was to model facilities with sizes of 0, 
400,600 and 800 and if the variable for size 0 had value 0.6 and the 
variable for size 800 had value 0.4 then the LP is using a capacity of 320 
so the two branches should be 0 or at least 400.  So the weights are for 
that purpose.  In the original paper I think the weights were derived from 
the "reference" row in the model but now we allow the user to enter any 
weights to help direct the branching.

The preprocessing is a bit primitive and it was thought that advanced 
users would define their own sets and weights as in example.  So SOS are 
very much meant to be independent of preprocessing.

As for SOS2, I did not have a realistic example to hand, but I know that 
John Tomlin has used SOS2 successfully with COIN and he may be able to add 
some thoughts.

John Forrest



jtyates at buffalo.edu 
Sent by: coin-lpsolver-bounces at list.coin-or.org
03/23/2006 04:15 PM

To
coin-lpsolver at list.coin-or.org
cc

Subject
[Coin-lpsolver] SOS in preprocessing






I've spent some time recently looking into the presence and usage of SOS
as a form of preprocessing and branching within COIN.  The main files I
have found which contain SOS code are in CglPreProcess, CbcBranchActual
and in a sample code found under Cbc\Samples simply called SOS.cpp.

As of right now, I can see that Coin has the ability to find SOS and
branch on them.  What I still can't see is specifically how the
weighting of the SOS is accomplished and what the weights represent
(weightSOS_), whether the SOS branching in Cbc is based off of the
preprocess SOS found in the Cgl or whether these are two independent
steps, and whether there is much on SOS2 (from what I've seen it appears
that the focus is on SOS1 and the fixing and branching that comes from
it, and not so much on SOS2).

Any direction on where to find additional SOS code or materials within
any of the programs would be helpful.  Also, any answers to the above
questions on SOS would be sincerely appreciated.  I am specifically
interested in SOS as they relate to preprocessing.

Thank you,

Justin

__________________________________________
Mr. Justin .T. Yates
Dept. of Industrial and Systems Engineering
State University of New York at Buffalo
415 Lawrence D. Bell Hall
Buffalo, NY 14260-2050
_______________________________________________
Coin-lpsolver mailing list
Coin-lpsolver at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/coin-lpsolver

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/clp/attachments/20060324/2a235ea8/attachment.html>