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

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief   Interface for specifying an milp. Does not define a solution method.
   9  * @author  Daniel Grund
  10  */
  11 #ifndef LPP_LPP_H
  12 #define LPP_LPP_H
  13
  14 #include <stdio.h>
  15 #include <obstack.h>
  16 #include <stdbool.h>
  17
  18 #include "set.h"
  19
  20 #include "sp_matrix.h"
  21
  22 typedef enum _lpp_opt_t {
  23         lpp_minimize,
  24         lpp_maximize
  25 } lpp_opt_t;
  26
  27 typedef enum _lpp_cst_t {
  28         lpp_objective,
  29         lpp_equal,
  30         lpp_less_equal,
  31         lpp_greater_equal
  32 } lpp_cst_t;
  33
  34 typedef enum _lpp_var_t {
  35         lpp_invalid,
  36         lpp_rhs,
  37         lpp_continous,
  38         lpp_binary
  39 } lpp_var_t;
  40
  41 typedef enum _lpp_sol_state_t {
  42         lpp_unknown,
  43         lpp_infeasible,
  44         lpp_inforunb,
  45         lpp_unbounded,
  46         lpp_feasible,
  47         lpp_optimal
  48 } lpp_sol_state_t;
  49
  50 typedef enum _lpp_value_kind_t {
  51         lpp_none,
  52         lpp_value_start,
  53         lpp_value_solution,
  54 } lpp_value_kind_t;
  55
  56 typedef enum _lpp_emphasis_t {
  57         lpp_balanced,
  58         lpp_feasability,
  59         lpp_optimality,
  60         lpp_bestbound,
  61         lpp_hiddenfeasibility
  62 } lpp_emphasis_t;
  63
  64 typedef struct _name_t {
  65         const char *name;           /**< the name of the var/constraint supplied by user */
  66         int nr;                     /**< the col/row number in the matrix */
  67         lpp_value_kind_t value_kind;
  68         double value;
  69         union _type {
  70                 lpp_var_t var_type;
  71                 lpp_cst_t cst_type;
  72         } type;
  73 } lpp_name_t;
  74
  75 typedef struct _lpp_t {
  76         /* The problem data */
  77         const char     *name;            /**< A textual name for this problem */
  78         FILE           *log;             /**< The log file. */
  79         lpp_opt_t      opt_type;         /**< Optimization direction */
  80         struct obstack obst;             /**< Obstack for variable names */
  81         sp_matrix_t    *m;               /**< The matrix holding objective, constraints and rhs */
  82
  83         /* Cst/Var to Nr mapping */
  84         set *cst2nr;                     /**< Holds name_t's for constraints */
  85         set *var2nr;                     /**< Holds name_t's for variables */
  86
  87         /* Nr to Cst/Var mapping */
  88         int        cst_size, var_size;   /**< Size of the csts/vars-arrays below */
  89         int        cst_next, var_next;   /**< Next free position in arrays below */
  90         lpp_name_t **csts;               /**< Pointers to the elements in the cst2nr set */
  91         lpp_name_t **vars;               /**< Pointers to the elements in the var2nr set */
  92         double     objval;               /**< OUT: Value of the objective function. */
  93         double     best_bound;           /**< OUT: best bound to the integer solution. */
  94         double     grow_factor;          /**< The factor by which the vars and constraints are enlarged */
  95
  96         /* Solving options */
  97         bool   set_bound;                /**< IN: Boolean flag to set a bound for the objective function. */
  98         double bound;                    /**< IN: The bound. Only valid if set_bound == 1. */
  99         double time_limit_secs;          /**< IN: Time limit to obey while solving (0.0 means no time limit) */
 100
 101         /* Solution stuff */
 102         lpp_sol_state_t sol_state;       /**< State of the solution */
 103         double          sol_time;        /**< Time in seconds */
 104         unsigned        iterations;      /**< Number of iterations CPLEX needed to solve the ILP (whatever this means) */
 105
 106         char           *error;
 107         unsigned       next_name_number; /**< for internal use only */
 108         lpp_emphasis_t emphasis;         /**< On what should CPLEX concentrate (feasibility, bestbound, ...) */
 109
 110         /* some statistic stuff */
 111         unsigned       send_time;        /**< in case of solve_net: send time in usec */
 112         unsigned       recv_time;        /**< in case of solve_net: recv time in usec */
 113         unsigned       n_elems;          /**< number of elements stored in the matrix */
 114         unsigned       matrix_mem;       /**< memory used by matrix elements (in bytes) */
 115         double         density;          /**< density of the matrix (percentage) */
 116 } lpp_t;
 117
 118 #define ERR_NAME_NOT_ALLOWED -2
 119
 120 /**
 121  * Creates a new problem. Optimization type is minimize or maximize.
 122  * Implicit row with name "obj" is inserted.
 123  * Implicit col with name "rhs" is inserted.
 124  */
 125 lpp_t *lpp_new(const char *name, lpp_opt_t opt_type);
 126
 127 /**
 128  * Creates a new problem. Optimization type is minimize or maximize.
 129  * Implicit row with name "obj" is inserted.
 130  * Implicit col with name "rhs" is inserted.
 131  * @param estimated_vars   The estimated number of variables for the problem
 132  * @param estimated_csts   The estimated number of constraints for the problem
 133  * @param grow_factor      By which factor should the problem grow, if there are
 134  *                         more variables or constraints than estimated.
 135  */
 136 lpp_t *lpp_new_userdef(const char *name, lpp_opt_t opt_type,
 137                                            int estimated_vars, int estimated_csts,
 138                                            double grow_factor);
 139
 140 /**
 141  * Frees the matrix embedded in the LPP.
 142  */
 143 void lpp_free_matrix(lpp_t *lpp);
 144
 145 /**
 146  * Frees all memory allocated for LPP data structure.
 147  */
 148 void lpp_free(lpp_t *lpp);
 149
 150 /**
 151  * @return The constant term in the objective function
 152  */
 153 double lpp_get_fix_costs(lpp_t *lpp);
 154
 155 /**
 156  * Sets the constant term in the objective function to @p value
 157  */
 158 void lpp_set_fix_costs(lpp_t *lpp, double value);
 159
 160 /**
 161  * Adds a constraint to a problem. If a constraint with the same name already
 162  * exists nothing is altered, and the index of the existing entry is returned.
 163  * @param cst_name The name of the constraint (1st char only alpha-numeric!). If NULL, a default name will be used.
 164  * @param cst_type The type of constraint: objective, equality, less-or-equal, greater-or-equal
 165  * @param rhs The right hand side value to set for this constraint.
 166  * @return The (new or existing) index of the constraint
 167  */
 168 int lpp_add_cst(lpp_t *lpp, const char *cst_name, lpp_cst_t cst_type, double rhs);
 169
 170 /**
 171  * Adds a constraint to a problem. If a constraint with the same name already
 172  * exists it dies a horribly cruel death
 173  * @param cst_name The name of the constraint (1st char only alpha-numeric!). If NULL, a default name will be used.
 174  * @param cst_type The type of constraint: objective, equality, less-or-equal, greater-or-equal
 175  * @param rhs The right hand side value to set for this constraint.
 176  * @return The (new or existing) index of the constraint
 177  */
 178 int lpp_add_cst_uniq(lpp_t *lpp, const char *cst_name, lpp_cst_t cst_type, double rhs);
 179
 180 /**
 181  * Returns the internal index of a constraint.
 182  * @param cst_name The name of the constraint
 183  * @return The internal index of constraint @p cst_name or -1 if it does not exist.
 184  */
 185 int lpp_get_cst_idx(lpp_t *lpp, const char *cst_name);
 186
 187 /**
 188  * Returns the name of a constraint.
 189  * @param index The internal index of a constraint.
 190  * @param buf A buffer to hold the name of the constraint
 191  * @param buf_size Size of the buffer
 192  */
 193 void lpp_get_cst_name(lpp_t *lpp, int index, char *buf, size_t buf_size);
 194
 195 /**
 196  * Adds a variable to a problem. If a variable with the same name already
 197  * exists nothing is altered, and the index of the existing entry is returned.
 198  * @param var_name The name of the constraint (1st char only alpha-numeric!). If NULL, a default name will be used.
 199  * @param var_type The type of variable: real, binary
 200  * @param obj The objective value coefficient for this variable.
 201  * @return The (new or existing) index of the variable
 202  *
 203  * NOTE: common integer or semi-continuous vars are not (yet) implemented
 204  */
 205 int lpp_add_var(lpp_t *lpp, const char *var_name, lpp_var_t var_type, double obj);
 206
 207 /**
 208  * Same as lpp_add_var() but the user can supply a default value.
 209  */
 210 int lpp_add_var_default(lpp_t *lpp, const char *var_name, lpp_var_t var_type, double obj, double startval);
 211
 212 /**
 213  * Returns the internal index of a variable.
 214  * @param cst_name The name of the variable
 215  * @return The internal index of variable @p var_name or -1 if it does not exist.
 216  */
 217 int lpp_get_var_idx(lpp_t *lpp, const char *var_name);
 218
 219 /**
 220  * Returns the name of a variable.
 221  * @param index The internal index of a variable.
 222  * @param buf A buffer to hold the name of the variable
 223  * @param buf_size Size of the buffer
 224  */
 225 void lpp_get_var_name(lpp_t *lpp, int index, char *buf, size_t buf_size);
 226
 227 /**
 228  * Sets the factor of the variable @p var_name in constraint @p cst_name to @p value.
 229  * @return -1 if constraint or variable name does not exist.
 230  *          0 otherwise
 231  */
 232 int lpp_set_factor(lpp_t *lpp, const char *cst_name, const char *var_name, double value);
 233
 234 /**
 235  * Same as lpp_set_factor but uses the internal indices instead of names.
 236  * @return -1 if an index was invalid
 237  *          0 otherwise
 238  */
 239 int lpp_set_factor_fast(lpp_t *lpp, int cst_idx, int var_idx, double value);
 240
 241 int lpp_set_factor_fast_bulk(lpp_t *lpp, int cst_idx, int *var_idx, int num_vars, double value);
 242
 243 /**
 244  * Set a starting value for a var.
 245  * @param var_idx The index of the variable to set the value for.
 246  * @param value The value to set.
 247  */
 248 void lpp_set_start_value(lpp_t *lpp, int var_idx, double value);
 249
 250 /**
 251  * @return The solution values of the variables from index begin to index end.
 252  */
 253 lpp_sol_state_t lpp_get_solution(lpp_t *lpp, double *values, int begin, int end);
 254
 255 /**
 256  * Dumps the lpp into a file with name @p filename in MPS-format
 257  */
 258 void lpp_dump(lpp_t *lpp, const char *filename);
 259
 260 /**
 261  * Set the log file, where the solver should write to.
 262  * @param lpp The problem.
 263  * @param log The logfile. NULL for no logging.
 264  */
 265 void lpp_set_log(lpp_t *lpp, FILE *log);
 266
 267 /**
 268  * Check the start values and list conflicting constraints.
 269  */
 270 void lpp_check_startvals(lpp_t *lpp);
 271
 272 /**
 273  * Dump problem into a text file.
 274  * @param lpp The problem.
 275  * @param f   The file.
 276  */
 277 void lpp_dump_plain(lpp_t *lpp, FILE *f);
 278
 279 static inline unsigned lpp_get_iter_cnt(const lpp_t *lpp)
 280 {
 281         return lpp->iterations;
 282 }
 283
 284 static inline double lpp_get_sol_time(const lpp_t *lpp)
 285 {
 286         return lpp->sol_time;
 287 }
 288
 289 static inline lpp_sol_state_t lpp_get_sol_state(const lpp_t *lpp)
 290 {
 291         return lpp->sol_state;
 292 }
 293
 294 static inline int lpp_get_var_count(const lpp_t *lpp)
 295 {
 296         return lpp->var_next-1;
 297 }
 298
 299 static inline int lpp_get_cst_count(const lpp_t *lpp)
 300 {
 301         return lpp->cst_next-1;
 302 }
 303
 304 static inline double lpp_get_var_sol(const lpp_t *lpp, int idx)
 305 {
 306         return lpp->vars[idx]->value;
 307 }
 308
 309 static inline bool lpp_is_sol_valid(const lpp_t *lpp)
 310 {
 311         return lpp_get_sol_state(lpp) >= lpp_feasible;
 312 }
 313
 314 static inline void lpp_set_time_limit(lpp_t *lpp, double secs)
 315 {
 316         lpp->time_limit_secs = secs;
 317 }
 318
 319 /**
 320  * Set a bound for the objective function.
 321  * @param lpp The problem.
 322  * @param bound A bound for the objective function.
 323  *              If the problem is a minimization problem, the bound
 324  *              is a lower bound. If it is a maximization problem,
 325  *              the bound is an upper bound.
 326  */
 327 static inline void lpp_set_bound(lpp_t *lpp, double bound)
 328 {
 329         lpp->set_bound = true;
 330         lpp->bound = bound;
 331 }
 332
 333 /**
 334  * Clear a set bound.
 335  * @param lpp The problem.
 336  */
 337 static inline void lpp_unset_bound(lpp_t *lpp)
 338 {
 339         lpp->set_bound = false;
 340 }
 341
 342 /**
 343  * Solve an ILP.
 344  * @param lpp    The problem.
 345  * @param host   The host to solve on.
 346  * @param solver The solver to use.
 347  */
 348 void lpp_solve(lpp_t *lpp, const char* host, const char* solver);
 349
 350 #endif