2 * Copyright (C) 2005-2011 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Interface for specifying an milp. Does not define a solution method.
23 * @author Daniel Grund
34 #include "sp_matrix.h"
36 typedef enum _lpp_opt_t {
41 typedef enum _lpp_cst_t {
48 typedef enum _lpp_var_t {
55 typedef enum _lpp_sol_state_t {
64 typedef enum _lpp_value_kind_t {
70 typedef enum _lpp_emphasis_t {
78 typedef struct _name_t {
79 const char *name; /**< the name of the var/constraint supplied by user */
80 int nr; /**< the col/row number in the matrix */
81 lpp_value_kind_t value_kind;
89 typedef struct _lpp_t {
90 /* The problem data */
91 const char *name; /**< A textual name for this problem */
92 FILE *log; /**< The log file. */
93 lpp_opt_t opt_type; /**< Optimization direction */
94 struct obstack obst; /**< Obstack for variable names */
95 sp_matrix_t *m; /**< The matrix holding objective, constraints and rhs */
97 /* Cst/Var to Nr mapping */
98 set *cst2nr; /**< Holds name_t's for constraints */
99 set *var2nr; /**< Holds name_t's for variables */
101 /* Nr to Cst/Var mapping */
102 int cst_size, var_size; /**< Size of the csts/vars-arrays below */
103 int cst_next, var_next; /**< Next free position in arrays below */
104 lpp_name_t **csts; /**< Pointers to the elements in the cst2nr set */
105 lpp_name_t **vars; /**< Pointers to the elements in the var2nr set */
106 double objval; /**< OUT: Value of the objective function. */
107 double best_bound; /**< OUT: best bound to the integer solution. */
108 double grow_factor; /**< The factor by which the vars and constraints are enlarged */
110 /* Solving options */
111 bool set_bound; /**< IN: Boolean flag to set a bound for the objective function. */
112 double bound; /**< IN: The bound. Only valid if set_bound == 1. */
113 double time_limit_secs; /**< IN: Time limit to obey while solving (0.0 means no time limit) */
116 lpp_sol_state_t sol_state; /**< State of the solution */
117 double sol_time; /**< Time in seconds */
118 unsigned iterations; /**< Number of iterations CPLEX needed to solve the ILP (whatever this means) */
121 unsigned next_name_number; /**< for internal use only */
122 lpp_emphasis_t emphasis; /**< On what should CPLEX concentrate (feasibility, bestbound, ...) */
124 /* some statistic stuff */
125 unsigned send_time; /**< in case of solve_net: send time in usec */
126 unsigned recv_time; /**< in case of solve_net: recv time in usec */
127 unsigned n_elems; /**< number of elements stored in the matrix */
128 unsigned matrix_mem; /**< memory used by matrix elements (in bytes) */
129 double density; /**< density of the matrix (percentage) */
132 #define ERR_NAME_NOT_ALLOWED -2
135 * Creates a new problem. Optimization type is minimize or maximize.
136 * Implicit row with name "obj" is inserted.
137 * Implicit col with name "rhs" is inserted.
139 lpp_t *lpp_new(const char *name, lpp_opt_t opt_type);
142 * Creates a new problem. Optimization type is minimize or maximize.
143 * Implicit row with name "obj" is inserted.
144 * Implicit col with name "rhs" is inserted.
145 * @param estimated_vars The estimated number of variables for the problem
146 * @param estimated_csts The estimated number of constraints for the problem
147 * @param grow_factor By which factor should the problem grow, if there are
148 * more variables or constraints than estimated.
150 lpp_t *lpp_new_userdef(const char *name, lpp_opt_t opt_type,
151 int estimated_vars, int estimated_csts,
155 * Frees the matrix embedded in the LPP.
157 void lpp_free_matrix(lpp_t *lpp);
160 * Frees all memory allocated for LPP data structure.
162 void lpp_free(lpp_t *lpp);
165 * @return The constant term in the objective function
167 double lpp_get_fix_costs(lpp_t *lpp);
170 * Sets the constant term in the objective function to @p value
172 void lpp_set_fix_costs(lpp_t *lpp, double value);
175 * Adds a constraint to a problem. If a constraint with the same name already
176 * exists nothing is altered, and the index of the existing entry is returned.
177 * @param cst_name The name of the constraint (1st char only alpha-numeric!). If NULL, a default name will be used.
178 * @param cst_type The type of constraint: objective, equality, less-or-equal, greater-or-equal
179 * @param rhs The right hand side value to set for this constraint.
180 * @return The (new or existing) index of the constraint
182 int lpp_add_cst(lpp_t *lpp, const char *cst_name, lpp_cst_t cst_type, double rhs);
185 * Adds a constraint to a problem. If a constraint with the same name already
186 * exists it dies a horribly cruel death
187 * @param cst_name The name of the constraint (1st char only alpha-numeric!). If NULL, a default name will be used.
188 * @param cst_type The type of constraint: objective, equality, less-or-equal, greater-or-equal
189 * @param rhs The right hand side value to set for this constraint.
190 * @return The (new or existing) index of the constraint
192 int lpp_add_cst_uniq(lpp_t *lpp, const char *cst_name, lpp_cst_t cst_type, double rhs);
195 * Returns the internal index of a constraint.
196 * @param cst_name The name of the constraint
197 * @return The internal index of constraint @p cst_name or -1 if it does not exist.
199 int lpp_get_cst_idx(lpp_t *lpp, const char *cst_name);
202 * Returns the name of a constraint.
203 * @param index The internal index of a constraint.
204 * @param buf A buffer to hold the name of the constraint
205 * @param buf_size Size of the buffer
207 void lpp_get_cst_name(lpp_t *lpp, int index, char *buf, size_t buf_size);
210 * Adds a variable to a problem. If a variable with the same name already
211 * exists nothing is altered, and the index of the existing entry is returned.
212 * @param var_name The name of the constraint (1st char only alpha-numeric!). If NULL, a default name will be used.
213 * @param var_type The type of variable: real, binary
214 * @param obj The objective value coefficient for this variable.
215 * @return The (new or existing) index of the variable
217 * NOTE: common integer or semi-continuous vars are not (yet) implemented
219 int lpp_add_var(lpp_t *lpp, const char *var_name, lpp_var_t var_type, double obj);
222 * Same as lpp_add_var() but the user can supply a default value.
224 int lpp_add_var_default(lpp_t *lpp, const char *var_name, lpp_var_t var_type, double obj, double startval);
227 * Returns the internal index of a variable.
228 * @param cst_name The name of the variable
229 * @return The internal index of variable @p var_name or -1 if it does not exist.
231 int lpp_get_var_idx(lpp_t *lpp, const char *var_name);
234 * Returns the name of a variable.
235 * @param index The internal index of a variable.
236 * @param buf A buffer to hold the name of the variable
237 * @param buf_size Size of the buffer
239 void lpp_get_var_name(lpp_t *lpp, int index, char *buf, size_t buf_size);
242 * Sets the factor of the variable @p var_name in constraint @p cst_name to @p value.
243 * @return -1 if constraint or variable name does not exist.
246 int lpp_set_factor(lpp_t *lpp, const char *cst_name, const char *var_name, double value);
249 * Same as lpp_set_factor but uses the internal indices instead of names.
250 * @return -1 if an index was invalid
253 int lpp_set_factor_fast(lpp_t *lpp, int cst_idx, int var_idx, double value);
255 int lpp_set_factor_fast_bulk(lpp_t *lpp, int cst_idx, int *var_idx, int num_vars, double value);
258 * Set a starting value for a var.
259 * @param var_idx The index of the variable to set the value for.
260 * @param value The value to set.
262 void lpp_set_start_value(lpp_t *lpp, int var_idx, double value);
265 * @return The solution values of the variables from index begin to index end.
267 lpp_sol_state_t lpp_get_solution(lpp_t *lpp, double *values, int begin, int end);
270 * Dumps the lpp into a file with name @p filename in MPS-format
272 void lpp_dump(lpp_t *lpp, const char *filename);
275 * Set the log file, where the solver should write to.
276 * @param lpp The problem.
277 * @param log The logfile. NULL for no logging.
279 void lpp_set_log(lpp_t *lpp, FILE *log);
282 * Check the start values and list conflicting constraints.
284 void lpp_check_startvals(lpp_t *lpp);
287 * Dump problem into a text file.
288 * @param lpp The problem.
291 void lpp_dump_plain(lpp_t *lpp, FILE *f);
293 static inline unsigned lpp_get_iter_cnt(const lpp_t *lpp)
295 return lpp->iterations;
298 static inline double lpp_get_sol_time(const lpp_t *lpp)
300 return lpp->sol_time;
303 static inline lpp_sol_state_t lpp_get_sol_state(const lpp_t *lpp)
305 return lpp->sol_state;
308 static inline int lpp_get_var_count(const lpp_t *lpp)
310 return lpp->var_next-1;
313 static inline int lpp_get_cst_count(const lpp_t *lpp)
315 return lpp->cst_next-1;
318 static inline double lpp_get_var_sol(const lpp_t *lpp, int idx)
320 return lpp->vars[idx]->value;
323 static inline bool lpp_is_sol_valid(const lpp_t *lpp)
325 return lpp_get_sol_state(lpp) >= lpp_feasible;
328 static inline void lpp_set_time_limit(lpp_t *lpp, double secs)
330 lpp->time_limit_secs = secs;
334 * Set a bound for the objective function.
335 * @param lpp The problem.
336 * @param bound A bound for the objective function.
337 * If the problem is a minimization problem, the bound
338 * is a lower bound. If it is a maximization problem,
339 * the bound is an upper bound.
341 static inline void lpp_set_bound(lpp_t *lpp, double bound)
343 lpp->set_bound = true;
349 * @param lpp The problem.
351 static inline void lpp_unset_bound(lpp_t *lpp)
353 lpp->set_bound = false;
358 * @param lpp The problem.
359 * @param host The host to solve on.
360 * @param solver The solver to use.
362 void lpp_solve(lpp_t *lpp, const char* host, const char* solver);