[Coin-symphony] Fix the variables

[Ted Ralphs]

I'm still not perfectly clear on how you're planning to generate columns
based on this kind of dual information. At best, this would give you a
heuristic procedure, since a linear dual function is not going to be
strong for an IP in general. Also, if you are generating cutting planes,
it is not clear how the dual values of these cuts should be handled when
doing the column generation.

That said, yes, I think you can do the same with SYMPHONY/CLP. There are
a number of different possibilities depending on how sophisticated you
want to get. The easiest/quickest thing to do would be just to dump an
MPS file of the current LP relaxation using the write_mps() function
(see lp_solver.c) whenever an integer solution is found, along with the
solution itself. This file could then be read back into the solver at
the end of the solution process to generate the appropriate dual values.
Alternatively, you could just clone the OsiClpSolverInterface object
(the pointer is stored in lp_data->si), fix the variables there, solve
the resulting LP, and dump the dual solution. The easiest place to do
this would be is in the user callback user_is_feasible() (or its wrapper
function is_feasible_u()), which is called very time SYMPHONY checks the
integer feasibility of a solution. Any static data could be saved in the
user data structure passed to this function.

I hope this is clear. Please let me know if you need any more info. Good
luck!

Cheers,

Ted

Yossiri Adulyasak wrote:
> Hi Ted,
> 
> Thanks for your reply.  You understood correctly.  In essence, we try to
> use column generation to solve an IP without using
> Branch-and-Price.  That is, we generate columns outside of B&B tree.  
> 
> Here's an outline of our column generation algorithm:
> 1. Formulate a Restricted Master Problem (RMP) with subset of columns
> from the original problem.
> 2. Solve the above RMP in B&B to IP optimal.  
> 3. Use the optimal IP solution, to price and generate columns.
> 4. Solve the RMP + additional columns generated in B&B to optimality.
> 5. Repeat 3 and 4, until no more columns are generated.
> 
> Now, in Step 3, we need dual information to price the columns.  And I
> guess here's where I confused you.  I used to work with CPLEX; in CPLEX
> it allows users to obtain dual info of the optimal IP solution (or more
> correctly, of the LP relaxation solution at the optimal B&B node) by
> changing the problem type from IP to LP-fixed, in which, all variables
> are fixed at the IP solution.  I think what CPLEX does (to fix those
> variables) is to solve LP relaxation with the conditions at that B&B
> node to reproduce the integer solution and hence dual info.  That is, it
> does not literally fix the variables.  (So, I confused you when I said
> we tried to fix the variables.)  
> 
> So, the question is, can we do the same thing with SYMPHONY/CLP?
> 
> Many thanks for your help.  I appreciate you time and help.
> 
> Cheers,
> 
>  
> 
>     --
>     -Yossiri Adulyasak-
>     Graduate Student
>     Transportation engineering Program
>     Department of Civil Engineering
>     Chulalongkorn University
>     Thailand
> 
>     a.yossiri -at- gmail.com <http://gmail.com> 
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> Coin-symphony mailing list
> Coin-symphony at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-symphony


-- 
Dr. Ted Ralphs
Assistant Professor
Industrial and Systems Engineering
Lehigh University
(610)758-4784
tkralphs at lehigh.edu
www.lehigh.edu/~tkr2