Originally posted by: ACJ4_Telmo_Matos

Hi,

I am working on transportation problem (TP) and i encounter a problem solving it with CPLEX (using C language).

I want to solve several TP and I want to use the same data from earlier TP formulation and use it for solve other TP (this way saving computational time). The initial data is the same for all the TP, only changing (adding or deleting) a warehouse from the problem data, maintaining always the set of costumers.

I try to use CPXcopylp for copying the original problem (with all warehouse opened) and I use the CPXchgobj for setting to 0 the coefficient of the objective function, the CPXdelrows dor deleting rows, CPXdelrows for deleting columns and the CPXchgcoef for setting to 0 the cofficient of the constraints.

After optimize the problem, the variable that I deleted appear in the solution and I cannot read and understand this solution.

Thank you.

#DecisionOptimization
#MathematicalProgramming-General

Try printing the modified model (or export it to an LP-format file). Most likely you are not making the changes you think you are making.

I also think you are going about this the hard way. I would build a single model containing all the facilities. To eliminate (restore) a facility, just change the right hand side of the capacity constraint to zero (actual capacity). The presolver will automatically eliminate variables associated with a closed facility.

Paul

 

 

 

 

 

 

#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: ACJ4_Telmo_Matos

Hi, thanks for your answer.

Well, you are right, the simple way to do what i want is to set the right hand side (RHS) to zero (to eliminate) or set the RHS to the actual capacity.

Bellow i give an example of a 6 by 5 problem (6 warehouses and 5 customers).

First line is warehouse and customer.

Next line [capacity] [opening cost]

Next So for each customer: 

[demand of j] 
[cost of allocating all demand of customer to facility

I want to eliminate the last warehouse (resulting to a 5 by 5 problem and the capacity of warehouses can serve all the 5 customers). For that i use the CPXchgrhs an i have this (the RHS of c6 is set to zero):

When i print the solution, the variables x26, x27, x28, x29, x30 appear in the solution.

Is there any way to remove them? I try to use the CPX_PARAM_PREIND but didn't work..

Thank you.

#DecisionOptimization
#MathematicalProgramming-General

Why do you need to remove them? Just ignore them (don't print them, don't use them).

#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: ACJ4_Telmo_Matos

Hi, thanks again for your answer.

I thought, considering your response, that these variable would be eliminated from the solution (My mistake!)..But yes, just ignore these variables wold do the trick..

Just one thing: is the function CPXcopylp the most appropriate to do the delete/insert facility? Solving the problem with all facilities open and then use the CPXcopylp to copy the problem and then delete/insert facility? is this the most efficient (time consumption) process?

 

thanks again :) 

#DecisionOptimization
#MathematicalProgramming-General

I don't know why you need a separate copy of the LP, so I'm not sure how to answer. In any case, I don't use the C API, so it would probably be best to get someone else's opinion.

#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: ACJ4_Telmo_Matos

Well, my goal is load data only once into CPLEX and them reoptimize n times.

Well, but i think that i can manage with what you said earlier.

Thanks again :)

#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: ACJ4_Telmo_Matos

Hi,

I implemented the a model like you said: "build a single model containing all the facilities. To eliminate (restore) a facility, just change the right hand side of the capacity constraint to zero (actual capacity)".

I discovered a peculiar thing (not sure if is missing some CPLEX arguments).

I am experiment with a 300 by 300 Transportation Problem and using CPXcopyLP (containing all the facilities with actual capacity) and CPXchgrhs for set RHS to zero (or actual capacity).

When i change at most 3 facilities (that is, set the right hand side of the capacity constraint to zero) it is much more faster than solving/optimizing from scrach. But when the modifications are many, for example, changing 50 or 60 warehouses, it is slower than solving/optimizing from scrach.

I am using CPXchgrhs, to pass the array of size (all facilities) of righthand side coefficients to be changed or simply the the indexes of the facilities that i want to change and its value?

Exemple: 

status = CPXchgrhs (env, lp, <number of all facilities>, <array of length "all facilities" indexes of all facilities>, <array of array of length "all facilities" containing the changes (zero or (or actual capacity))>);

I think the "bug" is in the CPXchgrhs but i am not sure..

Can you help please?

Thanks :)

 

#DecisionOptimization
#MathematicalProgramming-General

Have you tried changing the RHS of the original problem (rather than working with a copy each time)?

Also, assuming you have advanced starts turned on (the default), have you tried turning it over?

 

#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: ACJ4_Telmo_Matos

What you mean by "Have you tried changing the RHS of the original problem (rather than working with a copy each time)?".

Did you mean not work with the data in the LP (data that i store with the CPXCopyLP) or destroying this data and use the CPXCopyLP again with the changes on the RHS?

Meanwhile i used use the "CPX_PARAM_ADVIND" setting it to 0 but with no effect (i am using the CPXDualOpt).

I notice that if i use the "CPX_PARAM_LPMETHOD" with argument set to "CPX_ALG_NET" it is faster but even so, solving/optimizing from scrach, is faster.

 

thanks for your time

#DecisionOptimization
#MathematicalProgramming-General

