This paper deals with a general combinatorial optimization problem with uncertain element weights modeled by fuzzy intervals. A fuzzy interval is regarded as a possibility distribution describing the set of more or less plausible values of an element weight. In order to choose a ldquobestrdquo solution the concept of a necessary optimality and the concept of a necessary soft optimality are adopted. It is shown that the use of possibility theory leads to finding robust solutions under fuzzy weights. Some general algorithms that compute the degrees of necessary and necessary soft optimality of a given solution and find an optimal solution according to the introduced concepts are provided.