glpipp01.c

来自「著名的大规模线性规划求解器源码GLPK.C语言版本,可以修剪.内有详细帮助文档.」· C语言 代码 · 共 806 行 · 第 1/2 页

/* glpipp01.c */

/***********************************************************************
*  This code is part of GLPK (GNU Linear Programming Kit).
*
*  Copyright (C) 2000,01,02,03,04,05,06,07,08,2009 Andrew Makhorin,
*  Department for Applied Informatics, Moscow Aviation Institute,
*  Moscow, Russia. All rights reserved. E-mail: <[e-mail]>.
*
*  GLPK is free software: you can redistribute it and/or modify it
*  under the terms of the GNU General Public License as published by
*  the Free Software Foundation, either version 3 of the License, or
*  (at your option) any later version.
*
*  GLPK is distributed in the hope that it will be useful, but WITHOUT
*  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
*  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
*  License for more details.
*
*  You should have received a copy of the GNU General Public License
*  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
***********************************************************************/

#include "glpipp.h"
#define dmp_create_poolx(size) dmp_create_pool()
#define dmp_get_atomv dmp_get_atom

/*----------------------------------------------------------------------
-- ipp_create_wksp - create MIP presolver workspace.
--
-- SYNOPSIS
--
-- #include "glpipp.h"
-- IPP *ipp_create_wksp(void);
--
-- DESCRIPTION
--
-- The routine ipp_create_wksp creates an empty workspace used by the
-- MIP presolver routines.
--
-- RETURNS
--
-- The routine returns a pointer to the MIP workspace created. */

IPP *ipp_create_wksp(void)
{     IPP *ipp;
      ipp = xmalloc(sizeof(IPP));
      ipp->orig_m = 0;
      ipp->orig_n = 0;
      ipp->orig_nnz = 0;
      ipp->orig_dir = LPX_MIN;
      ipp->ncols = 0;
      ipp->row_pool = dmp_create_poolx(sizeof(IPPROW));
      ipp->col_pool = dmp_create_poolx(sizeof(IPPCOL));
      ipp->aij_pool = dmp_create_poolx(sizeof(IPPAIJ));
      ipp->row_ptr = NULL;
      ipp->col_ptr = NULL;
      ipp->row_que = NULL;
      ipp->col_que = NULL;
      ipp->c0 = 0.0;
      ipp->tqe_pool = dmp_create_poolx(0);
      ipp->tqe_list = NULL;
      ipp->col_stat = NULL;
      ipp->col_mipx = NULL;
      return ipp;
}

/*----------------------------------------------------------------------
-- ipp_add_row - add new row to the transformed problem.
--
-- SYNOPSIS
--
-- #include "glpipp.h"
-- IPPROW *ipp_add_row(IPP *ipp, double lb, double ub);
--
-- DESCRIPTION
--
-- The routine ipp_add_row adds a new empty row to the transformed
-- problem.
--
-- The parameter lb is an lower bound of the new row (-DBL_MAX means
-- the row has no lower bound).
--
-- The parameter ub is an upper bound of the new row (+DBL_MAX means
-- the row has no upper bound).
--
-- RETURNS
--
-- The routine returns a pointer to the created row. */

IPPROW *ipp_add_row(IPP *ipp, double lb, double ub)
{     IPPROW *row;
      /* perform sanity checks */
      xassert(lb <= ub);
      /* create new row */
      row = dmp_get_atom(ipp->row_pool, sizeof(IPPROW));
      row->lb = lb;
      row->ub = ub;
      row->ptr = NULL;
      row->temp = 0;
      row->prev = NULL;
      row->next = ipp->row_ptr;
      row->q_flag = 0;
      row->q_prev = NULL;
      row->q_next = NULL;
      /* add the row to the linked list of rows */
      if (row->next != NULL) row->next->prev = row;
      ipp->row_ptr = row;
      return row;
}

/*----------------------------------------------------------------------
-- ipp_add_col - add new column to the transformed problem.
--
-- SYNOPSIS
--
-- #include "glpipp.h"
-- IPPCOL *ipp_add_col(IPP *ipp, int i_flag, double lb, double ub,
--    double c);
--
-- DESCRIPTION
--
-- The routine ipp_add_col adds a new empty column to the transformed
-- problem.
--
-- The parameter i_flag is a column integrality flag. If it is set, the
-- new column is integer, otherwise the new column is continuous.
--
-- The parameter lb is an lower bound of the new column (-DBL_MAX means
-- the column has no lower bound).
--
-- The parameter ub is an upper bound of the new column (+DBL_MAX means
-- the column has no upper bound).
--
-- The parameter c is an objective coefficient at the new column.
--
-- RETURNS
--
-- The routine returns a pointer to the created column. */

