Apparatus for optimizing combinatorial optimization problems

An apparatus for optimizing a combinatorial optimization problem by using a computer, in which starting from an initial combination state, a destination state to which a certain state is to be moved is determined from one of its neighboring states and previously defined transferable combination states by using an evaluation function, and an optimal combination state for minimizing or maximizing the function value of an evaluation function comprising the sum of a function to be minimized or maximized and a penalty function representing an amount of constraint violation is found by iteratively performing a search in which the certain state is successively moved to the thus determined destination state,

• said apparatus comprising:
• first processing means for switching the evaluation function to a new evaluation function in which the weight of component other than the penalty function is reduced, thereby to find a sub-search initial evaluation function value, which is an evaluation function value for a current combination state, when there exists no neighboring state having an evaluation function value better than that of the current combination state, and when there still remains a constraint violation in the current combination state;
• second processing means for starting a search using the new evaluation function in such a manner that if a combination state having an evaluation function value better than the sub-search initial evaluation function value is reached within a predetermined number of searches, the search is continued while restoring the evaluation function to the original evaluation function, whereas if a combination state having an evaluation function value better than the sub-search initial evaluation function value is unable to be reached within the predetermined number of searches, it is determined that there exists no feasible solution, thereby ending the processing;
• third processing means for switching the evaluation function to a new evaluation function in which the weight of the penalty function is reduced, thereby to find a sub-search initial evaluation function value, which is an evaluation function value for the current combination state, when there exists no neighboring state having an evaluation function value better than that of the current combination state, and when there exists no constraint violation in the current combination state;
• and
• fourth processing means for starting a search using the new evaluation function in such a manner that if a combination state having an evaluation function value better than the sub-search initial evaluation function value is reached within a predetermined number of searches, the search is continued while restoring the evaluation function to the original evaluation function, whereas if a combination state having an evaluation function value better than the sub-search initial evaluation function value is unable to be reached within the predetermined number of searches, it is determined that there no longer exists a better solution, thus ending the processing.