Abstract:

It is undoubtedly significant to study the change rules of the optimal values  of optimization problems, when the set of feasible solutions changes follow some parameters, even if there is no way to get the optimal value generally. For continuous optimization, where the independent variables are numbers or vectors, the characteristics of the optimal value functions following the changing of the variables has been studied extensively, but for discrete optimization problems there is few literature. In this paper some important classical combinatorial optimization problems are considered. We mainly focus on the characteristics of the optimal value functions, here the independent variables are some plans or tours, may not be numbers nor vectors. Parallel scheduling problem, Knapsack problem, Traveling salesman problem are considered in the paper, focusing on  the characteristics of the optimal value functions of these problems if the inputs of parameters are change. Finally, we also consider the characteristics of objective function arised by some famous algorithms such as LPT to  minimize  the makespan of parallel machine schedule.

Key words: schedule, traveling salesman problem, Knapsack problem, optimal value function, subdifferential