Originally posted by: StephK

Hi,

I program  with C++ language and I use CPLEX  CONCERT.  I'm interesting to know  what is the command to save optimal basis for an LP problem and to initialize an  LP problem with a basis previously saved.  I don't want to use the readBasis/writeBasis methods of IloCplex. These methods read and write  basis from/into a file.  I know that in java getBasis method  exists but not in C++ ?

 

Thank you very much,

Stephane

#CPLEXOptimizers
#DecisionOptimization

The following member functions of class IloCplex should help you so warmstart LP solves:

• setBasisStatuses()
• getBasisStatuses()
• setStart()

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: StephK

Should I use getBasisStatuses()/setBasisStatuses  for each of all IloNumVarArray in my LP ?

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: T_O

I am not an expert in Concert, but if you want to save the complete basis, you have to obtain the basis status from every variable AND every constraint.

Best regards,
Thomas

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: StephK

 

If I use this method:

setStart (const IloNumArray x, const IloNumArray dj, const IloIntVarArray var, const IloNumArray slack, const IloNumArray pi, const IloRangeArray rng)

I need to pass an  IloNumArray  (x)  that corresponds to all variables in the PL.  Variables in my program are : IloNumVarArray (x), IloNumVarArray(y), IloNumVarArray(z), IlonNumvar t

Should I use setStart for each of all these variables ?  Same question for constraints. Do you have example using setStart ?

Thank you

 

 

 

 

#CPLEXOptimizers
#DecisionOptimization

The iloadmipex6.cpp example uses setStart() in a solve callback.

In order to set values for all your arrays x, y, z you need to concatenate them into one flat array:

IloNumVarArray vars(env);
IloNumArray vals(env);
for (IloInt i = 0; i < x.getSize(); ++i) {
   vars.add(x[i]);
   vals.add(xval[i]);
}
for (IloInt i = 0; i < y.getSize(); ++i) {
   vars.add(y[i]);
   vals.add(yval[i]);
}
...
cplex.setStart(vars, vals, ...);
vars.end();
vals.end();

And the similarly for constraints.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: TOYSED

Hello,

 

When using setStart do we only need to add variables and values of these variables? 

I only add these two add parameters and the warning I receive is that no overloaded function takes two arguments...

When I look at the iloadmipex6, I only see these two, together with some zeros. But it also gives warning...

What should I do? Thanks...

 

ILOSOLVECALLBACK3(UserSolve, IloNumVarArray, vars,
                             IloNumArray, x,
                             IloBool, done) {
   if ( !done ) {
      setStart(x, vars, 0, 0);
      solve(IloCplex::Primal);
      if ( getStatus() == IloAlgorithm::Optimal ) useSolution();
      done = IloTrue;
   }
}

 

#CPLEXOptimizers
#DecisionOptimization

For question like this you should take a look at the reference documentation here. It tells you that there are 2 overloads (one for IloNumVar one for IloIntVar) for method setStart():

void setStart(const IloNumArray x, const IloIntVarArray var, const IloNumArray pi, const IloRangeArray rng)
void setStart(const IloNumArray x, const IloNumVarArray var, const IloNumArray pi, const IloRangeArray rng)
 

So you have to pass 4 arguments. Passing 0 as argument should be fine since it makes the C++ compiler generate a call to the array constructor that creates an empty array. What warning do you get?

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: TOYSED

When I add zeros it says ;

 

IloCplex::setStart no overloaded function takes 4 arguments.

 

no instance of overloaded function matches the argument list (IloNumArray, IloNumVarArray, int, int)

 

#CPLEXOptimizers
#DecisionOptimization

Like I said: Please take a look at the reference documentation!

In your original post you showed us code that called IloCplex::SolveCallbackI::setStart(). This function takes 4 arguments. Now you are calling a completely different function? According to your most recent post you are now calling IloCplex::setStart(). Since that is a different function it takes a different number of arguments. Please check the reference documentation here. Maybe it is not intended to call IloCplex::setStart() instead of IloCplex::SolveCallbackI::setStart(). Then you need to fix your code.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: TOYSED

 

