Originally posted by: RobertoSteri

Hello,

I am trying to implement a warm start by specifiying the initial vector x using the Cplex class in Matlab. I am solving an LP, and I am using CPLEX Studio - Academic Research Edition v. 12.2.

I specify the initial condition (I set it equal to the solution for debug purposes) as follows:

cplex = Cplex('LP_VF');
cplex.Model.sense='minimize';
cplex.addCols(ones(nk*nxz,1), [], ones(nk*nxz,1)*-inf, ones(nk*nxz,1)*inf);
cplex.addRows(b, A, ones(nk*nkpr*nxz,1)*inf);
cplex.Start.x=init;
cplex.solve();

However, the initial condition doesn't seem to affect the execution time at all. On the contrary, when I do the same using the Matlab toolbox, i.e.

out=cplexlp(ones(nk*nxz,1),-A,-b,],[,init);

the execution time decreases dramatically (i.e. the warm start works).

Is this a bug? How can I implement the warm start using the Cplex class?

Thanks!
Roberto
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: RobertoSteri

Additional info: I updated my version to 12.3 but the problem persists.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Your second code example was mangled by the Forum software. You should include source code into { code } tags. Can you confirm that your code is

out=cplexlp(ones(nk*nxz,1),-A,-b,[],[],[],[],init);

i.e., that 'init' is the 8th element to the function call? In your example it looked it was the 6th argument, in which case you would have specified lower bounds instead of an initial vector.
Could you also show us the output of the two runs? Maybe also export the two problems to an LP file and double check that they are indeed the same.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: RobertoSteri

Hello Daniel,

thank you for your reply. It seems that I actually specified a lower bound (6th argument) instead of the initial point. The problems are the same (it's the same Matlab file as the code below shows). For some reason (perhaps related to the properties of my problem), the solution is the same but much faster if I specify a lower bound.

The only oddity is that when I (now) correctly set the initial point equal to the solution, the execution time doesn't decrease at all with respect to the case in which I don't specify the initial point. In other words, the results from the API and the Toolbox are now consistent, but in both cases setting x0 = solution has no effect at all on speed.

Is this possible?

{
elseif 0

%Cplex API
cplex = Cplex('LP_VF');
cplex.Model.sense='minimize';
cplex.addCols(ones(nk*nxz,1), [], ones(nk*nxz,1)*-inf, ones(nk*nxz,1)*inf);
cplex.addRows(b, A, ones(nk*nkpr*nxz,1)*inf);
cplex.Start.x = init;
cplex.solve();
out=cplex.Solution.x;

elseif 1

%Matlab toolbox
out=cplexlp(ones(nk*nxz,1),-A,-b,],[,ones(nk*nxz,1)*-inf,ones(nk*nxz,1)*inf,init);

end
}
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: John Cui

Could you please attach your code here? including your input data, then I can try your code on my machine.

John Cui
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: RobertoSteri

Dear John,

thanks a lot! Attached you can find my code and the input files you need to run that. I put comments so that you can quickly see what's going on.

Best,
Roberto

p.s. I attach the code here and the input files in the next messages
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: RobertoSteri

Input file #1
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: RobertoSteri

Here's the first input file
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: RobertoSteri

Here's the second input file
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: John Cui

Unable to read file LP_Input: No such file or directory.

Did you attached LP_Input file？

John
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: RobertoSteri

I'm sorry, I thought it was in the first .rar file but it wasn't. Here it is, thank you again!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: John Cui

I tried both Cplex class and cplexlp, x vector is useless in both cases.

In CPLEX to solve LP, only provide x vector as start is not always useful to improve performance, the better way to provide start to LP is to provide basis to your problem.
For example, after you solved your LP in Cplex class, you need to save cplex.Start.basis in MATLAB, then use this basis to a new cplex object.

...% build cplex
cplex.solve
basis = cplex.Start.basis
...% build cplex1
cplex1.Start.basis = basis
cplex1.solve

John
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: RobertoSteri

Thank you John!

Actually, another option that seems to work is to specify the dual in cplex.Start.dual along with the vector x. However, one should make sure that the solution method is not the barrier algorithm - otherwise this type initialization is useless.

Roberto
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: John Cui

Yes, you are right.

John
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: RWunderling

Just a few points of (hopefully) clarification:

1. The Simplex algorithm operates on a basis as it's main data type.
Thus specifying a basis is the only way to provide a well defined starting
point to simplex.
2. CPLEX has code that tries to guess a basis given a set of starting
vectors. The theory actually provides a uniquely defined basis if you
provide consistent primal and dual vectors. Unfortunately, numerics
get in the way of theory here, and the computation of a basis from an
optimal set of primal and dual vectors is not perfect. Still providing
both, the primal and the dual vector is the second best way of providing
a starting point for the Simplex algorithm
3. If only one of the vectors (e.g. only the primal) is provided, there
is no more theory that one could rely on to define a good starting basis.
In fact one can prove that for a given starting vector you could define
a potentially large family of simplex bases that are all consistent with
the starting vector. Which one CPLEX then ends up picking is more or less
random. As a consequence, specifying only one starting vector is a very
weak way of provinding a starting point for Simplex. This issue gets worse
the more degenerate your problem is.

Hope this helps,

Roland
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

hi, RWunderling

I have some questions about your clarification:
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