glplpp01.c

著名的大规模线性规划求解器源码GLPK.C语言版本,可以修剪.内有详细帮助文档.

/* glplpp01.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 "glpapi.h"
#include "glplpp.h"
#define dmp_create_poolx(size) dmp_create_pool()
#define dmp_get_atomv dmp_get_atom

/*----------------------------------------------------------------------
-- lpp_create_wksp - create LP presolver workspace.
--
-- *Synopsis*
--
-- #include "glplpp.h"
-- LPP *lpp_create_wksp(void);
--
-- *Description*
--
-- The routine lpp_create_wksp creates an empty workspace used by the
-- LP presolver routines.
--
-- *Returns*
--
-- The routine returns a pointer to the LP workspace created. */

LPP *lpp_create_wksp(void)
{     LPP *lpp;
      lpp = xmalloc(sizeof(LPP));
      lpp->orig_m = 0;
      lpp->orig_n = 0;
      lpp->orig_nnz = 0;
      lpp->orig_dir = LPX_MIN;
      lpp->nrows = 0;
      lpp->ncols = 0;
      lpp->row_pool = dmp_create_poolx(sizeof(LPPROW));
      lpp->col_pool = dmp_create_poolx(sizeof(LPPCOL));
      lpp->aij_pool = dmp_create_poolx(sizeof(LPPAIJ));
      lpp->row_ptr = NULL;
      lpp->col_ptr = NULL;
      lpp->row_que = NULL;
      lpp->col_que = NULL;
      lpp->c0 = 0.0;
      lpp->tqe_pool = dmp_create_poolx(0);
      lpp->tqe_list = NULL;
      lpp->m = 0;
      lpp->n = 0;
      lpp->nnz = 0;
      lpp->row_ref = NULL;
      lpp->col_ref = NULL;
      lpp->row_stat = NULL;
      lpp->row_prim = NULL;
      lpp->row_dual = NULL;
      lpp->col_stat = NULL;
      lpp->col_prim = NULL;
      lpp->col_dual = NULL;
      return lpp;
}

/*----------------------------------------------------------------------
-- lpp_add_row - add new row to the transformed problem.
--
-- *Synopsis*
--
-- #include "glplpp.h"
-- LPPROW *lpp_add_row(LPP *lpp, double lb, double ub);
--
-- *Description*
--
-- The routine lpp_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. */

LPPROW *lpp_add_row(LPP *lpp, double lb, double ub)
{     LPPROW *row;
      row = dmp_get_atom(lpp->row_pool, sizeof(LPPROW));
      row->i = ++(lpp->nrows);
      row->lb = lb;
      row->ub = ub;
      row->ptr = NULL;
      row->temp = 0;
      row->prev = NULL;
      row->next = lpp->row_ptr;
      row->q_flag = 0;
      row->q_prev = row->q_next = NULL;
      if (lpp->row_ptr != NULL) lpp->row_ptr->prev = row;
      lpp->row_ptr = row;
      lpp_enque_row(lpp, row);
      return row;
}

/*----------------------------------------------------------------------
-- lpp_add_col - add new column to the transformed problem.
--
-- *Synopsis*
--
-- #include "glplpp.h"
-- LPPCOL *lpp_add_col(LPP *lpp, double lb, double ub, double c);
--
-- *Description*
--
-- The routine lpp_add_col adds a new empty column to the transformed
-- problem.
--
-- 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. */

LPPCOL *lpp_add_col(LPP *lpp, double lb, double ub, double c)
{     LPPCOL *col;
      col = dmp_get_atom(lpp->col_pool, sizeof(LPPCOL));
      col->j = ++(lpp->ncols);
      col->lb = lb;
      col->ub = ub;
      col->c = c;
      col->ptr = NULL;
      col->prev = NULL;
      col->next = lpp->col_ptr;
      col->q_flag = 0;
      col->q_prev = col->q_next = NULL;
      if (lpp->col_ptr != NULL) lpp->col_ptr->prev = col;
      lpp->col_ptr = col;
      lpp_enque_col(lpp, col);
      return col;
}

/*----------------------------------------------------------------------
-- lpp_add_aij - add new element to the constraint matrix.
--
-- *Synopsis*
--
-- #include "glplpp.h"
-- LPPAIJ *lpp_add_aij(LPP *lpp, LPPROW *row, LPPCOL *col, double val);
--
-- *Description*
--
-- The routine lpp_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. */

LPPAIJ *lpp_add_aij(LPP *lpp, LPPROW *row, LPPCOL *col, double val)
{     LPPAIJ *aij;
      xassert(val != 0.0);
      aij = dmp_get_atom(lpp->aij_pool, sizeof(LPPAIJ));
      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;
}

/*----------------------------------------------------------------------
-- lpp_remove_row - remove row from the transformed problem.
--
-- *Synopsis*
--
-- #include "glplpp.h"
-- void lpp_remove_row(LPP *lpp, LPPROW *row);
--
-- *Description*
--
-- The routine lpp_remove_row removes a row, which the parameter row
-- points to, from the transformed problem. */

