3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
20 ///\brief Implementation of the LEMON-GLPK lp solver interface.
22 #include <lemon/lp_glpk.h>
27 LpGlpk::LpGlpk() : Parent() {
28 rows = _lp_bits::LpId(1);
29 cols = _lp_bits::LpId(1);
30 lp = lpx_create_prob();
31 ///\todo control function for this:
32 lpx_set_int_parm(lp, LPX_K_DUAL, 1);
36 LpGlpk::LpGlpk(const LpGlpk &glp) : Parent() {
37 rows = _lp_bits::LpId(1);
38 cols = _lp_bits::LpId(1);
39 lp = lpx_create_prob();
40 ///\todo control function for this:
41 lpx_set_int_parm(lp, LPX_K_DUAL, 1);
43 //Coefficient matrix, row bounds
44 lpx_add_rows(lp, lpx_get_num_rows(glp.lp));
45 lpx_add_cols(lp, lpx_get_num_cols(glp.lp));
47 int ind[1+lpx_get_num_cols(glp.lp)];
48 Value val[1+lpx_get_num_cols(glp.lp)];
49 for (int i=1;i<=lpx_get_num_rows(glp.lp);++i)
51 len=lpx_get_mat_row(glp.lp,i,ind,val);
52 lpx_set_mat_row(lp, i,len,ind,val);
53 lpx_set_row_bnds(lp,i,lpx_get_row_type(glp.lp,i),
54 lpx_get_row_lb(glp.lp,i),lpx_get_row_ub(glp.lp,i));
57 //Objective function, coloumn bounds
58 lpx_set_obj_dir(lp, lpx_get_obj_dir(glp.lp));
59 //Objectif function's constant term treated separately
60 lpx_set_obj_coef(lp,0,lpx_get_obj_coef(glp.lp,0));
61 for (int i=1;i<=lpx_get_num_cols(glp.lp);++i)
63 lpx_set_obj_coef(lp,i,lpx_get_obj_coef(glp.lp,i));
64 lpx_set_col_bnds(lp,i,lpx_get_col_type(glp.lp,i),
65 lpx_get_col_lb(glp.lp,i),lpx_get_col_ub(glp.lp,i));
73 int LpGlpk::_addCol() {
74 int i=lpx_add_cols(lp, 1);
75 _setColLowerBound(i, -INF);
76 _setColUpperBound(i, INF);
83 LpSolverBase &LpGlpk::_newLp()
85 LpGlpk* newlp=new LpGlpk;
91 LpSolverBase &LpGlpk::_copyLp()
93 LpGlpk* newlp=new LpGlpk(*this);
97 int LpGlpk::_addRow() {
98 int i=lpx_add_rows(lp, 1);
103 void LpGlpk::_eraseCol(int i) {
106 lpx_del_cols(lp, 1, cols);
109 void LpGlpk::_eraseRow(int i) {
112 lpx_del_rows(lp, 1, rows);
115 void LpGlpk::_getColName(int col, std::string & name)
118 char *n = lpx_get_col_name(lp,col);
123 void LpGlpk::_setColName(int col, const std::string & name)
125 lpx_set_col_name(lp,col,const_cast<char*>(name.c_str()));
129 void LpGlpk::_setRowCoeffs(int i, LpRowIterator b, LpRowIterator e)
131 std::vector<int> indices;
132 std::vector<Value> values;
134 indices.push_back(0);
137 for(LpRowIterator it=b; it!=e; ++it) {
138 indices.push_back(it->first);
139 values.push_back(it->second);
142 lpx_set_mat_row(lp, i, values.size() - 1, &indices[0], &values[0]);
145 void LpGlpk::_setColCoeffs(int i, LpColIterator b, LpColIterator e) {
147 std::vector<int> indices;
148 std::vector<Value> values;
150 indices.push_back(0);
153 for(LpColIterator it=b; it!=e; ++it) {
154 indices.push_back(it->first);
155 values.push_back(it->second);
158 lpx_set_mat_col(lp, i, values.size() - 1, &indices[0], &values[0]);
162 void LpGlpk::_setCoeff(int row, int col, Value value)
165 if (lpx_get_num_cols(lp) < lpx_get_num_rows(lp)) {
167 int length=lpx_get_mat_row(lp, row, 0, 0);
169 std::vector<int> indices(length + 2);
170 std::vector<Value> values(length + 2);
172 lpx_get_mat_row(lp, row, &indices[0], &values[0]);
174 //The following code does not suppose that the elements of the
175 //array indices are sorted
177 for (int i = 1; i <= length; ++i) {
178 if (indices[i]==col){
187 values[length]=value;
190 lpx_set_mat_row(lp, row, length, &indices[0], &values[0]);
194 int length=lpx_get_mat_col(lp, col, 0, 0);
196 std::vector<int> indices(length + 2);
197 std::vector<Value> values(length + 2);
199 lpx_get_mat_col(lp, col, &indices[0], &values[0]);
201 //The following code does not suppose that the elements of the
202 //array indices are sorted
204 for (int i = 1; i <= length; ++i) {
205 if (indices[i]==col){
214 values[length]=value;
217 lpx_set_mat_col(lp, col, length, &indices[0], &values[0]);
221 LpGlpk::Value LpGlpk::_getCoeff(int row, int col)
224 int length=lpx_get_mat_row(lp, row, 0, 0);
226 std::vector<int> indices(length + 2);
227 std::vector<Value> values(length + 2);
229 lpx_get_mat_row(lp, row, &indices[0], &values[0]);
231 //The following code does not suppose that the elements of the
232 //array indices are sorted
233 for (int i = 1; i <= length; ++i) {
234 if (indices[i]==col){
243 void LpGlpk::_setColLowerBound(int i, Value lo)
248 int b=lpx_get_col_type(lp, i);
249 double up=lpx_get_col_ub(lp, i);
254 lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
260 lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
269 lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
275 lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
277 lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
286 LpGlpk::Value LpGlpk::_getColLowerBound(int i)
288 int b=lpx_get_col_type(lp, i);
293 return lpx_get_col_lb(lp, i);
299 void LpGlpk::_setColUpperBound(int i, Value up)
304 int b=lpx_get_col_type(lp, i);
305 double lo=lpx_get_col_lb(lp, i);
312 lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
316 lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
324 lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
327 lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
333 lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
335 lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
343 LpGlpk::Value LpGlpk::_getColUpperBound(int i)
345 int b=lpx_get_col_type(lp, i);
350 return lpx_get_col_ub(lp, i);
356 void LpGlpk::_setRowBounds(int i, Value lb, Value ub)
359 if (lb==INF || ub==-INF) {
365 lpx_set_row_bnds(lp, i, LPX_FR, lb, ub);
368 lpx_set_row_bnds(lp, i, LPX_UP, lb, ub);
373 lpx_set_row_bnds(lp, i, LPX_LO, lb, ub);
378 lpx_set_row_bnds(lp, i, LPX_FX, lb, ub);
381 lpx_set_row_bnds(lp, i, LPX_DB, lb, ub);
388 void LpGlpk::_getRowBounds(int i, Value &lb, Value &ub)
391 int b=lpx_get_row_type(lp, i);
398 lb=lpx_get_row_lb(lp, i);
407 ub=lpx_get_row_ub(lp, i);
412 void LpGlpk::_setObjCoeff(int i, Value obj_coef)
414 //i=0 means the constant term (shift)
415 lpx_set_obj_coef(lp, i, obj_coef);
418 LpGlpk::Value LpGlpk::_getObjCoeff(int i){
419 //i=0 means the constant term (shift)
420 return lpx_get_obj_coef(lp, i);
423 void LpGlpk::_clearObj()
425 for (int i=0;i<=lpx_get_num_cols(lp);++i){
426 lpx_set_obj_coef(lp, i, 0);
430 LpGlpk::SolveExitStatus LpGlpk::_solve()
432 // A way to check the problem to be solved
433 //lpx_write_cpxlp(lp,"naittvan.cpx");
436 int i = lpx_simplex(lp);
446 LpGlpk::Value LpGlpk::_getPrimal(int i)
448 return lpx_get_col_prim(lp,i);
451 LpGlpk::Value LpGlpk::_getDual(int i)
453 return lpx_get_row_dual(lp,i);
456 LpGlpk::Value LpGlpk::_getPrimalValue()
458 return lpx_get_obj_val(lp);
460 bool LpGlpk::_isBasicCol(int i) {
461 return (lpx_get_col_stat(lp, i)==LPX_BS);
465 LpGlpk::SolutionStatus LpGlpk::_getPrimalStatus()
467 int stat= lpx_get_status(lp);
469 case LPX_UNDEF://Undefined (no solve has been run yet)
471 case LPX_NOFEAS://There is no feasible solution (primal, I guess)
472 case LPX_INFEAS://Infeasible
474 case LPX_UNBND://Unbounded
476 case LPX_FEAS://Feasible
478 case LPX_OPT://Feasible
481 return UNDEFINED; //to avoid gcc warning
486 LpGlpk::SolutionStatus LpGlpk::_getDualStatus()
488 // std::cout<<"Itt megy: "<<lpx_get_dual_stat(lp)<<std::endl;
489 // std::cout<<"Itt a primal: "<<lpx_get_prim_stat(lp)<<std::endl;
491 switch (lpx_get_dual_stat(lp)) {
492 case LPX_D_UNDEF://Undefined (no solve has been run yet)
494 case LPX_D_NOFEAS://There is no dual feasible solution
495 // case LPX_D_INFEAS://Infeasible
497 case LPX_D_FEAS://Feasible
498 switch (lpx_get_status(lp)) {
507 return UNDEFINED; //to avoid gcc warning
512 LpGlpk::ProblemTypes LpGlpk::_getProblemType()
514 //int stat= lpx_get_status(lp);
515 int statp= lpx_get_prim_stat(lp);
516 int statd= lpx_get_dual_stat(lp);
517 if (statp==LPX_P_FEAS && statd==LPX_D_FEAS)
518 return PRIMAL_DUAL_FEASIBLE;
519 if (statp==LPX_P_FEAS && statd==LPX_D_NOFEAS)
520 return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
521 if (statp==LPX_P_NOFEAS && statd==LPX_D_FEAS)
522 return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;
523 if (statp==LPX_P_NOFEAS && statd==LPX_D_NOFEAS)
524 return PRIMAL_DUAL_INFEASIBLE;
529 void LpGlpk::_setMax()
531 lpx_set_obj_dir(lp, LPX_MAX);
534 void LpGlpk::_setMin()
536 lpx_set_obj_dir(lp, LPX_MIN);
539 bool LpGlpk::_isMax()
541 return (lpx_get_obj_dir(lp)==LPX_MAX);
546 void LpGlpk::messageLevel(int m)
548 lpx_set_int_parm(lp, LPX_K_MSGLEV, m);
551 void LpGlpk::presolver(bool b)
553 lpx_set_int_parm(lp, LPX_K_PRESOL, b);
557 } //END OF NAMESPACE LEMON