IPPCOL *ipp_add_col(IPP *ipp, int i_flag, double lb, double ub,
      double c)
{     IPPCOL *col;
      /* perform sanity checks */
      xassert(lb <= ub);
      if (i_flag)
      {  if (lb != -DBL_MAX) xassert(lb == floor(lb));
         if (ub != +DBL_MAX) xassert(ub == floor(ub));
      }
      /* create new column */
      col = dmp_get_atom(ipp->col_pool, sizeof(IPPCOL));
      col->j = ++(ipp->ncols);
      col->i_flag = i_flag;
      col->lb = lb;
      col->ub = ub;
      col->c = c;
      col->ptr = NULL;
      col->temp = 0;
      col->prev = NULL;
      col->next = ipp->col_ptr;
      col->q_flag = 0;
      col->q_prev = NULL;
      col->q_next = NULL;
      /* add the column to the linked list of columns */
      if (col->next != NULL) col->next->prev = col;
      ipp->col_ptr = col;
      return col;
}

/*----------------------------------------------------------------------
-- ipp_add_aij - add new element to the constraint matrix.
--
-- SYNOPSIS
--
-- #include "glpipp.h"
-- IPPAIJ *ipp_add_aij(IPP *ipp, IPPROW *row, IPPCOL *col, double val);
--
-- DESCRIPTION
--
-- The routine ipp_add_aij adds a new element to the constraint matrix
-- of the transformed problem.
--
-- The parameter row is a pointer to a row, in which the new element
-- should be placed.
--
-- The parameter col is a pointer to a column, in which the new element
-- should be placed.
--
-- The parameter val is a numeric value of the new element.
--
-- RETURNS
--
-- The routine returns a pointer to the created element. */

IPPAIJ *ipp_add_aij(IPP *ipp, IPPROW *row, IPPCOL *col, double val)
{     IPPAIJ *aij;
      xassert(val != 0.0);
      aij = dmp_get_atom(ipp->aij_pool, sizeof(IPPAIJ));
      aij->row = row;
      aij->col = col;
      aij->val = val;
      aij->r_prev = NULL;
      aij->r_next = row->ptr;
      aij->c_prev = NULL;
      aij->c_next = col->ptr;
      if (row->ptr != NULL) row->ptr->r_prev = aij;
      if (col->ptr != NULL) col->ptr->c_prev = aij;
      row->ptr = col->ptr = aij;
      return aij;
}

/*----------------------------------------------------------------------
-- ipp_remove_row - remove row from the transformed problem.
--
-- SYNOPSIS
--
-- #include "glpipp.h"
-- void ipp_remove_row(IPP *ipp, IPPROW *row);
--
-- DESCRIPTION
--
-- The routine ipp_remove_row removes a row, which the parameter row
-- points to, from the transformed problem. */

void ipp_remove_row(IPP *ipp, IPPROW *row)
{     IPPAIJ *aij;
      /* remove the row from the active queue */
      ipp_deque_row(ipp, row);
      /* remove elements of the row from the constraint matrix */
      while (row->ptr != NULL)
      {  /* get a next element in the row */
         aij = row->ptr;
         /* remove the element from the row list */
         row->ptr = aij->r_next;
         /* remove the element from the column list */
         if (aij->c_prev == NULL)
            aij->col->ptr = aij->c_next;
         else
            aij->c_prev->c_next = aij->c_next;
         if (aij->c_next == NULL)
            ;
         else
            aij->c_next->c_prev = aij->c_prev;
         /* and return it to its pool */
         dmp_free_atom(ipp->aij_pool, aij, sizeof(IPPAIJ));
      }
      /* remove the row from the linked list */
      if (row->prev == NULL)
         ipp->row_ptr = row->next;
      else
         row->prev->next = row->next;
      if (row->next == NULL)
         ;
      else
         row->next->prev = row->prev;
      /* and return the row to its pool */
      dmp_free_atom(ipp->row_pool, row, sizeof(IPPROW));
      return;
}

