Originally posted by: Ali_Emi

Hello everyone,
I'm solving a problem where i have to minimize the number of vehicles and ensure that every trip is covered by one vehicle. I have maintenance constraints and graph constraints (where the nodes are the trips and there is an arc between the node i and j if a vehicle can do trip i after trip j). I have chosen the column generation approach because my problem has really a lot of trips (1xxx trips). So my restricted master problem has "R[Chemins]" as dvar where Chemins is the set of paths ( a path is a succesion of trips that can be performed by one vehicle) So R[p]=1 if the path p is chosen and 0 if not. So my objective function is "Minimize sum (p in Chemins) R[p]) In fact minimizing the number of paths means that we minimize the number of vehicles.  The only constraints that i have in the master problem is that every trip must be covered one time.
The set of paths that i begin with contains 64 paths and  garantee a feasible solution. 
For the other constraints such as maintenance constraints and graph constraints are all in the subproblem. The subproblem has an objective fonction that is minimizing this expression "1-sum (i in trips) Duals[i]*t[i] " where t is a single path, it correspands to the path that we will put in the set of paths of the master problem after resolving the sub problem(his dimension equals the number of trip, and his n-th value is equal to 1 if in this path we do the trip n and 0 if not) and Duals[i] correspond to the duals of the constraints in the master problem.
So when i execute this problem i have in the first iteration in the master problem 64 (the initial solution) after that we resolve the sub problem and we have -3 in his objective function and when we resolve the master problem in the second iteration the objective function is still 64 and it continues for all iterations without amelioration of the objective of the master problem. And the objective function in the subproblem decrease after each iteration ie in the 10 th iteration for example we have in the objective function of the sub problem -10.  Is this normal ? that the objective function of the master problem doesn't decrease and the objective function in the sub problem decrease? 
I hope that you have understanded me with my bad english.
 

Originally posted by: UserCplex

So, if I understand your question correctly, you are asking is it possible that the master problem objective function reduces by a larger amount even though the discovered reduced cost of a nonbasic variable has lesser magnitude?

Yes, this is indeed possible. Think of what the reduced cost of a nonbasic variable means. It denotes the change in objective function for a unit change in the value of the nonbasic variable. The min ratio test finds out how much this nonbasic variable can be increased and this min ratio could be different for different nonbasic variables and is independent of the reduced cost.

Yes, the min ratio test can give 0 as the amount of permitted change and yes, this would mean degeneracy.

Originally posted by: Ali_Emi

I have done some modification and there is the output that i have after each iteration:
Iternation 1: Objective function of the master problem 64
Objective function of the subproblem -2

Iternation 2: Objective function of the master problem 64
Objective function of the subproblem -2
Iternation 3: Objective function of the master problem 64
Objective function of the subproblem -2
And it goes like that for hours
So after each iteration there is no amelioration even if we generate after each iteration a new column