Re: [eclipse-clp-users] Knappsack-Problem Modification

Am 13.04.2010 13:46, schrieb Marco Gavanelli:
>
> My guess is that it is not NP-complete, but NP-hard, since it is an 
> optimization problem and not a satisfaction problem.
>
> I would suggest to use the eplex library, as your problem can be seen as 
> an integer programming problem, and eplex is probably the most efficient 
> way to solve it.
>   

I would agree to trying to solve it with eplex, but you should be
careful about what LP/MIP solver you use when you formulate it as an IP
problem. In my experience, CLP/CBC as the external LP solver works ok if
you have a pure LP formulation. However, I always ran into trouble when
trying to use CLP/CBC for MIP problems. It just didn't scale. As an
academic user, you should have access to CPLEX. In that case, there
shouldn't be any problem. If you have to use CLP/CBC (which comes as
default LP solver with ECLiPSe), try to formulate the problem as a pure
LP problem (using SOS1 sets).

Cheers,
Thorsten