/*----------------------------------------------------------------------
-- ipp_remove_col - remove column from the transformed problem.
--
-- SYNOPSIS
--
-- #include "glpipp.h"
-- void ipp_remove_col(IPP *ipp, IPPCOL *col);
--
-- DESCRIPTION
--
-- The routine ipp_remove_col removes a column, which the parameter col
-- points to, from the transformed problem. */

void ipp_remove_col(IPP *ipp, IPPCOL *col)
{     IPPAIJ *aij;
      /* remove the column from the active queue */
      ipp_deque_col(ipp, col);
      /* remove elements of the column from the constraint matrix */
      while (col->ptr != NULL)
      {  /* get a next element in the column */
         aij = col->ptr;
         /* remove the element from the column list */
         col->ptr = aij->c_next;
         /* remove the element from the row list */
         if (aij->r_prev == NULL)
            aij->row->ptr = aij->r_next;
         else
            aij->r_prev->r_next = aij->r_next;
         if (aij->r_next == NULL)
            ;
         else
            aij->r_next->r_prev = aij->r_prev;
         /* and return it to its pool */
         dmp_free_atom(ipp->aij_pool, aij, sizeof(IPPAIJ));
      }
      /* remove the column from the linked list */
      if (col->prev == NULL)
         ipp->col_ptr = col->next;
      else
         col->prev->next = col->next;
      if (col->next == NULL)
         ;
      else
         col->next->prev = col->prev;
      /* and return the column to its pool */
      dmp_free_atom(ipp->col_pool, col, sizeof(IPPCOL));
      return;
}

/*----------------------------------------------------------------------
-- ipp_enque_row - place row in the active queue.
--
-- SYNOPSIS
--
-- #include "glpipp.h"
-- void ipp_enque_row(IPP *ipp, IPPROW *row);
--
-- DESCRIPTION
--
-- The routine ipp_enque_row places the specified row to the queue of
-- active rows. */

void ipp_enque_row(IPP *ipp, IPPROW *row)
{     if (!row->q_flag)
      {  row->q_flag = 1;
         row->q_prev = NULL;
         row->q_next = ipp->row_que;
         if (ipp->row_que != NULL) ipp->row_que->q_prev = row;
         ipp->row_que = row;
      }
      return;
}

/*----------------------------------------------------------------------
-- ipp_deque_row - remove row from the active queue.
--
-- SYNOPSIS
--
-- #include "glpipp.h"
-- void ipp_deque_row(IPP *ipp, IPPROW *row);
--
-- DESCRIPTION
--
-- The routine ipp_deque_row removes the specified row from the queue
-- of active rows. */

void ipp_deque_row(IPP *ipp, IPPROW *row)
{     if (row->q_flag)
      {  row->q_flag = 0;
         if (row->q_prev == NULL)
            ipp->row_que = row->q_next;
         else
            row->q_prev->q_next = row->q_next;
         if (row->q_next == NULL)
            ;
         else
            row->q_next->q_prev = row->q_prev;
      }
      return;
}

/*----------------------------------------------------------------------
-- ipp_enque_col - place column in the active queue.
--
-- SYNOPSIS
--
-- #include "glpipp.h"
-- void ipp_enque_col(IPP *ipp, IPPCOL *col);
--
-- DESCRIPTION
--
-- The routine ipp_enque_col places the specified column to the queue of
-- active columns. */

void ipp_enque_col(IPP *ipp, IPPCOL *col)
{     if (!col->q_flag)
      {  col->q_flag = 1;
         col->q_prev = NULL;
         col->q_next = ipp->col_que;
         if (ipp->col_que != NULL) ipp->col_que->q_prev = col;
         ipp->col_que = col;
      }
      return;
}

/*----------------------------------------------------------------------
-- ipp_deque_col - remove column from the active queue.
--
-- SYNOPSIS
--
-- #include "glpipp.h"
-- void ipp_deque_col(IPP *ipp, IPPCOL *col);
--
-- DESCRIPTION
--
-- The routine ipp_deque_col removes the specified column from the queue
-- of active columns. */

void ipp_deque_col(IPP *ipp, IPPCOL *col)
{     if (col->q_flag)
      {  col->q_flag = 0;
         if (col->q_prev == NULL)
            ipp->col_que = col->q_next;