[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] is it possible to determine the value a nb variable will

From: Selçuk Cihan
Subject: Re: [Help-glpk] is it possible to determine the value a nb variable will take?
Date: Mon, 29 Dec 2008 16:52:59 +0200

Thanks for the response,

> In glplpx08.c (of GLPK 4.34) you can find function lpx_print_sens_bnds()
> which is used to print a sensitivity report (called for parameter --bounds
> of glpsol).
> It calculates amounts by which variable bounds may be changed in the
> original problem while the optimal basis remains the same.

i am working with suboptimal solutions, lpx_print_sens_bnds() is of no
use for me i guess, it just tells me that i do not have an optimal

i am not sure if i made myself clear, due most probably to my lack of
experience in linear programming. what i need is, to be able to
implement my own iterative algorithm, for solving a 0-1 integer
program. The iterations will start from the optimal solution of the LP
relaxation of the 0-1 integer program. At each iteration i will select
a nonbasic variable and make it enter to the basis. That is called a

Currently, i have everything in place for the iteration mechanism to
work. However the move i choose at each iteration is not a clever
move, it is random. I want to make it a clever choice. By being
clever, i mean, i need some measure of how good the current solution
is. The measure i chose includes two factors, integer infeasibility
and objective value. So, basically, i need to be able to tell by how
much the objective would change if i make a certain move, and by how
much the actual variables would change(to be able to compute integer
feasibility, which stands for the difference between a variable and
the integer closest to that variable). I need to be able to obtain
that knowledge without actually carrying out that move. So that after
evaluating each possible move, i will choose the move with most
benefit and apply it.

Following piece of code carries on a move
void TS::makeMove(Move p_move, int p_iter, int dummy) /* default value
for dummy == 0 */
        if(p_move.b <= m_m) /* aux. var. to leave basis */
                glp_set_row_stat(m_pMip, p_move.b, GLP_NL);
        else /* structural var. to leave basis */
                if(dummy == 0) /* i have no clue if we need to use GLP_NU or 
                        glp_set_col_stat(m_pMip, p_move.b - m_m, GLP_NU);
                else /* if we get an infeasible sln using GLP_NU, we'll switch 
GLP_NL by calling this function again */
                        glp_set_col_stat(m_pMip, p_move.b - m_m, GLP_NL);
        if(p_move.nb <= m_m) /* aux. var. to enter basis */
                glp_set_row_stat(m_pMip, p_move.nb, GLP_BS);
        else /* structural var. to enter basis */
                glp_set_col_stat(m_pMip, p_move.nb - m_m, GLP_BS);

        int retVal = lpx_warm_up(m_pMip);
        assert(retVal == LPX_E_OK);
        if(glp_get_status(m_pMip) == GLP_INFEAS)
                makeMove(p_move, p_iter, 1);

where p_move is a structure with fields:
b => denotes index of a currently basic variable, which will leave the basis
nb => denotes index of a currently nonbasic variable, which enters the
basis after execution of above code

thanks in advance for any suggestions

reply via email to

[Prev in Thread] Current Thread [Next in Thread]