As I understand it, you load your LP once (from external data) and never change that version (call it the master copy). Instead, you make a copy at each change point and alter the RHS, then solve the copy. Assuming my understanding is correct, I am suggesting that you try loading the problem once, and at each point where you want to change facilities, directly alter the RHS of the master copy. So you would never call CPXcopylp. I'm not positive that would be faster, but it might be.

#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: ACJ4_Telmo_Matos

Well, i think that i'm doing it already. 

I start initialize global variables "env" and "lp" and then initialize the CPLEX environment with "CPXopenCPLEX". Then i create the problem with "CPXcreateprob" and copy the problem with "CPXcopylp". This is done just one time, at the beginning of the program.   

When i want to reoptimize the problem i just use the "CPXchgrhs" for the "env" and "lp" earlier created (with the changes in facilities capacity),  and then use the "CPXdualopt" to optimize.

 

#DecisionOptimization
#MathematicalProgramming-General

I guess I misunderstood what you said earlier about copylp; I thought you were making a new copy each time you changed the model.

Looking back at the original question, I'm not sure that the behavior you observe is surprising. There are certain specific circumstances where dual simplex tends to outperform primal simplex. One is when you have an optimal solution and you add one or more constraints, which makes the current solution superoptimal (but infeasible). Another, I think, is where the primal problem has significant degeneracy.

In your case, the changes you make will likely render the current basis infeasible, but the objective value could be either superoptimal, optimal or suboptimal. If you use primal simplex, CPLEX will first have to restore feasibility and then do additional pivots to reach optimality. If you use dual simplex, CPLEX will first have to restore superoptimality (if it was lost), then do additional pivots to reach feasibility. With enough changes, it is anyone's guess which requires more pivots.

If the TPs arrive all at once, possibly you could sort them so that the transition from one problem to the next would involve relatively few openings and closings. You could probably solve a quick graph problem to find a "path" through the TPs that minimized the maximum number of changes from any problem to the next. If the problems arrive sequentially, the only thing I can think of is to try CPXlpopt with CPX_PARAM_LPMETHOD set to either concurrent or, if that is no help, the default setting (let CPLEX choose).

Paul

#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: ACJ4_Telmo_Matos

Well, i suppose that changing RHS, will make CPLEX do several internal pivot operations to solve this modified TP. Despite checking for feasibility before using CPLEX, this have to do several operations to solve the new model (based on the master model), that's why i think it takes longer time than solving TP from scratch.

I wonder, if i change the objective function, say, setting a value big enough for the facilities that i want to close and keeping the constraints, do i get time efficiency?

Responding to your question  "If the TPs arrive all at once(...)", they arrive sequentially with a change on facilities that are removed form the master problem.

Thanks once again for your time..

    

#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: ACJ4_Telmo_Matos

Sorry once again, but i thing i figure it out what was my problem.

As i told you, i use the CPXcopylp to load data only once (master problem - MP) to use as many times as i want in the change of RHS (sub-problems - SP).

I was doing it wrong, because i thought that in the function CPXchgRHS, i had  to change every RHS of my problem and i discover that i only have to change the indexes wher i want to change the RHS..

I thought that i discovered the time problem, but then i discover that the function CPXchgRHS changed the MP.

I search on CPLEX documentation and i discover the CPXcloneprob to clone the problem and keeping the MP intact, but it takes too long to do this way. 

I tried to do the CPXchgRHS again after optimize the problem to "rollback" to the beginning but the time consumption is to much.

Do you have any idea to do this? The use of the CPXcopyStart or the CPXcopyBase will do the trick?

Thanks again :)

 

 

#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: TobiasAchterberg

I think that the approach you were using is the best way to go:

1. Use CPXcopylp to set up your master problem.
2. Solve the problem.
3. Modify the rhs vector using CPXchgrhs.
4. Solve the problem.
5. Goto 3.

As far as I understand, you are not satisfied with the performance of the simplex solves in 4. You need to play around with various strategies here. Here are some thoughts on this:

As you have observed it is most often the case that if you modify only a small fraction of the model in 3. that it is then the best to just let CPLEX deal with this automatically. It will continue the solve from the optimal basis of the previous solve and often find an optimal solution of the modified problem in just a few pivots.

But the downside of the automatic approach is that presolving will be disabled if a warm start basis is loaded. Thus, if you are setting many right hand sides to zero (disabling many facilities), the presolving reductions can outweigh the warm start basis advantage. Moreover, if you have many problem changes it can be that the old optimal solution is far away from the new optimal solution and thus the warm start basis is not a good starting basis. For this reason, starting from scratch (setting ADVIND to 0) can help. You can also try setting ADVIND to 2. This means that CPLEX tries to use presolving and still starting from the warm start basis, if this is possible (if this basis can be transformed through presolve into a basis of the presolved model).

Finally, when you go from one sub-problem to the next, I guess you will also relax the problem again (i.e., changing the rhs from zero back to a positive value; in other words: adding back a facility). In this case, reoptimizing from the previous warm start basis is often hard. In this case it is probably better to either start from scratch or start from the optimal basis of the original problem (solved in Step 2), which you can do using CPXcopybase.

 

#DecisionOptimization
#MathematicalProgramming-General