Search

In this paper, we introduce a class of stochastic programming problem with fixed charge recourse in which a fixed cost is imposed if the value of the continuous recourse variable is strictly positive. The algorithm of a branch-and-cut method to solve the problem is developed by using the property of the expected recourse function. Then, the problem is applied to a power generating system. The numerical experiments show that the proposed algorithm is quite efficient. The mathematical programming model defined in this paper is quite useful for a variety of design and operational problems.

It is commonly believed that the use of the assignment problem works well when one selects a relaxation problem within the framework of a branch and bound algorithm to solve an asymmetric traveling salesman problem (TS P) optimally. In this paper, we present asymmetric TSP instances found in real-life setting, and show that t.he above common belief is not necessarily appropriate. Based on the real-life example, a family of asymmetric TSP instances called SLOPE is considered, which are generated by deforming arc lengths of standard two-dimensional TSPs on a plane in a, specific manner. For this type of instances, we show that the assignmellt relaxation yields poor performance, and propose a minimum 1-arborescence relaxation similar to the minimum i-tree relaxation that has been successfullv applied to the symmetric TSPs. In order to make the algorithm more efficient, the propel' selection of Cc ro;t node and the detenninat,ion of Lagrange multipliers to increase the lower bounds are explored. Computational experiments with instances SLOPE and also with t.he real-life instance show that the proposed algorithm gives better computational performance than the algorithm with the assignment relax­ ation.