حل مساله فروشنده دوره‌گرد TSP در نرم افزار CPLEX

 

در این پست نحوه کدنویسی مدل برنامه‌ریزی عدد صحیح مساله فروشنده دوره گرد تشریح می‌شود.

مدل برنامه ریزی عدد صحیح مساله فروشنده دوره گرد را به صورت زیر در نظر بگیرید:

$$\textbf{minimize} \quad \sum_{i \in A} \sum_{j \neq i, j \in A} c_{ij} x_{ij} \\ \textbf{s.t.} \quad \sum_{i \in A,i \neq j} x_{ij}=1, \quad j \in A \\ \textbf{ }\quad \sum_{j \in A,j \neq i} x_{ij}=1, \quad i \in A \\ u_i – u_j + (n-1)x_{ij} \leq n-2 \quad i \in A \backslash \{1\},j \in A \backslash \{1\}, i\neq j$$

 

که محدودیت آخر به محدودیت های حذف تور Miller–Tucker–Zemlin مشهور هستند. در این مساله متغیر \( x_{ij} \) متغیر تخصیص می باشد. و مجموعه \( A \) شامل اندیس تمامی شهرها می باشد.
$$A = \{1,2,…,n\}$$
و کد نرم افزار CPLEX به شرح زیر است.

/*********************************************
 * OPL 12.6.0.0 Model
 * Author: M. Namakshenas
 * Model: Travelling Salesman Person (TSP)
 *********************************************/
int nbcities = ...;
range city = 1..nbcities;
 
int cost[city][city]= ...;

dvar boolean x[city][city];
dvar float+ u[city];

minimize
 sum(i,j in city:i!=j)
 cost[i][j]*x[i][j];
 
subject to {

forall(j in city)
 sum(i in city:i!=j) x[i][j]==1;
 
forall(i in city)
 sum(j in city:i!=j) x[i][j]==1; 
 
forall(i,j in 2..nbcities:i!=j)
 u[i] - u[j] + (nbcities-1)*x[i][j] <= nbcities-2;
}
5 Comments
Inline Feedbacks
View all comments
سعید
ژوئن 21, 2019 7:55 ب.ظ

سلام مجدد.

هرچی سرچ کردم؛ تنها نسخه ۳۲ بیتی سیپلکس رو پیدا کردم. و نتونستم ۶۴بیتی رو دانلود کنم.
p30download هم نسخه ۳۲ بیتی گذاشته.

شما لینکی دارید که نسخه ۶۴ بیتی باشه؟ چونکه به این نسخه نیازمندم.

باتشکر

سعید
ژوئن 19, 2019 8:49 ب.ظ

سلام.
خیلی ممنون بابت آموزش.

آیا سیپلکس همانند گروبی، نیازمند دامین دانشگاهی هست چهت فعالسازی؟

یا به راحتی میشه نصبش کرد؟

باتشکر

سعید
Reply to  admin
ژوئن 20, 2019 11:44 ق.ظ

ممنون از راهنماییتان