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, ConstRowIterator b, ConstRowIterator e)
131 std::vector<int> indices;
132 std::vector<Value> values;
134 indices.push_back(0);
137 for(ConstRowIterator 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::_getRowCoeffs(int i, RowIterator b)
147 int length = lpx_get_mat_row(lp, i, 0, 0);
149 std::vector<int> indices(length + 1);
150 std::vector<Value> values(length + 1);
152 lpx_get_mat_row(lp, i, &indices[0], &values[0]);
154 for (int i = 1; i <= length; ++i) {
155 *b = std::make_pair(indices[i], values[i]);
160 void LpGlpk::_setColCoeffs(int i, ConstColIterator b, ConstColIterator e) {
162 std::vector<int> indices;
163 std::vector<Value> values;
165 indices.push_back(0);
168 for(ConstColIterator it=b; it!=e; ++it) {
169 indices.push_back(it->first);
170 values.push_back(it->second);
173 lpx_set_mat_col(lp, i, values.size() - 1, &indices[0], &values[0]);
176 void LpGlpk::_getColCoeffs(int i, ColIterator b)
178 int length = lpx_get_mat_col(lp, i, 0, 0);
180 std::vector<int> indices(length + 1);
181 std::vector<Value> values(length + 1);
183 lpx_get_mat_col(lp, i, &indices[0], &values[0]);
185 for (int i = 1; i <= length; ++i) {
186 *b = std::make_pair(indices[i], values[i]);
191 void LpGlpk::_setCoeff(int row, int col, Value value)
194 if (lpx_get_num_cols(lp) < lpx_get_num_rows(lp)) {
196 int length=lpx_get_mat_row(lp, row, 0, 0);
198 std::vector<int> indices(length + 2);
199 std::vector<Value> values(length + 2);
201 lpx_get_mat_row(lp, row, &indices[0], &values[0]);
203 //The following code does not suppose that the elements of the
204 //array indices are sorted
206 for (int i = 1; i <= length; ++i) {
207 if (indices[i]==col){
216 values[length]=value;
219 lpx_set_mat_row(lp, row, length, &indices[0], &values[0]);
223 int length=lpx_get_mat_col(lp, col, 0, 0);
225 std::vector<int> indices(length + 2);
226 std::vector<Value> values(length + 2);
228 lpx_get_mat_col(lp, col, &indices[0], &values[0]);
230 //The following code does not suppose that the elements of the
231 //array indices are sorted
233 for (int i = 1; i <= length; ++i) {
234 if (indices[i]==col){
243 values[length]=value;
246 lpx_set_mat_col(lp, col, length, &indices[0], &values[0]);
250 LpGlpk::Value LpGlpk::_getCoeff(int row, int col)
253 int length=lpx_get_mat_row(lp, row, 0, 0);
255 std::vector<int> indices(length + 1);
256 std::vector<Value> values(length + 1);
258 lpx_get_mat_row(lp, row, &indices[0], &values[0]);
260 //The following code does not suppose that the elements of the
261 //array indices are sorted
262 for (int i = 1; i <= length; ++i) {
263 if (indices[i]==col){
272 void LpGlpk::_setColLowerBound(int i, Value lo)
277 int b=lpx_get_col_type(lp, i);
278 double up=lpx_get_col_ub(lp, i);
283 lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
289 lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
298 lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
304 lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
306 lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
315 LpGlpk::Value LpGlpk::_getColLowerBound(int i)
317 int b=lpx_get_col_type(lp, i);
322 return lpx_get_col_lb(lp, i);
328 void LpGlpk::_setColUpperBound(int i, Value up)
333 int b=lpx_get_col_type(lp, i);
334 double lo=lpx_get_col_lb(lp, i);
341 lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
345 lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
353 lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
356 lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
362 lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
364 lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
372 LpGlpk::Value LpGlpk::_getColUpperBound(int i)
374 int b=lpx_get_col_type(lp, i);
379 return lpx_get_col_ub(lp, i);
385 void LpGlpk::_setRowBounds(int i, Value lb, Value ub)
388 if (lb==INF || ub==-INF) {
394 lpx_set_row_bnds(lp, i, LPX_FR, lb, ub);
397 lpx_set_row_bnds(lp, i, LPX_UP, lb, ub);
402 lpx_set_row_bnds(lp, i, LPX_LO, lb, ub);
407 lpx_set_row_bnds(lp, i, LPX_FX, lb, ub);
410 lpx_set_row_bnds(lp, i, LPX_DB, lb, ub);
417 void LpGlpk::_getRowBounds(int i, Value &lb, Value &ub)
420 int b=lpx_get_row_type(lp, i);
427 lb=lpx_get_row_lb(lp, i);
436 ub=lpx_get_row_ub(lp, i);
441 void LpGlpk::_setObjCoeff(int i, Value obj_coef)
443 //i=0 means the constant term (shift)
444 lpx_set_obj_coef(lp, i, obj_coef);
447 LpGlpk::Value LpGlpk::_getObjCoeff(int i){
448 //i=0 means the constant term (shift)
449 return lpx_get_obj_coef(lp, i);
452 void LpGlpk::_clearObj()
454 for (int i=0;i<=lpx_get_num_cols(lp);++i){
455 lpx_set_obj_coef(lp, i, 0);
459 LpGlpk::SolveExitStatus LpGlpk::_solve()
461 // A way to check the problem to be solved
462 //lpx_write_cpxlp(lp,"naittvan.cpx");
465 int i = lpx_simplex(lp);
475 LpGlpk::Value LpGlpk::_getPrimal(int i)
477 return lpx_get_col_prim(lp,i);
480 LpGlpk::Value LpGlpk::_getDual(int i)
482 return lpx_get_row_dual(lp,i);
485 LpGlpk::Value LpGlpk::_getPrimalValue()
487 return lpx_get_obj_val(lp);
489 bool LpGlpk::_isBasicCol(int i) {
490 return (lpx_get_col_stat(lp, i)==LPX_BS);
494 LpGlpk::SolutionStatus LpGlpk::_getPrimalStatus()
496 int stat= lpx_get_status(lp);
498 case LPX_UNDEF://Undefined (no solve has been run yet)
500 case LPX_NOFEAS://There is no feasible solution (primal, I guess)
501 case LPX_INFEAS://Infeasible
503 case LPX_UNBND://Unbounded
505 case LPX_FEAS://Feasible
507 case LPX_OPT://Feasible
510 return UNDEFINED; //to avoid gcc warning
515 LpGlpk::SolutionStatus LpGlpk::_getDualStatus()
517 // std::cout<<"Itt megy: "<<lpx_get_dual_stat(lp)<<std::endl;
518 // std::cout<<"Itt a primal: "<<lpx_get_prim_stat(lp)<<std::endl;
520 switch (lpx_get_dual_stat(lp)) {
521 case LPX_D_UNDEF://Undefined (no solve has been run yet)
523 case LPX_D_NOFEAS://There is no dual feasible solution
524 // case LPX_D_INFEAS://Infeasible
526 case LPX_D_FEAS://Feasible
527 switch (lpx_get_status(lp)) {
536 return UNDEFINED; //to avoid gcc warning
541 LpGlpk::ProblemTypes LpGlpk::_getProblemType()
543 //int stat= lpx_get_status(lp);
544 int statp= lpx_get_prim_stat(lp);
545 int statd= lpx_get_dual_stat(lp);
546 if (statp==LPX_P_FEAS && statd==LPX_D_FEAS)
547 return PRIMAL_DUAL_FEASIBLE;
548 if (statp==LPX_P_FEAS && statd==LPX_D_NOFEAS)
549 return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
550 if (statp==LPX_P_NOFEAS && statd==LPX_D_FEAS)
551 return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;
552 if (statp==LPX_P_NOFEAS && statd==LPX_D_NOFEAS)
553 return PRIMAL_DUAL_INFEASIBLE;
558 void LpGlpk::_setMax()
560 lpx_set_obj_dir(lp, LPX_MAX);
563 void LpGlpk::_setMin()
565 lpx_set_obj_dir(lp, LPX_MIN);
568 bool LpGlpk::_isMax()
570 return (lpx_get_obj_dir(lp)==LPX_MAX);
575 void LpGlpk::messageLevel(int m)
577 lpx_set_int_parm(lp, LPX_K_MSGLEV, m);
580 void LpGlpk::presolver(bool b)
582 lpx_set_int_parm(lp, LPX_K_PRESOL, b);
586 } //END OF NAMESPACE LEMON