Consider the CPXMIP_OPTIMAL_TOL status as OPTIMAL too.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
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>
25 #if GLP_MAJOR_VERSION > 4 || (GLP_MAJOR_VERSION == 4 && GLP_MINOR_VERSION > 15)
26 #define LEMON_glp(func) (glp_##func)
27 #define LEMON_lpx(func) (lpx_##func)
29 #define LEMON_GLP(def) (GLP_##def)
30 #define LEMON_LPX(def) (LPX_##def)
34 #define LEMON_glp(func) (lpx_##func)
35 #define LEMON_lpx(func) (lpx_##func)
37 #define LEMON_GLP(def) (LPX_##def)
38 #define LEMON_LPX(def) (LPX_##def)
44 LpGlpk::LpGlpk() : Parent() {
46 rows = _lp_bits::LpId(1);
47 cols = _lp_bits::LpId(1);
48 lp = LEMON_glp(create_prob)();
49 LEMON_glp(create_index)(lp);
50 LEMON_lpx(set_int_parm)(lp, LEMON_LPX(K_DUAL), 1);
54 LpGlpk::LpGlpk(const LpGlpk &glp) : Parent() {
56 rows = _lp_bits::LpId(1);
57 cols = _lp_bits::LpId(1);
58 lp = LEMON_glp(create_prob)();
59 LEMON_glp(create_index)(lp);
60 ///\todo control function for this:
61 LEMON_lpx(set_int_parm)(lp, LEMON_LPX(K_DUAL), 1);
63 //Coefficient matrix, row bounds
64 LEMON_glp(add_rows)(lp, LEMON_glp(get_num_rows)(glp.lp));
65 LEMON_glp(add_cols)(lp, LEMON_glp(get_num_cols)(glp.lp));
67 int ind[1+LEMON_glp(get_num_cols)(glp.lp)];
68 Value val[1+LEMON_glp(get_num_cols)(glp.lp)];
69 for (int i=1;i<=LEMON_glp(get_num_rows)(glp.lp);++i)
71 len=LEMON_glp(get_mat_row)(glp.lp,i,ind,val);
72 LEMON_glp(set_mat_row)(lp, i,len,ind,val);
73 LEMON_glp(set_row_bnds)(lp,i,
74 LEMON_glp(get_row_type)(glp.lp,i),
75 LEMON_glp(get_row_lb)(glp.lp,i),
76 LEMON_glp(get_row_ub)(glp.lp,i));
79 //Objective function, coloumn bounds
80 LEMON_glp(set_obj_dir)(lp, LEMON_glp(get_obj_dir)(glp.lp));
81 //Objectif function's constant term treated separately
82 LEMON_glp(set_obj_coef)(lp,0,LEMON_glp(get_obj_coef)(glp.lp,0));
83 for (int i=1;i<=LEMON_glp(get_num_cols)(glp.lp);++i)
85 LEMON_glp(set_obj_coef)(lp,i,
86 LEMON_glp(get_obj_coef)(glp.lp,i));
87 LEMON_glp(set_col_bnds)(lp,i,
88 LEMON_glp(get_col_type)(glp.lp,i),
89 LEMON_glp(get_col_lb)(glp.lp,i),
90 LEMON_glp(get_col_ub)(glp.lp,i));
95 LEMON_glp(delete_prob)(lp);
98 int LpGlpk::_addCol() {
99 int i=LEMON_glp(add_cols)(lp, 1);
100 LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(FR), 0.0, 0.0);
108 LpSolverBase &LpGlpk::_newLp()
110 LpGlpk* newlp=new LpGlpk;
116 LpSolverBase &LpGlpk::_copyLp()
118 LpGlpk* newlp=new LpGlpk(*this);
122 int LpGlpk::_addRow() {
123 int i=LEMON_glp(add_rows)(lp, 1);
129 void LpGlpk::_eraseCol(int i) {
132 LEMON_glp(del_cols)(lp, 1, ca);
136 void LpGlpk::_eraseRow(int i) {
139 LEMON_glp(del_rows)(lp, 1, ra);
143 void LpGlpk::_getColName(int c, std::string & name) const
146 const char *n = LEMON_glp(get_col_name)(lp,c);
151 void LpGlpk::_setColName(int c, const std::string & name)
153 LEMON_glp(set_col_name)(lp,c,const_cast<char*>(name.c_str()));
157 int LpGlpk::_colByName(const std::string& name) const
159 int k = LEMON_glp(find_col)(lp, const_cast<char*>(name.c_str()));
160 return k > 0 ? k : -1;
164 void LpGlpk::_setRowCoeffs(int i, ConstRowIterator b, ConstRowIterator e)
166 std::vector<int> indices;
167 std::vector<Value> values;
169 indices.push_back(0);
172 for(ConstRowIterator it=b; it!=e; ++it) {
173 indices.push_back(it->first);
174 values.push_back(it->second);
177 LEMON_glp(set_mat_row)(lp, i, values.size() - 1,
178 &indices[0], &values[0]);
183 void LpGlpk::_getRowCoeffs(int ix, RowIterator b) const
185 int length = LEMON_glp(get_mat_row)(lp, ix, 0, 0);
187 std::vector<int> indices(length + 1);
188 std::vector<Value> values(length + 1);
190 LEMON_glp(get_mat_row)(lp, ix, &indices[0], &values[0]);
192 for (int i = 1; i <= length; ++i) {
193 *b = std::make_pair(indices[i], values[i]);
198 void LpGlpk::_setColCoeffs(int ix, ConstColIterator b, ConstColIterator e) {
200 std::vector<int> indices;
201 std::vector<Value> values;
203 indices.push_back(0);
206 for(ConstColIterator it=b; it!=e; ++it) {
207 indices.push_back(it->first);
208 values.push_back(it->second);
211 LEMON_glp(set_mat_col)(lp, ix, values.size() - 1,
212 &indices[0], &values[0]);
217 void LpGlpk::_getColCoeffs(int ix, ColIterator b) const
219 int length = LEMON_glp(get_mat_col)(lp, ix, 0, 0);
221 std::vector<int> indices(length + 1);
222 std::vector<Value> values(length + 1);
224 LEMON_glp(get_mat_col)(lp, ix, &indices[0], &values[0]);
226 for (int i = 1; i <= length; ++i) {
227 *b = std::make_pair(indices[i], values[i]);
232 void LpGlpk::_setCoeff(int ix, int jx, Value value)
235 if (LEMON_glp(get_num_cols)(lp) < LEMON_glp(get_num_rows)(lp)) {
237 int length=LEMON_glp(get_mat_row)(lp, ix, 0, 0);
239 std::vector<int> indices(length + 2);
240 std::vector<Value> values(length + 2);
242 LEMON_glp(get_mat_row)(lp, ix, &indices[0], &values[0]);
244 //The following code does not suppose that the elements of the
245 //array indices are sorted
247 for (int i = 1; i <= length; ++i) {
257 values[length]=value;
260 LEMON_glp(set_mat_row)(lp, ix, length, &indices[0], &values[0]);
264 int length=LEMON_glp(get_mat_col)(lp, jx, 0, 0);
266 std::vector<int> indices(length + 2);
267 std::vector<Value> values(length + 2);
269 LEMON_glp(get_mat_col)(lp, jx, &indices[0], &values[0]);
271 //The following code does not suppose that the elements of the
272 //array indices are sorted
274 for (int i = 1; i <= length; ++i) {
284 values[length]=value;
287 LEMON_glp(set_mat_col)(lp, jx, length, &indices[0], &values[0]);
293 LpGlpk::Value LpGlpk::_getCoeff(int ix, int jx) const
296 int length=LEMON_glp(get_mat_row)(lp, ix, 0, 0);
298 std::vector<int> indices(length + 1);
299 std::vector<Value> values(length + 1);
301 LEMON_glp(get_mat_row)(lp, ix, &indices[0], &values[0]);
303 //The following code does not suppose that the elements of the
304 //array indices are sorted
305 for (int i = 1; i <= length; ++i) {
315 void LpGlpk::_setColLowerBound(int i, Value lo)
320 int b=LEMON_glp(get_col_type)(lp, i);
321 double up=LEMON_glp(get_col_ub)(lp, i);
326 LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(FR), lo, up);
332 LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(UP), lo, up);
341 LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(LO), lo, up);
347 LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(FX), lo, up);
349 LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(DB), lo, up);
359 LpGlpk::Value LpGlpk::_getColLowerBound(int i) const
361 int b=LEMON_glp(get_col_type)(lp, i);
366 return LEMON_glp(get_col_lb)(lp, i);
372 void LpGlpk::_setColUpperBound(int i, Value up)
377 int b=LEMON_glp(get_col_type)(lp, i);
378 double lo=LEMON_glp(get_col_lb)(lp, i);
385 LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(FR), lo, up);
389 LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(LO), lo, up);
397 LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(UP), lo, up);
400 LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(UP), lo, up);
406 LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(FX), lo, up);
408 LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(DB), lo, up);
418 LpGlpk::Value LpGlpk::_getColUpperBound(int i) const
420 int b=LEMON_glp(get_col_type)(lp, i);
425 return LEMON_glp(get_col_ub)(lp, i);
431 void LpGlpk::_setRowBounds(int i, Value lb, Value ub)
434 if (lb==INF || ub==-INF) {
440 LEMON_glp(set_row_bnds)(lp, i, LEMON_GLP(FR), lb, ub);
443 LEMON_glp(set_row_bnds)(lp, i, LEMON_GLP(UP), lb, ub);
448 LEMON_glp(set_row_bnds)(lp, i, LEMON_GLP(LO), lb, ub);
453 LEMON_glp(set_row_bnds)(lp, i, LEMON_GLP(FX), lb, ub);
456 LEMON_glp(set_row_bnds)(lp, i, LEMON_GLP(DB), lb, ub);
464 void LpGlpk::_getRowBounds(int i, Value &lb, Value &ub) const
467 int b=LEMON_glp(get_row_type)(lp, i);
474 lb=LEMON_glp(get_row_lb)(lp, i);
483 ub=LEMON_glp(get_row_ub)(lp, i);
488 void LpGlpk::_setObjCoeff(int i, Value obj_coef)
490 //i=0 means the constant term (shift)
491 LEMON_glp(set_obj_coef)(lp, i, obj_coef);
496 LpGlpk::Value LpGlpk::_getObjCoeff(int i) const {
497 //i=0 means the constant term (shift)
498 return LEMON_glp(get_obj_coef)(lp, i);
501 void LpGlpk::_clearObj()
503 for (int i=0;i<=LEMON_glp(get_num_cols)(lp);++i){
504 LEMON_glp(set_obj_coef)(lp, i, 0);
510 LpGlpk::SolveExitStatus LpGlpk::_solve()
512 // A way to check the problem to be solved
513 //LEMON_glp(write_cpxlp(lp,"naittvan.cpx");
515 LEMON_lpx(std_basis)(lp);
516 int i = LEMON_lpx(simplex)(lp);
519 case LEMON_LPX(E_OK):
527 LpGlpk::Value LpGlpk::_getPrimal(int i) const
529 return LEMON_glp(get_col_prim)(lp,i);
532 LpGlpk::Value LpGlpk::_getDual(int i) const
534 return LEMON_glp(get_row_dual)(lp,i);
537 LpGlpk::Value LpGlpk::_getPrimalValue() const
539 return LEMON_glp(get_obj_val)(lp);
541 bool LpGlpk::_isBasicCol(int i) const
543 return (LEMON_glp(get_col_stat)(lp, i)==LEMON_GLP(BS));
547 LpGlpk::SolutionStatus LpGlpk::_getPrimalStatus() const
549 if (!solved) return UNDEFINED;
550 int stat= LEMON_lpx(get_status)(lp);
552 case LEMON_LPX(UNDEF)://Undefined (no solve has been run yet)
554 case LEMON_LPX(NOFEAS)://There is no feasible solution (primal, I guess)
555 case LEMON_LPX(INFEAS)://Infeasible
557 case LEMON_LPX(UNBND)://Unbounded
559 case LEMON_LPX(FEAS)://Feasible
561 case LEMON_LPX(OPT)://Feasible
564 return UNDEFINED; //to avoid gcc warning
569 LpGlpk::SolutionStatus LpGlpk::_getDualStatus() const
571 if (!solved) return UNDEFINED;
572 switch (LEMON_lpx(get_dual_stat)(lp)) {
573 case LEMON_LPX(D_UNDEF)://Undefined (no solve has been run yet)
575 case LEMON_LPX(D_NOFEAS)://There is no dual feasible solution
576 // case LEMON_LPX(D_INFEAS://Infeasible
578 case LEMON_LPX(D_FEAS)://Feasible
579 switch (LEMON_lpx(get_status)(lp)) {
580 case LEMON_LPX(NOFEAS):
588 return UNDEFINED; //to avoid gcc warning
593 LpGlpk::ProblemTypes LpGlpk::_getProblemType() const
595 if (!solved) return UNKNOWN;
596 //int stat= LEMON_glp(get_status(lp);
597 int statp= LEMON_lpx(get_prim_stat)(lp);
598 int statd= LEMON_lpx(get_dual_stat)(lp);
599 if (statp==LEMON_LPX(P_FEAS) && statd==LEMON_LPX(D_FEAS))
600 return PRIMAL_DUAL_FEASIBLE;
601 if (statp==LEMON_LPX(P_FEAS) && statd==LEMON_LPX(D_NOFEAS))
602 return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
603 if (statp==LEMON_LPX(P_NOFEAS) && statd==LEMON_LPX(D_FEAS))
604 return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;
605 if (statp==LEMON_LPX(P_NOFEAS) && statd==LEMON_LPX(D_NOFEAS))
606 return PRIMAL_DUAL_INFEASIBLE;
611 void LpGlpk::_setMax()
614 LEMON_glp(set_obj_dir)(lp, LEMON_GLP(MAX));
617 void LpGlpk::_setMin()
620 LEMON_glp(set_obj_dir)(lp, LEMON_GLP(MIN));
623 bool LpGlpk::_isMax() const
625 return (LEMON_glp(get_obj_dir)(lp)==LEMON_GLP(MAX));
630 void LpGlpk::messageLevel(int m)
632 LEMON_lpx(set_int_parm)(lp, LEMON_LPX(K_MSGLEV), m);
635 void LpGlpk::presolver(bool b)
637 LEMON_lpx(set_int_parm)(lp, LEMON_LPX(K_PRESOL), b);
641 } //END OF NAMESPACE LEMON