آی اس آی پیپر

دانلود رایکان مقاله انگلیسی ISI با موضوع چارچوب برش و شاخه برای مسئله ثابت فروشنده دوره گرد

عنوان فارسی مقاله:

یک چارچوب برش و شاخه برای مسئله ثابت فروشنده دوره گرد

عنوان انگلیسی مقاله:

A branch-and-cut framework for the consistent traveling salesman problem

دانلود رایگان مقاله ISI با فرمت PDF:

مشاهده توضیحات کامل و خرید ترجمه فارسی با فرمت ورد تایپ شده:

بخشی از مقاله انگلیسی :

5. Branch-and-cut framework

We implemented three separate branch-and-cut algorithms, one based on each of the formulations presented in Sections 3.1, 3.2 and 3.3. At the interest of working with sufficiently tractable linear programming (LP) relaxations, a subset of applicable constraints are initially ignored and added later as cutting planes, if necessary. More specifically, in the case of Formulation 1, the initial LP relaxation consisted only of the degree constraints (3) and (4), along with continuous bounds on the x variables (relaxation of the integrality restrictions (2)). In the case of Formulation 2, constraints (9)–(11) were considered, along with the degree constraints and variable bounds, while in the case of Formulation 3, the initial LP relaxation consisted of constraints (12) and (13), in addition to the degree constraints and variable bounds. The SEC, 2MC and IPEC were considered in all cases as cutting planes and dynamically added back to the applicable model, when found to be violated, at each node of the search tree. At the root node, if we are unable to generate any additional violated inequalities, we permanently fix nonbasic x variables to their current values using reduced cost information. Let UB be the current (incumbent) upper bound (obtained through a heuristic or otherwise) and let LB be the global (root-node) lower bound obtained from the applicable LP relaxation. Let c¯ijp be the reduced cost of each nonbasic variable xijp in the root-node LP solution. Then, if xijp = 0 and LB + c¯ijp > UB, we can fix this variable to zero. Conversely, if xijp = 1 and LB − c¯ijp > UB, then we can fix this variable to one. In a similar manner, using a local lower bound, one may set non-basic x variables to their current values in the sub-tree associated with each node of the search process.These fixings ensure that the variables are never branched upon in the corresponding sub-trees. The remainder of this section elaborates on our separation routines and associated protocols.