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 lp(lpx_create_prob()) {
29 ///\todo constrol function for this:
30 lpx_set_int_parm(lp, LPX_K_DUAL, 1);
34 LpGlpk::LpGlpk(const LpGlpk &glp) : Parent(glp),
35 lp(lpx_create_prob()) {
36 ///\todo constrol function for this:
37 lpx_set_int_parm(lp, LPX_K_DUAL, 1);
39 //Coefficient matrix, row bounds
40 lpx_add_rows(lp, lpx_get_num_rows(glp.lp));
41 lpx_add_cols(lp, lpx_get_num_cols(glp.lp));
43 int ind[1+lpx_get_num_cols(glp.lp)];
44 Value val[1+lpx_get_num_cols(glp.lp)];
45 for (int i=1;i<=lpx_get_num_rows(glp.lp);++i)
47 len=lpx_get_mat_row(glp.lp,i,ind,val);
48 lpx_set_mat_row(lp, i,len,ind,val);
49 lpx_set_row_bnds(lp,i,lpx_get_row_type(glp.lp,i),
50 lpx_get_row_lb(glp.lp,i),lpx_get_row_ub(glp.lp,i));
53 //Objective function, coloumn bounds
54 lpx_set_obj_dir(lp, lpx_get_obj_dir(glp.lp));
55 //Objectif function's constant term treated separately
56 lpx_set_obj_coef(lp,0,lpx_get_obj_coef(glp.lp,0));
57 for (int i=1;i<=lpx_get_num_cols(glp.lp);++i)
59 lpx_set_obj_coef(lp,i,lpx_get_obj_coef(glp.lp,i));
60 lpx_set_col_bnds(lp,i,lpx_get_col_type(glp.lp,i),
61 lpx_get_col_lb(glp.lp,i),lpx_get_col_ub(glp.lp,i));
69 int LpGlpk::_addCol() {
70 int i=lpx_add_cols(lp, 1);
71 _setColLowerBound(i, -INF);
72 _setColUpperBound(i, INF);
79 LpSolverBase &LpGlpk::_newLp()
81 LpGlpk* newlp=new LpGlpk;
87 LpSolverBase &LpGlpk::_copyLp()
89 LpGlpk* newlp=new LpGlpk(*this);
93 int LpGlpk::_addRow() {
94 int i=lpx_add_rows(lp, 1);
99 void LpGlpk::_eraseCol(int i) {
102 lpx_del_cols(lp, 1, cols);
105 void LpGlpk::_eraseRow(int i) {
108 lpx_del_rows(lp, 1, rows);
111 void LpGlpk::_getColName(int col, std::string & name)
114 char *n = lpx_get_col_name(lp,col);
119 void LpGlpk::_setColName(int col, const std::string & name)
121 lpx_set_col_name(lp,col,const_cast<char*>(name.c_str()));
124 void LpGlpk::_setRowCoeffs(int i, LpRowIterator b, LpRowIterator e)
126 std::vector<int> indices;
127 std::vector<Value> values;
129 indices.push_back(0);
132 for(LpRowIterator it=b; it!=e; ++it) {
133 indices.push_back(it->first);
134 values.push_back(it->second);
137 lpx_set_mat_row(lp, i, values.size() - 1, &indices[0], &values[0]);
140 void LpGlpk::_setColCoeffs(int i, LpColIterator b, LpColIterator e) {
142 std::vector<int> indices;
143 std::vector<Value> values;
145 indices.push_back(0);
148 for(LpColIterator it=b; it!=e; ++it) {
149 indices.push_back(it->first);
150 values.push_back(it->second);
153 lpx_set_mat_col(lp, i, values.size() - 1, &indices[0], &values[0]);
157 void LpGlpk::_setCoeff(int row, int col, Value value)
160 if (lpx_get_num_cols(lp) < lpx_get_num_rows(lp)) {
162 int length=lpx_get_mat_row(lp, row, 0, 0);
164 std::vector<int> indices(length + 2);
165 std::vector<Value> values(length + 2);
167 lpx_get_mat_row(lp, row, &indices[0], &values[0]);
169 //The following code does not suppose that the elements of the
170 //array indices are sorted
172 for (int i = 1; i <= length; ++i) {
173 if (indices[i]==col){
182 values[length]=value;
185 lpx_set_mat_row(lp, row, length, &indices[0], &values[0]);
189 int length=lpx_get_mat_col(lp, col, 0, 0);
191 std::vector<int> indices(length + 2);
192 std::vector<Value> values(length + 2);
194 lpx_get_mat_col(lp, col, &indices[0], &values[0]);
196 //The following code does not suppose that the elements of the
197 //array indices are sorted
199 for (int i = 1; i <= length; ++i) {
200 if (indices[i]==col){
209 values[length]=value;
212 lpx_set_mat_col(lp, col, length, &indices[0], &values[0]);
216 void LpGlpk::_setColLowerBound(int i, Value lo)
221 int b=lpx_get_col_type(lp, i);
222 double up=lpx_get_col_ub(lp, i);
227 lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
233 lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
242 lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
248 lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
250 lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
259 void LpGlpk::_setColUpperBound(int i, Value up)
264 int b=lpx_get_col_type(lp, i);
265 double lo=lpx_get_col_lb(lp, i);
272 lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
276 lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
284 lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
287 lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
293 lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
295 lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
303 // void LpGlpk::_setRowLowerBound(int i, Value lo)
308 // int b=lpx_get_row_type(lp, i);
309 // double up=lpx_get_row_ub(lp, i);
314 // lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
320 // lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
329 // lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
335 // lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
337 // lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
345 // void LpGlpk::_setRowUpperBound(int i, Value up)
350 // int b=lpx_get_row_type(lp, i);
351 // double lo=lpx_get_row_lb(lp, i);
358 // lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
362 // lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
370 // lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
373 // lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
379 // lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
381 // lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
389 void LpGlpk::_setRowBounds(int i, Value lb, Value ub)
392 if (lb==INF || ub==-INF) {
398 lpx_set_row_bnds(lp, i, LPX_FR, lb, ub);
401 lpx_set_row_bnds(lp, i, LPX_UP, lb, ub);
406 lpx_set_row_bnds(lp, i, LPX_LO, lb, ub);
411 lpx_set_row_bnds(lp, i, LPX_FX, lb, ub);
414 lpx_set_row_bnds(lp, i, LPX_DB, lb, ub);
421 void LpGlpk::_setObjCoeff(int i, Value obj_coef)
423 //i=0 means the constant term (shift)
424 lpx_set_obj_coef(lp, i, obj_coef);
427 void LpGlpk::_clearObj()
429 for (int i=0;i<=lpx_get_num_cols(lp);++i){
430 lpx_set_obj_coef(lp, i, 0);
433 // void LpGlpk::_setObj(int length,
434 // int const * indices,
435 // Value const * values )
437 // Value new_values[1+lpx_num_cols()];
438 // for (i=0;i<=lpx_num_cols();++i){
441 // for (i=1;i<=length;++i){
442 // new_values[indices[i]]=values[i];
445 // for (i=0;i<=lpx_num_cols();++i){
446 // lpx_set_obj_coef(lp, i, new_values[i]);
450 LpGlpk::SolveExitStatus LpGlpk::_solve()
452 int i = lpx_simplex(lp);
461 LpGlpk::Value LpGlpk::_getPrimal(int i)
463 return lpx_get_col_prim(lp,i);
466 LpGlpk::Value LpGlpk::_getDual(int i)
468 return lpx_get_row_dual(lp,i);
471 LpGlpk::Value LpGlpk::_getPrimalValue()
473 return lpx_get_obj_val(lp);
475 bool LpGlpk::_isBasicCol(int i) {
476 return (lpx_get_col_stat(lp, i)==LPX_BS);
480 LpGlpk::SolutionStatus LpGlpk::_getPrimalStatus()
482 int stat= lpx_get_status(lp);
484 case LPX_UNDEF://Undefined (no solve has been run yet)
486 case LPX_NOFEAS://There is no feasible solution (primal, I guess)
487 case LPX_INFEAS://Infeasible
489 case LPX_UNBND://Unbounded
491 case LPX_FEAS://Feasible
493 case LPX_OPT://Feasible
496 return UNDEFINED; //to avoid gcc warning
501 LpGlpk::SolutionStatus LpGlpk::_getDualStatus()
503 // std::cout<<"Itt megy: "<<lpx_get_dual_stat(lp)<<std::endl;
504 // std::cout<<"Itt a primal: "<<lpx_get_prim_stat(lp)<<std::endl;
506 switch (lpx_get_dual_stat(lp)) {
507 case LPX_D_UNDEF://Undefined (no solve has been run yet)
509 case LPX_D_NOFEAS://There is no dual feasible solution
510 // case LPX_D_INFEAS://Infeasible
512 case LPX_D_FEAS://Feasible
513 switch (lpx_get_status(lp)) {
522 return UNDEFINED; //to avoid gcc warning
527 LpGlpk::ProblemTypes LpGlpk::_getProblemType()
529 //int stat= lpx_get_status(lp);
530 int statp= lpx_get_prim_stat(lp);
531 int statd= lpx_get_dual_stat(lp);
532 if (statp==LPX_P_FEAS && statd==LPX_D_FEAS)
533 return PRIMAL_DUAL_FEASIBLE;
534 if (statp==LPX_P_FEAS && statd==LPX_D_NOFEAS)
535 return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
536 if (statp==LPX_P_NOFEAS && statd==LPX_D_FEAS)
537 return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;
538 if (statp==LPX_P_NOFEAS && statd==LPX_D_NOFEAS)
539 return PRIMAL_DUAL_INFEASIBLE;
544 void LpGlpk::_setMax()
546 lpx_set_obj_dir(lp, LPX_MAX);
549 void LpGlpk::_setMin()
551 lpx_set_obj_dir(lp, LPX_MIN);
555 void LpGlpk::messageLevel(int m)
557 lpx_set_int_parm(lp, LPX_K_MSGLEV, m);
560 void LpGlpk::presolver(bool b)
562 lpx_set_int_parm(lp, LPX_K_PRESOL, b);
566 } //END OF NAMESPACE LEMON