nsz Git - libfirm/blob - ir/be/lpp.h

   1 /**
   2  * Author:      Daniel Grund
   3  * Date:                16.05.2005
   4  * Copyright:   (c) Universitaet Karlsruhe
   5  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
   6  *
   7  * Interface for specifying an milp. Does not define a solution method.
   8  */
   9 #ifndef _LPP_H
  10 #define _LPP_H
  11
  12 #include <stdio.h>
  13 #include "set.h"
  14 #include "sp_matrix.h"
  15
  16 typedef enum _opt_t {minimize, maximize} opt_t;
  17 typedef enum _cst_t {objective=0, equal=1, less=2, greater=3} cst_t;
  18 typedef enum _var_t {invalid=0, rhs=1, continous=2, binary=3} var_t;
  19 typedef enum _sol_state_t {unknown=0, infeasible=1, inforunb=2, unbounded=3, feasible=4, optimal=5} sol_state_t;
  20 typedef enum _value_kind_t {none=0, value_start, value_solution} value_kind_t;
  21
  22 typedef struct _name_t name_t;
  23 struct _name_t {
  24         char *name;                                     /**< the name of the var/constraint supplied by user */
  25         int nr;                                         /**< the col/row number in the matrix */
  26         value_kind_t value_kind;
  27         double value;
  28         union _type {
  29                 var_t var_type;
  30                 cst_t cst_type;
  31         } type;
  32 };
  33
  34 typedef struct _lpp_t {
  35         /* The problem data */
  36         char *name;                                             /**< A textual name for this problem */
  37         opt_t opt_type;                                 /**< Optimization direction */
  38         sp_matrix_t *m;                                 /**< The matrix holding objective, constraints and rhs */
  39
  40         /* Cst/Var to Nr mapping */
  41         set *cst2nr;                                    /**< Holds name_t's for constraints */
  42         set *var2nr;                                    /**< Holds name_t's for variables */
  43
  44         /* Nr to Cst/Var mapping */
  45         int cst_size, var_size;                 /**< Size of the csts/vars-arrays below */
  46         int cst_next, var_next;                 /**< Next free position in arrays below */
  47         name_t **csts;                                  /**< Pointers to the elements in the cst2nr set */
  48         name_t **vars;                                  /**< Pointers to the elements in the var2nr set */
  49
  50         /* Solution stuff */
  51         sol_state_t sol_state;
  52         double sol_time;                                        /**< Time in seconds */
  53         unsigned iterations;
  54
  55         char *error;
  56         unsigned next_name_number;
  57 } lpp_t;
  58
  59 #define ERR_NAME_NOT_ALLOWED -2
  60
  61 /**
  62  * Creates a new problem. Optimization type is minimize or maximize.
  63  * Implicit row with name "obj" is inserted.
  64  * Implicit col with name "rhs" is inserted.
  65  */
  66 lpp_t *new_lpp(const char *name, opt_t opt_type);
  67
  68 void free_lpp(lpp_t *lpp);
  69
  70 /**
  71  * Adds a constraint to a problem. If a constraint with the same name already
  72  * exists nothing is altered, and the index of the existing entry is returned.
  73  * @param cst_name The name of the constraint (1st char only alpha-numeric!). If NULL, a default name will be used.
  74  * @param cst_type The type of constraint: objective, equality, less-or-equal, greater-or-equal
  75  * @param rhs The right hand side value to set for this constraint.
  76  * @return The (new or existing) index of the constraint
  77  */
  78 int lpp_add_cst(lpp_t *lpp, char *cst_name, cst_t cst_type, double rhs);
  79
  80 /**
  81  * Returns the internal index of a constraint.
  82  * @param cst_name The name of the constraint
  83  * @return The internal index of constraint @p cst_name or -1 if it does not exist.
  84  */
  85 int lpp_get_cst_idx(lpp_t *lpp, char *cst_name);
  86
  87 /**
  88  * Returns the name of a constraint.
  89  * @param index The internal index of a constraint.
  90  * @param buf A buffer to hold the name of the constraint
  91  * @param buf_size Size of the buffer
  92  */
  93 void lpp_get_cst_name(lpp_t *lpp, int index, char *buf, size_t buf_size);
  94
  95 /**
  96  * Adds a variable to a problem. If a variable with the same name already
  97  * exists nothing is altered, and the index of the existing entry is returned.
  98  * @param var_name The name of the constraint (1st char only alpha-numeric!). If NULL, a default name will be used.
  99  * @param var_type The type of variable: real, binary
 100  * @param obj The objactive value coefficient for this variable.
 101  * @return The (new or existing) index of the variable
 102  *
 103  * NOTE: common integer or semi-continous vars are not (yet) implemented
 104  */
 105 int lpp_add_var(lpp_t *lpp, char *var_name, var_t var_type, double obj);
 106
 107 /**
 108  * Returns the internal index of a variable.
 109  * @param cst_name The name of the variable
 110  * @return The internal index of variable @p var_name or -1 if it does not exist.
 111  */
 112 int lpp_get_var_idx(lpp_t *lpp, char *var_name);
 113
 114 /**
 115  * Returns the name of a variable.
 116  * @param index The internal index of a variable.
 117  * @param buf A buffer to hold the name of the variable
 118  * @param buf_size Size of the buffer
 119  */
 120 void lpp_get_var_name(lpp_t *lpp, int index, char *buf, size_t buf_size);
 121
 122 /**
 123  * Sets the factor of the variable @p var_name in constraint @p cst_name to @p value.
 124  * @return -1 if constraint or variable name does not exist.
 125  *                      0 otherwise
 126  */
 127 int lpp_set_factor(lpp_t *lpp, char *cst_name, char *var_name, double value);
 128
 129 /**
 130  * Same as lpp_set_factor but uses the internal indices instead of names.
 131  * @return -1 if an index was invalid
 132  *                      0 otherwise
 133  */
 134 int lpp_set_factor_fast(lpp_t *lpp, int cst_idx, int var_idx, double value);
 135
 136 /**
 137  * Set a starting value for a var.
 138  * @param var_idx The index of the variable to set the value for.
 139  * @param value The value to set.
 140  */
 141 void lpp_set_start_value(lpp_t *lpp, int var_idx, double value);
 142
 143 /**
 144  * @return The solution values of the variables from index begin to index end.
 145  */
 146 sol_state_t lpp_get_solution(lpp_t *lpp, double *values, int begin, int end);
 147
 148 /**
 149  * Dumps the lpp into a file with name @p filename in MPS-format
 150  */
 151 void lpp_dump(lpp_t *lpp, const char *filename);
 152
 153 #define lpp_get_iter_cnt(lpp) ((lpp)->iterations)
 154 #define lpp_get_sol_time(lpp) ((lpp)->sol_time)
 155
 156 #endif