[Coin-discuss] Some questions on heuristic and cut writing style

[Fabrizio Ferrandi]

I need some support to develop my own code that try to solve the scheduling
    of the operations extracted from a behavioral description (High-level
    synthesis of VLSI design). In particular, this "scheduling" try to 
minimize
    the number of control steps to which assign the operations given some
    resource constraints. To solve this particular scheduling problem 
several
    heuristic approaches and also some exact approaches based on integer 
linear
    programming has been proposed. To validate the efficiency of my approach 
I
    implement also the ILP solution.
    I’ve considered several open source project but until now the most
    interesting results come from the Cbc standalone solver.
    To improve the performance of Cbc I’ve wrote some specific heuristics 
and
    I’ve also tried to define some global cuts.
    The heuristic currently developed is quite different from those provided
    with the COIN-OR distribution, since it does not use any linear solver 
but a
    different data structure. It is very fast and can exploit also some
    information provided by Cbc. In fact, if the Cbc framework fixes some
    variables then the heuristic can propose a solution that take into 
account
    such suggestion.
    Now, I suppose that a partial solution, columns fixed by presolve, or by
    standard cuts, or simply by the branch process, can be obtained using 
the
    function getColSolution provided by the OsiSolver.
    Is it true?
    Currently, I’ve some source code that correctly work when no partial
    solution is considered (the solution provided to the Cbc code has been
    validated and accepted) but problems arise when I try to use the
    getColSolution function.

    Moreover, when a solution has been found by strong branching or by my
    heuristic I can further fix the problem by setting to zero some columns. 
By
    browsing the code I see that the cut generator actually does not allow 
this
    type of operation. It allows the addition of column cuts but it seems to 
me
    that such cut are used only when constraints are violated. Actually 
fixing
    columns to zero should further reduce the number of variables used by 
the
    branch code.
    I’ve also seen that CglProbing is able to modify the matrix but this is
    based on some ad-hoc code. Do you think that the right solution to my
    problem is to mimic the CglProbing code?

    After hard debugging I’ve also seen a strange behavior. When a solution 
is
    provided by my heuristic the getColSolution function actually does not
    return it but something of different. It could be the linear relaxation 
but
    I’m not sure.
    How can I get the best solution found until now inside the generateCuts
    virtual function of the my user specified cut class?

    I hope that my questions are clear enough. In any case I can provide 
further
    details.

    Best Regards,

    Fabrizio Ferrandi

_________________________________________________________________
Express yourself instantly with MSN Messenger! Download today it's FREE! 
http://messenger.msn.click-url.com/go/onm00200471ave/direct/01/