|
|
|
<from JJHF>
|
|
“CBC is at version 0.9.? It
is designed to be much more flexible than any commercial solver (e.g. David
Wright is using Lot sizing). When (and
if I am allowed to work on it again) it gets to 1.0 it should be a free, good
license, code which will outperform any other free code. The aim is to be a reference code so that people either compare their
codes to Cplex or Cbc.” –JJHF
|
|
“I have no idea whom you can
talk about. IBM Japan were using for a
steel problem. Edwin Straver may use
it for a free solver version. <edit>
Pierre Bonami at CMU is using it (I think for nonlinear mip). Michael Bussieck of Gams is also looking at
it for the free solver. Fabrizio
Ferrandi is obviously using it for something interesting. David Wright in Australia seems to be
building a product using it.” - JJHF
|
|
|
|
Users
|
|
Fabrizio Ferrandi, Dipartimento
di Elettronica e Informazione, Politecnico di Milano. 2 uses.
|
|
(1) We are currently using
CBC in our research aiming at high-level synthesis of C
|
|
based specifications. This
is an abstract of a paper we are working on:
|
|
---------------------------------------------------------------------------------------------------------------
|
|
Abstract: Recent research
results have seen the application of parallelizing techniques to high-level
synthesis. In particular, the effect of speculative code transformation on
mixed control-data flow designs has demonstrated effective results on schedule lengths. In this paper we first analyze the
use of control and data dependence graph as
an intermediate representation that provides the possibility of
extracting the maximum parallelism. Then we analyze the scheduling problem by
formulating an approach based on Integer Linear Programming (ILP) to minimize
the number of control steps given the amount of resources. We improve the
already proposed ILP scheduling approaches by introducing a new conditional
resource sharing constraint which is then extended to the case of speculative
computation. To efficiently solve the ILP formulation we use a standard
Branch and Cut framework. Experimental results show that this framework gives
better results
|
|
with respect to well known
techniques.
|
|
-------------------------------------------------------------------------------------------------------------------------
|
|
(2) Moreover, we are
thinking to port on the COIN-OR framework an old work on logic synthesis
based on Lagrangean relaxation. This work has been published and this is the
reference: R. Cordone, F.Ferrandi, D.
Sciuto, R. Wolfler Calvo, “An Efficient Heuristic Approach to Solve the Unate
Covering Problem” IEEE Transactions on
Computer-Aided Design of Integrated Circuits and Systems, vol. 20, n. 12,
December 2001, pp. 1377 – 1388. In
case of interest this is the abstract:
|
|
---------------------------------------------------------------------------------------------------------------
|
|
Abstract: The paper presents
a new approach to solve the unate covering problem based on exploitation of information provided
by agrangean relaxation. In
particular, main advantages of the
proposed heuristic algorithm are the effective choice of elements to be
included in the solution, cost-related reductions of the problem, and a good
lower bound on the optimum. The results support the effectiveness of this
approach: on a wide set of benchmark problems, the algorithm nearly always
hits the optimum and in most cases proves it to be
|
|
such. On the problems whose
optimum is actually unknown, the best known result is strongly improved
|
|
-------------------------------------------------------------------------------------------------------------------------
|
|
(3) David Wright (7/24/05)
|
|
Hi Robin
|
|
Yes, we are using CLP/CBC in
our product. Our product is still pre-release and therefore we cannot discuss
it in any detail at the
|
|
moment unfortunately. We
expect to make a public release in a matter of months.
|
|
|
|
We have found Clp/Cbc to be
a fantastic toolset for LP and MIP problems. It is very robust and quite
mature, though there are clearly significant and very desirable improvements
planned for the future and under development.
|
|
|
|
We use a number of features
of CBC which are not universally supported by other solvers and will over
time use the tuning features of CBC to improve performance further. In
particular we use generalised lot-sizing (more than just semi-continuous
variables) and
|
|
SOS(n).
|
|
|
|
The API has been on the
whole easy to work with given that we have used it as it has developed. John
Forrest has been exemplary in
|
|
responding to our questions
and troubleshooting and we would particularly like to express our gratitude
to him.
|
|
|
|
Our product is designed to
be able to support a number of different LP/MIP codes as plug in modules.
This is important to us so that we
|
|
can compare and contrast
different codes and pick the best for our needs. At the moment we choose
Clp/Cbc as the best for these needs.
|
|
We will be going through
another evaluation cycle before final product release, so this may change of
course.
|
|
|
|
I hope the above is of some
use to you, in particular we would like to say that having such a high
quality MIP code available for use by
|
|
startup companies such as
our venture is a wonderful enabling technology and I am sure many will follow
this path in the future.
|
|
|
|
Regards
|
|
David
|
|
|
|
--
|
|
Dr David Wright
|
|
PanLogica Pty Ltd
|
|
PO Box 778
|
|
Sandy Bay 7006
|
|
Australia
|
|
Ph: 0412 009 703
|
|
mailto:David.Wright@panlogica.com
|
|
--------------------------------------------------------------------------------------------------------
|
|
(4) GAMS
|
|
Robin,
|
|
Here is some more
information about our work with COIN here at GAMS. Hopefully it helps to
prepare your talk for Monday.
|
|
|
|
About two years ago, GAMS
started to build a small object layer to connect the COIN/OSI interface and
our GAMS IO library so we could feed OSI with LP and MIP problems generated
by GAMS. This small project turned out to be a highly successful. One the one
hand we could offer our clients reliable access to open source mathematical
programming solvers like Cbc and Glpk. On the other hand with the help of our
clients and our rigorous testing facilities, we have been finding and fixing
bugs in COIN that hopefully improved the overall quality of COIN.
|
|
|
|
We have about 100 downloads
of the GAMS system a day. Each and everyone contains the COIN solvers. We
unfortunately don't have the sales staff to know exactly what our client are
doing, but we frequently hear about people working with the COIN solvers (sometime
with a description of a bug). For example, in Germany we have a company (I am
not allowed to reveal their name) using Cbc on a daily bases to solve medium
sized periodic scheduling problems. Moreover, Josef Kallrath created a
cutting stock application written in GAMS used in several paper mills that in
its core solves several small to medium sized MIPs with Cbc.
|
|
|
|
We hope that we can
intensify the work between GAMS and COIN, e.g. by contributing to a standard
way of interfacing with non-linear programming solvers, an area where GAMS
has acquired expertise for the last two decades.
|
|
|
|
Regards,
|
|
Michael Bussieck &
Steven Dirkse
|
|
|
