Originally posted by: Ho_Thanh

Dear all,

I am using ILOG CPLEX (Concert, Library) for my research. I am writing my algorithm by C++ in Visual Studio 2010 with CPLEX 12.6. 

In my algorithm, I have to solve some consecutive linear programs (LP) that satisfy a particular property as follows.

Assume that the first linear program (1) takes the standard form 

min <c,x>

s.t. Ax <= b 

and 0 <= x

where x \in R^n, A \in M_{m x n}, b \in R^m, c \in R^n,

and by the basic function of CPLEX for LP, I easily get x0, the solution of (1) .

Then, the next linear program (2) is obtained by adding (1) a new real variable x_{n+1} and a new constraint  as follows.

(2): min <c,x> + g x_{n+1}

s.t. Ax <= b

and <d,x> + e x_{n+1} <= f

and 0 <= x, 0 <= x_{n+1}.

where e,g,f  \in R, d \in R^n.

It is similar to the next linear programs in my algorithm.

When n and the number of linear problems are large , by independently applying CPLEX for solving each LP as (1), my algorithm spends a lot of time. 

My problem is how to apply CPLEX to solve the linear program (2) as well as the next linear programs fast? Specially, based on the previous solution x0? or the information of previous problems?

 

Please help me this problem. 

Thank you so much.

Best regards

HO Thanh

 

 

#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: RWunderling

I assume you are solving your LP with the Simplex algorithm and end up with an optimal basis.  Then the question is how to extend the optimal basis as to be ensure that the extended basis to the extended problem is primal or dual feasible.  In this case, you can hot start the (primal or dual) Simplex algorithm from the previous optimal basis.

Extending to a primal or dual feasible basis when adding both, variables and constraints at the same time is generally not possible.  However, the structure of the extension you present could allow you to do so, provided that g>=0.  In this case setting the basis status of the new constraint to non-basic and of the new variable x_{n+1} to basic should do the trick.  Use CPXXcopybase() to install the so extended basis.
If this does not work (because g< 0), you can still do a two step extension:  First only add the constraint, in which case CPLEX will automatically extend the basis to a dual feasible one from which you can hot start.  After having solved this model to optimality, also add the variable in which case CPLEX will automatically extend the basis to a primal feasible one from which you can again hot start.

Roland

#DecisionOptimization
#MathematicalProgramming-General