Re: C++ for combinatorial optimization problems

Discussion in 'C++' started by Dietmar Kuehl, Sep 15, 2004.

  1. N4M wrote:
    > C++ is currently a dominant programming lanaguage to solve
    > Combinatorial Optimization problems. Will other languages be able to
    > compete with C++ in this field?


    IMO, none of the other popular languages (C, Java, C#, Fortran,
    Perl, Python, ...) is well suited to implement non-trivial
    algorithms. It can be done in these languages but is unnecessary
    hard. Whether this will change in the future depends on the
    languages. I think support for generic programming is required
    for effective support of non-trivial algorithms.

    > Could you suggest some C++ libraries for Combinatorial Optimization?


    The Boost Graph Library (BGL) has algorithms for several
    combinatorial problems. Of course, those implemented can be
    solved in polynomial time. There is no general solver for
    combinatorial optimization in this library (like an implementation
    of the Simplex algorithm).

    > It is probably that a library will address a certain problem, e.g.
    > Max-Cut, TSP etc., that would already be fine.


    It is unlikely that anybody implements something addressing these
    problems: the problems you mention are NP-hard and thus only
    solvable for very small problem instances or in cases where
    additional structure information is available and can be exploited
    (e.g. TSP can be solved if certain restrictions on the distances
    are imposed - if I remember correctly).
    --
    <mailto:> <http://www.dietmar-kuehl.de/>
    <http://www.contendix.com> - Software Development & Consulting
     
    Dietmar Kuehl, Sep 15, 2004
    #1
    1. Advertising

  2. Dietmar Kuehl

    Guest

    "Dietmar Kuehl" <> wrote in message news:<ci989v$>...
    > N4M wrote:
    > > C++ is currently a dominant programming lanaguage to solve
    > > Combinatorial Optimization problems. Will other languages be able to
    > > compete with C++ in this field?

    >
    > IMO, none of the other popular languages (C, Java, C#, Fortran,
    > Perl, Python, ...) is well suited to implement non-trivial
    > algorithms. It can be done in these languages but is unnecessary
    > hard. Whether this will change in the future depends on the
    > languages. I think support for generic programming is required
    > for effective support of non-trivial algorithms.


    I think C and C++ are not well suited to problems involving
    multidimensional arrays, which are most of the problems I deal with.
    IMSL and NAG have Fortran 77, Fortran 90, and C libraries, but not C++
    libraries AFAIK. They expect C++ programmers to call their C
    libraries. Do IMSL and NAG only implement "trivial" algorithms? The
    Numerical Recipes C++ library is not that different from the C
    version.
     
    , Sep 16, 2004
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. RZ
    Replies:
    2
    Views:
    517
  2. N4M
    Replies:
    4
    Views:
    1,002
    Merrill & Michele
    Sep 18, 2004
  3. Dietmar Kuehl
    Replies:
    1
    Views:
    592
  4. sdf
    Replies:
    0
    Views:
    404
  5. Ravikiran

    Zero Optimization and Sign Optimization???

    Ravikiran, Nov 17, 2008, in forum: C Programming
    Replies:
    22
    Views:
    891
    Thad Smith
    Nov 24, 2008
Loading...

Share This Page