Combinatorial optimization system that extracts an undersirable relationship from a present solution

摘要

A combinatorial optimization system to reduce the number of neighborhoods generated by modifying a part of the present solution so that one improvement can be performed in a short time, and to efficiently obtain an optimum solution without resulting in a local optimum solution. The system comprises a device for extracting from the present solution a relationship including a possible improvement in an objective function, a device for cumulatively storing all the extracted inclusive relationships, a device for generating a neighborhood of the present solution after modifying the inclusive relationship extracted from the present solution, a checking device for determining a neighborhood as a new solution when the generated neighborhood does not include the inclusive relationship stored in the inclusive relationship accumulative storage, and a controller for providing for the inclusive relationship extractor the new solution outputted by a checker until the searching conditions are satisfied to reach an optimum solution.