OK. Let me ask the question again. I am working on Column Generation and want to save the last basis so that I can start from the last feasible solution every time I add a column.

If I am not wrong this is called warm start and the correct example for this operation  is in iloadmipex6. But when I look this example I can not figure out how to implement it.

Do I need SolveCallBack, setStart or both?

#CPLEXOptimizers
#DecisionOptimization

First of all, you probably don't need to do anything. If you just add a new column and then use primal simplex then CPLEX should be able to start from the previous basis automatically (since that basis is still primal feasible).

Since a SolveCallback is invoked during tree search and adding columns is not something you can do during tree search, I am almost certain that a SolveCallback is the wrong thing to do here. You have to use IloCplex::setStart() to install a starting basis. All values you need for this can be obtained by appropriate getters in the IloCplex class.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Nishit_Bhavsar

Hello,

I want to use initial solution to warm start LP. I am using Cplex concert technology (C++ API)

I have tried using setBasisStatuses() and getBasisStatuses(). But it shows syntax error. I want to understand how these parameter work/get implemented.

I have understood as follows: (Please correct me wherever I am wrong)

• First define 'BasisStatusArray'

           IloCplex::BasisStatusArray cstat(env), rstat(env);             // where cstat is for variable and rstat is for constraint

• Then add solution value that we want to assign to cstat using 'cstat.add(        )'. Please correct me if it is not this way. I am unable assign the (initial) solution value to the cstat. Please help me know how to do this.
• Then we can set this value to the variable using setBasisStatuses(cstat,vars, rstat,rng).

 Please note that I have two variables, one with single index other with three index.

Also, what if I don't want to set constraint at any initial value. Please help me know how to use setBasisStatuses().

Please let me know if anything further required for you to respond this.

Thanks

Nishit

#CPLEXOptimizers
#DecisionOptimization

If you get 'syntax error' then something is wrong in your C++ code. This is unrelated to CPLEX since your code is not even syntactically correct. If you want us to help you with this you would have to show us more code and also tell us where exactly the compiler complains about syntax errors.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Nishit_Bhavsar

Thank you for your reply! 

Sorry! I did not mention precisely. I meant while I write  line -   cstat.add( ) in my code, It shows error like 'too few argument in function call'.  So, I don't know the syntax of how to assign initial value to the cstat.

Can you please help me know how setBasisStatus(), getBasisStatus() and cstat.add() can be implemented to warm start LP, using an example of one dimensional variable. I don't have knowledge of using these parameter.

My code works fine when I don't include these parameters (setBasisStatus(), getBasisStatus() and cstat.add()).

#CPLEXOptimizers
#DecisionOptimization

Uhm, calling add() without any argument makes no sense. You have to supply what you want to add to this array. Maybe take a look at the reference documentation here.

Also, did you look at example ilolpex6.cpp that is shipped with CPLEX? It does exactly what you want: populate cstat and rstat and then set it as warmstart.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Nishit_Bhavsar

yes, I have looked at ilolpex6.cpp.  I have some questions pertain to it. See below a part of code ilolpex6.cpp.

IloCplex::BasisStatusArray cstat(env), rstat(env);
cstat.add(IloCplex::AtUpper);
cstat.add(IloCplex::Basic);
cstat.add(IloCplex::Basic);
rstat.add(IloCplex::AtLower);
rstat.add(IloCplex::AtLower);
cplex.setBasisStatuses(cstat, var, rstat, rng);

I understand that, through cstat.add() command,  varibales x1, x2 and x3 are assigned at AtUpper, Basic and Basic respectively. And then cplex.setBasisStatuses() copies these value to 'var'  to warm start.

In my case, I have obtained initial solution to assign them to variables for a warm start. How can I add/assign those solution value to cstat ? Please help me know syntax for that.

#CPLEXOptimizers
#DecisionOptimization

