0
$\begingroup$

/*********************************************

  • OPL 12.10.0.0 Model
  • Author: Shahrukh
  • Creation Date: 10-Apr-2024 at 11:55:50 PM

The podrace tournament involves n competitors (where n is even) who all race against each other over the course of n-1 day. Each competitor races once a day and each competitor must race against every other competitor over the course of a tournament. For each race, the two competitors have starting positions (called tracks). The left track (named 0) is a better starting position than the right track (named 1). As a result, each competitor cannot start too many consecutive times on the left track (and vice versa for the right track) to ensure as much fairness as possible. The number of successive times a competitor can start on a specific track is given by the constant maxSucc (e.g., maxSucc = 2)

*********************************************/

 int nbCompetitors = 20;
int nbDays = nbCompetitors - 1;
range Days = 1..nbDays;'
range Competitors = 1..nbCompetitors;
range Tracks = 0..1;
int maxSucc = 2;

// Decision variables
dvar int opp[Competitors][Competitors][Tracks] [Days] in 0..1; //in 1..nbCompetitors;
//1 if competitor 'c1' races with 'c2' on track 't' on day 'd'
//dvar int track[Competitors, Days] in Tracks;

//minimze number of races
minimize sum    (c1 in Competitors,c2 in Competitors, t in Tracks,d in Days) opp[c2][c1][t][d]/2;
 constraints {
 //subject to {
 // Ensure each competitor races all others exactly once and cannot race agains each other
 forall(c1 in Competitors, c2 in Competitors :c1!=c2 )  
 sum(d in Days, t in Tracks) opp[c1][c2][t][d] == 1; // Can't race against oneself

 // if one racer is at track sero the other should be at one 
 forall(c1 in Competitors, c2 in Competitors,d in Days, t in Tracks :c1!=c2 ) {
  if (t==0){
     opp[c1][c2][t][d]==opp[c2][c1][1][d];
  if (t==1){
     opp[c1][c2][t][d]==opp[c2][c1][0][d];
  }}}   





//can race only once a day
forall(c1 in Competitors,d in Days )   
sum (c2 in Competitors, t in Tracks) opp[c1][c2][t][d] == 1;

//maxsuccint
forall(c1 in Competitors,d in Days : d <= nbDays - maxSucc) {
// Track 0 (left track)

    sum(c2 in Competitors,k in 0..maxSucc) opp[c1][c2][0][d+k] <= maxSucc;

// Track 1 (right track)

    sum(c2 in Competitors,k in 0..maxSucc) opp[c1][c2][1][d+k] <= maxSucc; 

}


}


execute {
for (var d = 1; d <= nbDays; d++) {
    writeln("Day " + d + ":");
    for (var c1 = 1; c1 <= nbCompetitors; c1++) {
        for (var c2 = 1; c2 <= nbCompetitors; c2++) {
            if (c1 != c2 && opp[c1][c2][0][d]==1 && opp[c2][c1][1][d]==1 ) {
                
                writeln("  Competitor " + c1 + " vs Competitor " + c2 + " with Competitor " + 
                c1 + " on track 0 and Competitor " + c2 + ' on track 1' );
            }
        }
    }
   } 
  }

I have solved this problem using IP, however when I solve this using CP and I remove the objective function ( which basically counts number of races) it starts taking enormous computational time, can anyone explain why so?. Further more, I want to solve this problem using global constraints like packing and count. Any idea how to formulate the same problem using these constraints.

$\endgroup$

3 Answers 3

1
$\begingroup$

Global constraints:

You could turn

minimize sum    (c1 in Competitors,c2 in Competitors, t in Tracks,d in Days) opp[c2][c1][t][d]/2;

into

minimize 
 count(opp,1)/2;

and

forall(c1 in Competitors,d in Days )   
sum (c2 in Competitors, t in Tracks) opp[c1][c2][t][d] == 1;

into

forall(c1 in Competitors,d in Days )   
    count(all(c2 in Competitors, t in Tracks) opp[c1][c2][t][d],1) == 1;
$\endgroup$
1
$\begingroup$

In addition to using global constraints (mentioned elsewhere), I would recommend reconsidering your variables. The binary variable structure you are using is required in MILP models, but CP models are more flexible in their use of integer variables. For instance, you might want to use an array of integer variables (indexed by competitor and day) to hold the assigned track for each competitor on each day.

