Originally posted by: SystemAdmin

Hi,all
Please give me some suggestions about these questions bellow:
1、What's the mean of "starting vector" and "primal/dual vector"?What's the relationship between them and "starting basis"? Are they terminology of mathematics？
2、I am working on the performance improvement of solving LPs by using simplex/dual algorithm. Unfortunately, I was confused by advanced start(warm start) and preprocessing. Are they all about presolved model?
3、The problem I want to solve is very special, it is encoded from directed graph through a standard method. So most variables and constraints are redundancy. I just want to know if the problem is feasible or not . In addition, I have to modify and reoptimize the problem time and time again. e.g., add/remove a set of variables and constraints(relevant to some nodes in the graph). How can I use warm start and preprocessing in this situation?
Link: http://www.ibm.com/developerworks/forums/thread.jspa?messageID=14791641 give more information about my problem.

yang
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

1. A "starting vector" is just some primal and/or dual solution vector, which does not need to be feasible or optimal. If you provide such a vector or pair of vectors, then CPLEX tries to identify a simplex basis that is "close" to this vector. Then, it will use this basis as starting basis for the subsequent optimization.
If you provide a "starting basis" (i.e., specify the basis status of all rows and columns), then CPLEX uses this immediately as starting basis for the simplex algorithm.
So, if you have a basis at hand, it is always better to provide the basis instead of the vectors, because for converting the vectors into a basis there is some guessing done, which can be wrong.

2. If you provide a warm start basis, then presolving will be disabled in default settings because this may render your basis invalid. You can try to set the "advanced start indicator" to the value 2, which means that CPLEX would apply presolve and then try to crush your starting basis to the presolved model.

3. If you solve an LP to optimality, then modify it and reoptimize, CPLEX will try to apply the modifications to the presolved model as well. If this is possible (because your modifications are compatible to the presolve operations), then CPLEX will use the previously optimal (presolved) basis as starting basis for a subsequent optimization.

Maybe it helps to turn off dual presolve reductions and non-linear presolve reductions. This should make it more likely that your modifications stay compatible to the presolve reductions.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Hi, Tobias.

Thanks for your reply.I have tried to turn off dual presolve reductions and non-linear presolve reductions, but I got this warning:
Warning: Adding rows to the presolved model fails.
Tried aggregator 1 time.
LP Presolve eliminated 12997 rows and 5998 columns.
Aggregator did 1 substitutions.
Reduced LP has 0 rows, 13 columns, and 0 nonzeros.
Presolve time = 0.00 sec.
Using devex.
computation time：45.614 (cplex.getCplexTime())
what's the warning means?
Why the compution time is 45.614 while the presolve time is 0?
When I turn on primal presolving and warm start, the computation time almost have no change compared with solving the modified problem directly.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

The warning message says that CPLEX was not able to crush the new row that you added. Therefore,it had to discard the presolved model.
This will certainly happen in default settings (where dual reductions are allowed), but it can also happen if you disable dual presolve reductions, for example if the presolved model was empty (the previous model was trivially solved by presolve), or if the new row contains variables that have been aggregated out by presolve.

You are using the cplex.getCplexTime() method in a wrong way. Note that this does not return the time needed for the previous method call. Instead, it just returns a time stamp. So, you always need to query it before and after the solve() call and then take the difference. Note what the documentation says:

public IloNum getCplexTime() const
 
This method returns a time stamp.
 
To measure elapsed time in seconds between a starting point and ending point of an operation, take the time stamp at the starting point; take the time stamp at the ending point; subtract the starting time stamp from the ending time stamp.
 
This computation measures either wall clock time (also known as real time) or CPU time, depending on the parameter ClockType.
 
The absolute value of the time stamp is not meaningful.

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thank you,Tobias.
yeah,it is my fault. I didn't check the documents carefully.

But the result is still confused :

Warning: Adding rows to the presolved model fails.
Tried aggregator 1 time.
LP Presolve eliminated 12997 rows and 5998 columns.
Aggregator did 1 substitutions.
Reduced LP has 0 rows, 13 columns, and 0 nonzeros.
Presolve time =    0.02 sec.
Using devex.
computation time：0.030999999999998806

As you can see,the compution time is 0.030999999999998806 while the presolve time is 0.02. Why the computation time not equals to the presolve time?

You said the warning message can happen if the presolved model was empty (the previous model was trivially solved by presolve), or if the new row contains variables that have been aggregated out by presolve(Does this means adding new variables have the same effect?). Unfortunately. it seems both of them happened. Then is there any thing I can do to improve the performance？
#CPLEXOptimizers
#DecisionOptimization