VRP - Column Generation (no solution)

[Helen]

I am trying to solve a Bus Crew Scheduling problem using set partitioning.

I have relaxed the problem into the Restricted Master Problem and Pricing Problem, following the model for the " Gilmore-Gomory Method for Cutting Stock Problem". 

My notation is as follows:

# NOTATION

# i in P - set of trips to be covered (total of 70)

# j in R - set of all feasible runs

# Cj - cost of run j in R (parameter "RunCost[j]")

# Xj - 1 if run j in R is selected (decision var "Schedule[j]")

# Aij - 1 if trip i is included in run j (param matrix "TripInRun[j,i]")

My set of feasible runs has over ~900 options, so the TripInRun matrix is of size [~900x70].

My problem is that when I run my code, the nRun only increases up to 70 instead of 900, so my solution for Xj (or Schedule[j]) is zeros. Would you mind telling me what the problem is? Thank you in advance.

.MOD CODE:

problem MasterProblem ;

# ---------------------------------------

param nRun integer >=0 , default 0;

set Run ; # these are like routes.

set Trip; # these are tasks that must be done or nodes that must be visited.

param TripInRun {1..nRun,Trip};

param RunCost {1..nRun};

var Schedule {1..nRun} integer >=0 ; #binary;    # = 1 if run j in R is selected. 0 otherwise.

minimize ServiceCost: # no resource constraints in this problem

   sum {j in Run: j <= nRun} RunCost[j] * Schedule[j] ;

subj to TripCovering {i in Trip}:

  sum {j in Run: j <= nRun} Schedule[j] * TripInRun [j,i] >= 1 ;

  

problem PricingProblem;

  # ---------------------------------------

  

param price {Trip} default 0;

var Use {1..nRun} integer >=0;

  

minimize ReducedCost:  

  sum {j in 1..nRun} (RunCost[j] - sum {i in Trip} price[i] * TripInRun[j,i]) * Use[j]; 

 

subj to Pick_Run_Column:  

sum {j in 1..nRun} Use[j] >=1;

RUN CODE (WITH AMPL CPLEX):

(...)

problem MasterProblem;

option relax_integrality 1;

option presolve 0;

problem PricingProblem;

option relax_integrality 0;

option presolve 1;

let nRun := 0;

for {i in Trip} {

let nRun := nRun + 1;

display nRun;

};

repeat {

solve MasterProblem;

let {i in Trip} price[i] := TripCovering[i].dual;

solve PricingProblem;

if ReducedCost < -0.00001 then {

let nRun := nRun + 1;

}

else break;

};

display Schedule, ServiceCost;

option MasterProblem.relax_integrality 0;

option MasterProblem.presolve 10;

solve MasterProblem;

display Schedule, ServiceCost;

ERROR:

Error at _cmdno 224 executing "solve" command

(file C:\..., line 41, offset 978):

error processing param TripInRun:

64540 invalid subscripts discarded:

TripInRun[71,1]

TripInRun[71,2]

TripInRun[71,3]

and 64537 more.

Error at _cmdno 224 executing "solve" command

(file C:\..., line 41, offset 978):

error processing param RunCost:

922 invalid subscripts discarded:

RunCost[71]

RunCost[72]

RunCost[73]

and 919 more.

CPLEX 12.7.0.0: optimal solution; objective 400

6 dual simplex iterations (0 in phase I)

CPLEX 12.7.0.0: optimal integer solution; objective 0

0 MIP simplex iterations

0 branch-and-bound nodes

No basis.

Schedule [*] :=

 1 1    8 0   15 0   22 0   29 0   36 0   43 0   50 0   57 0   64 0

 2 1    9 0   16 0   23 0   30 0   37 0   44 0   51 0   58 0   65 0

 3 0   10 0   17 0   24 0   31 0   38 0   45 0   52 0   59 0   66 0

 4 0   11 0   18 0   25 0   32 0   39 0   46 0   53 0   60 0   67 0

 5 0   12 0   19 0   26 0   33 0   40 0   47 0   54 0   61 0   68 0

 6 0   13 0   20 0   27 0   34 0   41 0   48 0   55 0   62 0   69 0

 7 0   14 0   21 0   28 0   35 0   42 0   49 0   56 0   63 0   70 0

;

ServiceCost = 400

CPLEX 12.7.0.0: optimal integer solution; objective 400

0 MIP simplex iterations

0 branch-and-bound nodes

No basis.

Schedule [*] :=

 1 1    8 0   15 0   22 0   29 0   36 0   43 0   50 0   57 0   64 0

 2 1    9 0   16 0   23 0   30 0   37 0   44 0   51 0   58 0   65 0

 3 0   10 0   17 0   24 0   31 0   38 0   45 0   52 0   59 0   66 0

 4 0   11 0   18 0   25 0   32 0   39 0   46 0   53 0   60 0   67 0

 5 0   12 0   19 0   26 0   33 0   40 0   47 0   54 0   61 0   68 0

 6 0   13 0   20 0   27 0   34 0   41 0   48 0   55 0   62 0   69 0

 7 0   14 0   21 0   28 0   35 0   42 0   49 0   56 0   63 0   70 0

;

ServiceCost = 400 

[Robert Fourer]

You define

