Assume there are several states, and the objective function f\+s(x) is linked with each state s. Robust optimization is to solve the following problem: min x∈X max s∈Sf\+s(x)where X is the feasible s...Assume there are several states, and the objective function f\+s(x) is linked with each state s. Robust optimization is to solve the following problem: min x∈X max s∈Sf\+s(x)where X is the feasible solution set, and S is the collection of states.\;It has been showed that most of robust combinatorial optimization problems are NP\|hard in strong sense. In this paper, we will discuss the borderline between the ′easy′ and the ′hard′ cases of robust combinatorial optimization problems, and further present a heuristic frame work to solve the ′hard′ problems and discuss their concrete implementation of the heuristic method.展开更多
基金Research is supported by the National 863 Program ( No.863- 306- Z T
文摘Assume there are several states, and the objective function f\+s(x) is linked with each state s. Robust optimization is to solve the following problem: min x∈X max s∈Sf\+s(x)where X is the feasible solution set, and S is the collection of states.\;It has been showed that most of robust combinatorial optimization problems are NP\|hard in strong sense. In this paper, we will discuss the borderline between the ′easy′ and the ′hard′ cases of robust combinatorial optimization problems, and further present a heuristic frame work to solve the ′hard′ problems and discuss their concrete implementation of the heuristic method.