You should really take a look at the reference documentation and/or the examples shipped with CPLEX. ilolpex2.cpp shows how to obtain the basis statuses for an optimal solution.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Nishit_Bhavsar

Hello,

I have now implemented getBasisStatuses() and setBasisStatuses();

solution values for a variable that I want to use (for warm start) is as below:

[1, 0, 1, 0, 0, 0.452509, 0.365079, 0.608053, 0, 0]. 

I populate cstat and rstat using:  cplex.getBasisStatuses(cstat,vars, rstat, rng); 

And then assigned them for warmstart using: cplex.setBasisStatuses(cstat,vars, rstat,rng);

But when I print cstat, it prints like below:

[Basic, AtLower, AtUpper, AtLower, AtLower, Basic, Basic, Basic, AtLower, AtLower]

rstat values are also printed as AtLower and Basic

I am wondering whether cstat and rstat have been populated correctly. How can I ensure that the exactly same values(That I want) have been assigned for warm start?

#CPLEXOptimizers
#DecisionOptimization

I am not clear what your problem is. Is the problem that the cstat/rstat arrays contain basis statuses instead of numbers?

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Nishit_Bhavsar

Yes!  I understand that  cstat array should contain numbers (values) that I want to assign to warm start my LP.

#CPLEXOptimizers
#DecisionOptimization

As indicated by their type and name (and by the reference documentation), the cstat and rstat arrays take basis status values. If you want to start from a vector of values then you have to use the setStart() function.

Note however that it is usually more efficient to start from a basis rather than a vector: simplex needs a basis and if you only provide a value vector then simplex has to construct a basis first. If you instead provide a basis (via cstat and rstat) then it may directly start from that.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Nishit_Bhavsar

Does it mean that there is no role of values in LP warm start and it only concerns with status of the basis?

Also, How can we check the benefit of warm start? Can we only through time performance improvement, if observed?

 

#CPLEXOptimizers
#DecisionOptimization

Like I said, you can start from a vector of values. But then the first thing the simplex algorithm has to do is to create a basis from that vector. So if you already have a basis it should be faster to supply just that. If you don't have a basis but have the vector of values then CPLEX can start from that as well.

You can check the benefit of warm start by checking the elapsed time, the elapsed number of deterministic ticks and/or the number of iterations required to solve to optimality.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Nishit_Bhavsar

Thank you Daniel!

I just want you to elaborate that what do you mean by "create a basis from the vector of value"?

This might seem you a silly question but it may help me to avoid any confusion about term 'Basis' between what you wish to convey and what  I am understanding.

#CPLEXOptimizers
#DecisionOptimization

How familiar are you with the simplex algorithm?

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Nishit_Bhavsar

Simplex algorithm basically evaluates corner points (of polytope) at every iteration in a direction that leads to optimal solution. It is used to solve Linear Programming Problem. The set of Basic Variables is often referred to as the Basis. Basic Variables are the ones that are not set to zero in a simplex iteration.

I wanted to know what it implicitly does when it construct a basis from the vector value? I mean does it bifurcate basic and non-basic variables based on vector value? Does it do anything more?

Please feel free to avoid the question if you think it is too specific or irrelevant.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: BoJensen

I wanted to know what it implicitly does when it construct a basis from the vector value? I mean does it bifurcate basic and non-basic variables based on vector value? Does it do anything more? 

 

First of all I will recommend you to read a book on simplex, which describes the concept of a basis, basic solutions and degeneracy. But let me give you some pointers to get started.

 

Assume we have an LP problem :

 

min c x

s.t

A x = b

l <= x <= u

 

were m and n are respectively the row and column dimensions.

 

A basis is a partition of the variables into three sets :

• m basic variables, were the m x m sub matrix B is non singular (columns are linear independent, hence inv(B) exists) .
• Non basic variables on lower bound x_j = l_j.
• Non basic variables on upper bound x_j = u_j.

A basic solution can then be calculated as :

 

x_B = B^-1 (b-N x_N)

 