void lpp_remove_row(LPP *lpp, LPPROW *row)
{     LPPAIJ *aij;
      /* remove the row from the active queue */
      lpp_deque_row(lpp, row);
      /* remove elements of the row from the constraint matrix */
      while (row->ptr != NULL)
      {  /* get a next element in the row */
         aij = row->ptr;
         /* activate the corresponding column */
         lpp_enque_col(lpp, aij->col);
         /* 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(lpp->aij_pool, aij, sizeof(LPPAIJ));
      }
      /* remove the row from the linked list */
      if (row->prev == NULL)
         lpp->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(lpp->row_pool, row, sizeof(LPPROW));
      return;
}

/*----------------------------------------------------------------------
-- lpp_remove_col - remove column from the transformed problem.
--
-- *Synopsis*
--
-- #include "glplpp.h"
-- void lpp_remove_col(LPP *lpp, LPPCOL *col);
--
-- *Description*
--
-- The routine lpp_remove_col removes a column, which the parameter col
-- points to, from the transformed problem. */

void lpp_remove_col(LPP *lpp, LPPCOL *col)
{     LPPAIJ *aij;
      /* remove the column from the active queue */
      lpp_deque_col(lpp, col);
      /* remove elements of the column from the constraint matrix */
      while (col->ptr != NULL)
      {  /* get a next element in the column */
         aij = col->ptr;
         /* activate the corresponding row */
         lpp_enque_row(lpp, aij->row);
         /* 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(lpp->aij_pool, aij, sizeof(LPPAIJ));
      }
      /* remove the column from the linked list */
      if (col->prev == NULL)
         lpp->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(lpp->col_pool, col, sizeof(LPPCOL));
      return;
}

/*----------------------------------------------------------------------
-- lpp_enque_row - place row in the active queue.
--
-- *Synopsis*
--
-- #include "glplpp.h"
-- void lpp_enque_row(LPP *lpp, LPPROW *row);
--
-- *Description*
--
-- The routine lpp_enque_row places the specified row to the queue of
-- active rows. */

void lpp_enque_row(LPP *lpp, LPPROW *row)
{     if (!row->q_flag)
      {  row->q_flag = 1;
         row->q_prev = NULL;
         row->q_next = lpp->row_que;
         if (lpp->row_que != NULL) lpp->row_que->q_prev = row;
         lpp->row_que = row;
      }
      return;
}

/*----------------------------------------------------------------------
-- lpp_deque_row - remove row from the active queue.
--
-- *Synopsis*
--
-- #include "glplpp.h"
-- void lpp_deque_row(LPP *lpp, LPPROW *row);
--
-- *Description*
--
-- The routine lpp_deque_row removes the specified row from the queue
-- of active rows. */

void lpp_deque_row(LPP *lpp, LPPROW *row)
{     if (row->q_flag)
      {  row->q_flag = 0;
         if (row->q_prev == NULL)
            lpp->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;
}

/*----------------------------------------------------------------------
-- lpp_enque_col - place column in the active queue.
--
-- *Synopsis*
--
-- #include "glplpp.h"
-- void lpp_enque_col(LPP *lpp, LPPCOL *col);
--
-- *Description*
--
-- The routine lpp_enque_col places the specified column to the queue of
-- active columns. */

void lpp_enque_col(LPP *lpp, LPPCOL *col)
{     if (!col->q_flag)
      {  col->q_flag = 1;
         col->q_prev = NULL;
         col->q_next = lpp->col_que;
         if (lpp->col_que != NULL) lpp->col_que->q_prev = col;
         lpp->col_que = col;
      }
      return;
}

/*----------------------------------------------------------------------
-- lpp_deque_col - remove column from the active queue.
--
-- *Synopsis*
--
-- #include "glplpp.h"
-- void lpp_deque_col(LPP *lpp, LPPCOL *col);
--
-- *Description*
--
-- The routine lpp_deque_col removes the specified column from the queue
-- of active columns. */

void lpp_deque_col(LPP *lpp, LPPCOL *col)
{     if (col->q_flag)
      {  col->q_flag = 0;
         if (col->q_prev == NULL)
            lpp->col_que = col->q_next;
         else
            col->q_prev->q_next = col->q_next;
         if (col->q_next == NULL)
            ;
         else
            col->q_next->q_prev = col->q_prev;
      }
      return;
}

/*----------------------------------------------------------------------
-- lpp_load_orig - load original problem into LP presolver workspace.
--
-- *Synopsis*
--
-- #include "glplpp.h"
-- void lpp_load_orig(LPP *lpp, LPX *orig);
--
-- *Description*
--
-- The routine lpp_load_orig loads an original LP problem, which the
-- parameter orig points to, into the LP presolver workspace.
--
-- On exit from the routine the tranformed problem in the workspace is
-- identical to the original problem. */

void lpp_load_orig(LPP *lpp, LPX *orig)
{     LPPROW *row;
      LPPCOL *col, **map;
      int i, j, t, len, typx, *ndx;
      double lb, ub, temp, *c, *val;