Edit: I have a CP optimizer model (using the Java API -- I don't do OPL) that finds a feasible schedule in well under a second. It does not (yet) have an objective function, it just grabs the first feasible schedule. The variables are $x_{d,i},$ the index of the opponent of competitor $i$ on day $d,$ and $y_{d, i},$ the lane assignment (0 or 1) of competitor $i$ on day $d.$ Constraints are as follows:

  • You never race against yourself (because you will be sure to lose): $x_{d,i} \neq i$
  • You are your opponent's opponent: $x_{d,x_{i,d}}=i$ -- this uses a global constraint CPO calls inverse
  • You never race the same opponent twice: $x_{d,i}\neq x_{d',i} \, \forall i,\, \forall d'\neq d$ -- this uses CPO's version of the global all different constraint
  • You and your opponent are in different lanes: $y_{d,x_{d,i}}\neq y_{d,i}$ -- this uses CPO's element constraint to let a variable (here $x_{d,i}$) index another variable (here $y_{d,.}$)
  • You cannot be in either lane for more than $M=2$ consecutive days: $1 \le \sum_{t=d}^{d+M} y_{d,t} \le M \,\, \forall d$ (skipping days where you do not have $M$ subsequent days, of course)

Edit 2: I added as an objective minimizing the difference between the maximum and minimum number of left lane assignments incurred by an competitor. CPO gets the difference down to one in under a second, but after five minutes (the limit of patience) had not gotten it down to zero.

$\endgroup$
4
  • $\begingroup$ prof rubin, can you help me on how to formualte this problem using global constraint instead. Also are there any good resources to learn cp modellng by using global cosntraint. I have a good understandaing of milp modelling but i am new to cp especiallly using global constraints. $\endgroup$ Apr 29 at 15:46
  • 1
    $\begingroup$ There are a number of MOOCs covering CP modeling (including mooc-list.com/course/modeling-discrete-optimization-coursera), although they don't necessarily use CP Optimizer. One key difference between MIP and CP is that different CP solvers support different global constraints (whereas all MIP modeling languages and solvers support linear equality/inequality constraints). Taking a MOOC would be a good start, but you would still need to learn the specific global constraints in CPO. $\endgroup$
    – prubin
    Apr 29 at 16:22
  • $\begingroup$ As for providing a formulation, at the moment I'm afraid I don't have that much free time. $\endgroup$
    – prubin
    Apr 29 at 16:22
  • $\begingroup$ thanks a lot prof rubin for the mooc suggestion, as for formulation no worries, -Regards Shahrukh $\endgroup$ Apr 29 at 16:40
0
$\begingroup$

I have solved this problem using IP, however when i solve this using CP and i remove the objective function ( which basicaly counts number of races) it starts taking enormous computational time, can anyone explain why so?

Ignoring potential "problem might fit ILP approaches more" reasoning, it's well-known, that:

  • ILP (and SAT-solvers) are extremly well-perfoming in black-box settings as they have strong automatic search
  • While CP allows lots of fine-tuned control of search, it's often not only optional, but needed to obtain good results.

The following resource Link: Springer gives much more background on this:

Puget, Jean-Francois. "Constraint programming next challenge: Simplicity of use." Principles and Practice of Constraint Programming–CP 2004: 10th International Conference, CP 2004, Toronto, Canada, September 27-October 1, 2004. Proceedings 10. Springer Berlin Heidelberg, 2004.

Small excerpt:

"Indeed, the paradigm of mathematical programming tools can be concisely defined as: “model and run”. This means that the main thing one has to worry about is how the problem is specified in terms of variables, constraints and objective functions. There is no need to deal with how the search for solution should proceed for instance."

(I think you recognized yourself, that global-constraints are powerful and not (currently) exploiting them also hurts your performance)

$\endgroup$
1
  • $\begingroup$ how do i convert this program using global constraints ? any idea? i suspect we can use global constraints such as pack , to schedule which races happens on which day , but i dont know how to do it, how do i ensure the maxsucc cosntraint using global constraitns, thats where i am javing hardtime $\endgroup$ Apr 29 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.