param TripInRun {1..nRun,Trip};
param RunCost {1..nRun};

but then it seems you are initially setting nRun to the number of members of set Trip:

let nRun := 0;
for {i in Trip} {
let nRun := nRun + 1;
display nRun;
};

Thus nRun is initially 70 and any data you provided for, say, TripInRun[71,1] or RunCost[71] will be discarded with the error messages you see. Probably you want to index TripInRun and RunCost over something like 1..allRun, where param allRun is set to the total number of runs given in the data.

Also notice that even if there are 900 runs in your data, your "repeat" loop and your script will terminate as soon as ReducedCost >= -0.00001.

Bob Fourer
am...@googlegroups.com

=======

[khan]

--------------------------------------------------------------------------------------
CPLEX 12.8.0.0: optimal solution; objective -7.701927823e-05
0 dual simplex iterations (0 in phase I)
--------------------------------------------------------------------------------------

Can you please explain what does it mean by the above result? i got some optimal solution value here but with 0 dual simplex iterations (0 in phase What does this mean?

[AMPL Google Group]

CPLEX performs preprocessing in your problem. The CPLEX found an optimal solution in preprocessing phase and didn't need to run the simplex algorithm.

Thanks
Paras

--
Paras Tiwari
am...@googlegroups.com

{#HS:523805872-413#}

--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ampl+uns...@googlegroups.com.
To post to this group, send email to am...@googlegroups.com.
Visit this group at https://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.

[Muhammad umar]

Greetings,

Thank you for your response and useful information. Does this mean that the problem is so much simple or what? how can we interpret this?

1- Also, I want to know that in the following output Presolve eliminates 10 constraints.

2- And it says Adjusted problem: ..1 constraint, all linear; 5 nonzeros 1 inequality constraint

However, I am having 3 constraints in total.

Does 1 and 2 means that presolve phased has ignored my constraints? And they dont have any effect on the objective function and optimal value found?
  

OUTPUT:

----------------------------------------------------------------------------
Presolve eliminates 10 constraints.
"option presolve 2;" used.
Adjusted problem:
5 variables, all linear
1 constraint, all linear; 5 nonzeros
    1 inequality constraint
1 linear objective; 5 nonzeros.
----------------------------------------------------------------------------

Thanking you in anticipation.

-- 

Best Regards 

M. Umar Khan

To unsubscribe from this group and stop receiving emails from it, send an email to ampl+unsubscribe@googlegroups.com.

To post to this group, send email to am...@googlegroups.com.
Visit this group at https://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to a topic in the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/ampl/pX7z1stk-uY/unsubscribe.
To unsubscribe from this group and all its topics, send an email to ampl+unsubscribe@googlegroups.com.

[AMPL Google Group]

Yes, the problem is simple enough to be solved in the preprocessing stage. There are two preprocessing happens when you send solve command. AMPL runs presolve and tries to eliminate the constraints and variables. You can read about AMPL presolve at https://ampl.com/BOOK/CHAPTERS/17-solvers.pdf. The solver also perform preprocessing after AMPL send the problem to solver. So, it seems that AMPL eliminated 10 constraints from your problem in its presolve phase.

--
Paras Tiwari
am...@googlegroups.com

{#HS:523805872-413#}

To unsubscribe from this group and stop receiving emails from it, send an email to ampl+uns...@googlegroups.com.

[Muhammad umar]

To eliminate 10 constraints from the problem means that they don’t fulfil the requirements sets by bounds?

Or they don’t get fit into the problem?

-- 

Best Regards 

M. Umar Khan

To unsubscribe from this group and stop receiving emails from it, send an email to ampl+unsubscribe@googlegroups.com.

To post to this group, send email to am...@googlegroups.com.
Visit this group at https://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.

--

You received this message because you are subscribed to a topic in the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/ampl/pX7z1stk-uY/unsubscribe.
To unsubscribe from this group and all its topics, send an email to ampl+unsubscribe@googlegroups.com.

[AMPL Google Group]

AMPL ignores the constraint when it determines that the constraints don't impact the optimal value of the solution. So, your original problem can be reduced to a new smaller problem and the optimal solution of the new smaller problem is the same as that of the original problem. Therefore, AMPL eliminates the constraints and solves the smaller problem to get the solution of the original problem.

--
Paras Tiwari
am...@googlegroups.com

{#HS:523805872-413#}

On Fri, Feb 16, 2018 at 8:25 PM UTC, <am...@googlegroups.com> wrote:

To eliminate 10 constraints from the problem means that they don't fulfil the requirements sets by bounds?
Or they don't get fit into the problem?


--
Best Regards
M. Umar Khan

On Fri, Feb 16, 2018 at 8:11 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

Yes, the problem is simple enough to be solved in the preprocessing stage. There are two preprocessing happens when you send solve command. AMPL runs presolve and tries to eliminate the constraints and variables. You can read about AMPL presolve at https://ampl.com/BOOK/CHAPTERS/17-solvers.pdf. The solver also perform preprocessing after AMPL send the problem to solver. So, it seems that AMPL eliminated 10 constraints from your problem in its presolve phase.

--
Paras Tiwari
am...@googlegroups.com

To unsubscribe from this group and stop receiving emails from it, send an email to ampl+uns...@googlegroups.com.