were X_N are non basic variables either on lower or upper bound and N is their sub matrix of A. We then get the basic solution :

 

(x_B, x_L, x_U)

 

which is defined by the basis.

 

When you set the cstat and rstat arrays, you input a basis to cplex. If the basis is non singular and of full rank, then the corresponding basic solution will be calculated as explained above.

 

Now if you only input a basic solution (i.e the calculated values) and not the basis partition, then cplex has to guess which variables are in the basis. Often an LP is degenerated, hence multiple basis correspond to the same basic solution. Searching for a non singular basis often means more work, but further more it might mess up the dual solution (assuming primal simplex is used). Even multiple primal basic solution exists, with the same primal basic solution, then these solutions may have completely different corresponding dual solution. This means one solution could be "better" than the other and simplex takes more time to find the optimal solution.

 

So I recommend that if you have a basis (cstat and rstat arrays), then feed them to cplex instead of only feeding the numerical values.

 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: sjayaswal

Dear Daniel,

 

I have a related query.

I am trying to implement a Column Generation Method for a problem.

After adding a column, I would like to solve the Master problem (which is an LP) starting from the optimal basis of the previous master problem (i.e., the problem before adding the column.

What is the way to do that?

 

Regards,

Sachin

#CPLEXOptimizers
#DecisionOptimization

Adding a variable means that you can easily extend the optimal primal basis of the previous solve to a primal feasible basis of the modified problem. With that basis you can then warmstart the primal simplex algorithm.

Note that by default CPLEX should do this automatically provided you use primal simplex to (re)optimize the modified problem.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Nishit_Bhavsar

Dear Danial,

I am too working on a Column Generation problem (which is an LP) and, after adding a column (variable), I want to solve the Master problem (which is an LP) starting from the optimal basis of the previous solve. I am using Primal-Simplex to (re)optimize the modified problem to use optimal primal basis of the previous solve. I would admit that number of simplex (Primal) iterations has reduced compared to dual-simplex iterations.  Still, the modified problem takes many simplex (primal) iterations to be solved. Ideally, it should be solved in one simplex (primal) iteration, if optimal basis of previous solve is being used.

Further, I observed that, while solving modified problem, objective value obtained in the first primal simplex iteration (see second red box of the attached image) is not same as the (objective) value obtained in the previous solve (see first red box).  For Example, as in attached image (Q1.png), I obtained objective value of 20909.3 (please see first Red Box) after solving first Column Generation iteration. However, objective value obtained in the first primal-simplex iteration of second column generation iteration is 470 (please see second Red Box). I understand it should start with 20909.3, if the optimal basis of the previous solve is being used in the modified problem.

Regards,

Nishit

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: BoJensen

I don't see why the simplex algorithm should only take one iteration if you add an extra variable. Yes, it should pick this new variable as entering in the first iteration, but other variables may become pivot candidates after this basis exchange.

 

Looking at your screen dump, something is clearly not right. My first bet is your solution is not input correct and cplex solves without a initial solution in every run. Could you please if possible attach a .sav file written just be for the call to the optimizer in each round.  You can also send it to me bo.jensen (at) dk.ibm.com.
 

 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Nishit_Bhavsar

Hello BoJensen,

I have sent .sav files generated at each Column Generation iteration (i.e for each modified problem) for a particular instance to your given email ID.

Can you please look at them to see if there is a way to use optimal basis in my problem?

Thanks and Regards,

Nishit Bhavsar

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: BoJensen

I have looked at the sav files and they don't contain a stored solution, hence I think something is wrong with the way you input the solution. Further more I can see from the problems stats that you add both rows and columns, this is from a technical point of view fine, but there's no guarantee it will start feasible with simplex. 

 

I will resolve these issues with you over email instead.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: BoJensen

This was resolved over email communication. In every loop a new IloCplex was created and the solution was copied to another instance running out of scope. The user changed work flow and CPLEX restarts then worked automatically as it should.

#CPLEXOptimizers
#DecisionOptimization