1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2008
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
21 #include <lemon/lp_cplex.h>
24 #include <ilcplex/cplex.h>
29 ///\brief Implementation of the LEMON-CPLEX lp solver interface.
33 // env = CPXopenCPLEXdevelop(&status);
34 env = CPXopenCPLEX(&status);
35 lp = CPXcreateprob(env, &status, "LP problem");
38 LpCplex::LpCplex(const LpCplex& cplex) : LpSolverBase() {
39 env = CPXopenCPLEX(&status);
40 lp = CPXcloneprob(env, cplex.lp, &status);
50 LpSolverBase* LpCplex::_newLp()
52 //The first approach opens a new environment
56 LpSolverBase* LpCplex::_copyLp() {
57 return new LpCplex(*this);
60 int LpCplex::_addCol()
62 int i = CPXgetnumcols(env, lp);
66 status = CPXnewcols(env, lp, 1, NULL, lb, ub, NULL, NULL);
71 int LpCplex::_addRow()
73 //We want a row that is not constrained
75 sense[0]='L';//<= constraint
78 int i = CPXgetnumrows(env, lp);
79 status = CPXnewrows(env, lp, 1, rhs, sense, NULL, NULL);
84 void LpCplex::_eraseCol(int i) {
85 CPXdelcols(env, lp, i, i);
88 void LpCplex::_eraseRow(int i) {
89 CPXdelrows(env, lp, i, i);
92 void LpCplex::_getColName(int col, std::string &name) const
96 CPXgetcolname(env, lp, 0, 0, 0, &storespace, col, col);
97 if (storespace == 0) {
103 std::vector<char> buf(storespace);
106 ///\bug return code unchecked for error
107 CPXgetcolname(env, lp, names, &*buf.begin(), storespace,
108 &dontcare, col, col);
112 void LpCplex::_setColName(int col, const std::string &name)
116 names[0] = const_cast<char*>(name.c_str());
117 ///\bug return code unchecked for error
118 CPXchgcolname(env, lp, 1, &col, names);
121 int LpCplex::_colByName(const std::string& name) const
124 if (CPXgetcolindex(env, lp,
125 const_cast<char*>(name.c_str()), &index) == 0) {
131 ///\warning Data at index 0 is ignored in the arrays.
132 void LpCplex::_setRowCoeffs(int i, ConstRowIterator b, ConstRowIterator e)
134 std::vector<int> indices;
135 std::vector<int> rowlist;
136 std::vector<Value> values;
138 for(ConstRowIterator it=b; it!=e; ++it) {
139 indices.push_back(it->first);
140 values.push_back(it->second);
141 rowlist.push_back(i);
144 status = CPXchgcoeflist(env, lp, values.size(),
145 &rowlist[0], &indices[0], &values[0]);
148 void LpCplex::_getRowCoeffs(int i, RowIterator b) const {
149 int tmp1, tmp2, tmp3, length;
150 CPXgetrows(env, lp, &tmp1, &tmp2, 0, 0, 0, &length, i, i);
153 std::vector<int> indices(length);
154 std::vector<double> values(length);
156 CPXgetrows(env, lp, &tmp1, &tmp2, &indices[0], &values[0],
157 length, &tmp3, i, i);
159 for (int i = 0; i < length; ++i) {
160 *b = std::make_pair(indices[i], values[i]);
167 void LpCplex::_setColCoeffs(int i, ConstColIterator b, ConstColIterator e)
169 std::vector<int> indices;
170 std::vector<int> collist;
171 std::vector<Value> values;
173 for(ConstColIterator it=b; it!=e; ++it) {
174 indices.push_back(it->first);
175 values.push_back(it->second);
176 collist.push_back(i);
179 status = CPXchgcoeflist(env, lp, values.size(),
180 &indices[0], &collist[0], &values[0]);
183 void LpCplex::_getColCoeffs(int i, ColIterator b) const {
185 int tmp1, tmp2, tmp3, length;
186 CPXgetcols(env, lp, &tmp1, &tmp2, 0, 0, 0, &length, i, i);
189 std::vector<int> indices(length);
190 std::vector<double> values(length);
192 CPXgetcols(env, lp, &tmp1, &tmp2, &indices[0], &values[0],
193 length, &tmp3, i, i);
195 for (int i = 0; i < length; ++i) {
196 *b = std::make_pair(indices[i], values[i]);
202 void LpCplex::_setCoeff(int row, int col, Value value)
204 CPXchgcoef(env, lp, row, col, value);
207 LpCplex::Value LpCplex::_getCoeff(int row, int col) const
209 LpCplex::Value value;
210 CPXgetcoef(env, lp, row, col, &value);
214 void LpCplex::_setColLowerBound(int i, Value value)
222 status = CPXchgbds(env, lp, 1, indices, lu, bd);
226 LpCplex::Value LpCplex::_getColLowerBound(int i) const
229 CPXgetlb (env, lp, &x, i, i);
230 if (x <= -CPX_INFBOUND) x = -INF;
234 void LpCplex::_setColUpperBound(int i, Value value)
242 status = CPXchgbds(env, lp, 1, indices, lu, bd);
245 LpCplex::Value LpCplex::_getColUpperBound(int i) const
248 CPXgetub (env, lp, &x, i, i);
249 if (x >= CPX_INFBOUND) x = INF;
253 //This will be easier to implement
254 void LpCplex::_setRowBounds(int i, Value lb, Value ub)
257 if (lb==INF || ub==-INF) {
268 CPXchgsense(env, lp, cnt, indices, sense);
269 CPXchgcoef(env, lp, i, -1, ub);
275 CPXchgsense(env, lp, cnt, indices, sense);
276 CPXchgcoef(env, lp, i, -1, lb);
281 CPXchgsense(env, lp, cnt, indices, sense);
282 CPXchgcoef(env, lp, i, -1, lb);
286 CPXchgsense(env, lp, cnt, indices, sense);
287 CPXchgcoef(env, lp, i, -1, lb);
288 CPXchgcoef(env, lp, i, -2, ub-lb);
294 // void LpCplex::_setRowLowerBound(int i, Value value)
296 // //Not implemented, obsolete
299 // void LpCplex::_setRowUpperBound(int i, Value value)
301 // //Not implemented, obsolete
302 // // //TODO Ezt kell meg megirni
303 // // //type of the problem
305 // // status = CPXgetsense(env, lp, sense, i, i);
307 // // status = CPXgetrhs(env, lp, rhs, i, i);
309 // // switch (sense[0]) {
310 // // case 'L'://<= constraint
312 // // case 'E'://= constraint
314 // // case 'G'://>= constraint
316 // // case 'R'://ranged constraint
322 // // status = CPXchgcoef(env, lp, i, -2, value_rng);
325 void LpCplex::_getRowBounds(int i, Value &lb, Value &ub) const
328 CPXgetsense(env, lp, &sense,i,i);
334 CPXgetcoef(env, lp, i, -1, &ub);
337 CPXgetcoef(env, lp, i, -1, &lb);
340 CPXgetcoef(env, lp, i, -1, &lb);
344 CPXgetcoef(env, lp, i, -1, &lb);
346 CPXgetcoef(env, lp, i, -2, &x);
352 void LpCplex::_setObjCoeff(int i, Value obj_coef)
354 CPXchgcoef(env, lp, -1, i, obj_coef);
357 LpCplex::Value LpCplex::_getObjCoeff(int i) const
360 CPXgetcoef(env, lp, -1, i, &x);
364 void LpCplex::_clearObj()
366 for (int i=0;i< CPXgetnumcols(env, lp);++i){
367 CPXchgcoef(env, lp, -1, i, 0);
371 // The routine returns zero unless an error occurred during the
372 // optimization. Examples of errors include exhausting available
373 // memory (CPXERR_NO_MEMORY) or encountering invalid data in the
374 // CPLEX problem object (CPXERR_NO_PROBLEM). Exceeding a
375 // user-specified CPLEX limit, or proving the model infeasible or
376 // unbounded, are not considered errors. Note that a zero return
377 // value does not necessarily mean that a solution exists. Use query
378 // routines CPXsolninfo, CPXgetstat, and CPXsolution to obtain
379 // further information about the status of the optimization.
380 LpCplex::SolveExitStatus LpCplex::_solve()
383 status = CPXlpopt(env, lp);
384 //status = CPXprimopt(env, lp);
385 #if CPX_VERSION >= 800
392 switch (CPXgetstat(env, lp))
394 case CPX_STAT_OPTIMAL:
395 case CPX_STAT_INFEASIBLE:
396 case CPX_STAT_UNBOUNDED:
404 //We want to exclude some cases
405 switch (CPXgetstat(env, lp)){
407 case CPX_IT_LIM_FEAS:
408 case CPX_IT_LIM_INFEAS:
409 case CPX_TIME_LIM_FEAS:
410 case CPX_TIME_LIM_INFEAS:
422 LpCplex::Value LpCplex::_getPrimal(int i) const
425 CPXgetx(env, lp, &x, i, i);
429 LpCplex::Value LpCplex::_getDual(int i) const
432 CPXgetpi(env, lp, &y, i, i);
436 LpCplex::Value LpCplex::_getPrimalValue() const
439 //method = CPXgetmethod (env, lp);
440 //printf("CPXgetprobtype %d \n",CPXgetprobtype(env,lp));
441 CPXgetobjval(env, lp, &objval);
442 //printf("Objective value: %g \n",objval);
445 bool LpCplex::_isBasicCol(int i) const
447 std::vector<int> cstat(CPXgetnumcols(env, lp));
448 CPXgetbase(env, lp, &*cstat.begin(), NULL);
449 return (cstat[i]==CPX_BASIC);
452 //7.5-os cplex statusai (Vigyazat: a 9.0-asei masok!)
453 // This table lists the statuses, returned by the CPXgetstat()
454 // routine, for solutions to LP problems or mixed integer problems. If
455 // no solution exists, the return value is zero.
457 // For Simplex, Barrier
459 // Optimal solution found
461 // Problem infeasible
465 // Objective limit exceeded in Phase II
467 // Iteration limit exceeded in Phase II
468 // 6 CPX_IT_LIM_INFEAS
469 // Iteration limit exceeded in Phase I
470 // 7 CPX_TIME_LIM_FEAS
471 // Time limit exceeded in Phase II
472 // 8 CPX_TIME_LIM_INFEAS
473 // Time limit exceeded in Phase I
474 // 9 CPX_NUM_BEST_FEAS
475 // Problem non-optimal, singularities in Phase II
476 // 10 CPX_NUM_BEST_INFEAS
477 // Problem non-optimal, singularities in Phase I
478 // 11 CPX_OPTIMAL_INFEAS
479 // Optimal solution found, unscaled infeasibilities
481 // Aborted in Phase II
482 // 13 CPX_ABORT_INFEAS
483 // Aborted in Phase I
484 // 14 CPX_ABORT_DUAL_INFEAS
485 // Aborted in barrier, dual infeasible
486 // 15 CPX_ABORT_PRIM_INFEAS
487 // Aborted in barrier, primal infeasible
488 // 16 CPX_ABORT_PRIM_DUAL_INFEAS
489 // Aborted in barrier, primal and dual infeasible
490 // 17 CPX_ABORT_PRIM_DUAL_FEAS
491 // Aborted in barrier, primal and dual feasible
492 // 18 CPX_ABORT_CROSSOVER
493 // Aborted in crossover
495 // Infeasible or unbounded
499 // Ezeket hova tegyem:
500 // ??case CPX_ABORT_DUAL_INFEAS
501 // ??case CPX_ABORT_CROSSOVER
502 // ??case CPX_INForUNBD
505 //Some more interesting stuff:
507 // CPX_PARAM_LPMETHOD 1062 int LPMETHOD
512 // 4 Standard Barrier
514 // Description: Method for linear optimization.
515 // Determines which algorithm is used when CPXlpopt() (or "optimize"
516 // in the Interactive Optimizer) is called. Currently the behavior of
517 // the "Automatic" setting is that CPLEX simply invokes the dual
518 // simplex method, but this capability may be expanded in the future
519 // so that CPLEX chooses the method based on problem characteristics
520 #if CPX_VERSION < 900
521 void statusSwitch(CPXENVptr env,int& stat){
523 CPXgetintparam (env,CPX_PARAM_LPMETHOD,&lpmethod);
525 if (stat==CPX_UNBOUNDED){
529 if (stat==CPX_INFEASIBLE)
535 void statusSwitch(CPXENVptr,int&){}
538 LpCplex::SolutionStatus LpCplex::_getPrimalStatus() const
540 //Unboundedness not treated well: the following is from cplex 9.0 doc
541 // About Unboundedness
543 // The treatment of models that are unbounded involves a few
544 // subtleties. Specifically, a declaration of unboundedness means that
545 // ILOG CPLEX has determined that the model has an unbounded
546 // ray. Given any feasible solution x with objective z, a multiple of
547 // the unbounded ray can be added to x to give a feasible solution
548 // with objective z-1 (or z+1 for maximization models). Thus, if a
549 // feasible solution exists, then the optimal objective is
550 // unbounded. Note that ILOG CPLEX has not necessarily concluded that
551 // a feasible solution exists. Users can call the routine CPXsolninfo
552 // to determine whether ILOG CPLEX has also concluded that the model
553 // has a feasible solution.
555 int stat = CPXgetstat(env, lp);
556 #if CPX_VERSION >= 800
559 case CPX_STAT_OPTIMAL:
561 case CPX_STAT_UNBOUNDED:
563 case CPX_STAT_INFEASIBLE:
569 statusSwitch(env,stat);
570 //CPXgetstat(env, lp);
571 //printf("A primal status: %d, CPX_OPTIMAL=%d \n",stat,CPX_OPTIMAL);
574 return UNDEFINED; //Undefined
575 case CPX_OPTIMAL://Optimal
577 case CPX_UNBOUNDED://Unbounded
578 return INFEASIBLE;//In case of dual simplex
580 case CPX_INFEASIBLE://Infeasible
581 // case CPX_IT_LIM_INFEAS:
582 // case CPX_TIME_LIM_INFEAS:
583 // case CPX_NUM_BEST_INFEAS:
584 // case CPX_OPTIMAL_INFEAS:
585 // case CPX_ABORT_INFEAS:
586 // case CPX_ABORT_PRIM_INFEAS:
587 // case CPX_ABORT_PRIM_DUAL_INFEAS:
588 return INFINITE;//In case of dual simplex
591 // case CPX_IT_LIM_FEAS:
592 // case CPX_TIME_LIM_FEAS:
593 // case CPX_NUM_BEST_FEAS:
594 // case CPX_ABORT_FEAS:
595 // case CPX_ABORT_PRIM_DUAL_FEAS:
598 return UNDEFINED; //Everything else comes here
604 //9.0-as cplex verzio statusai
605 // CPX_STAT_ABORT_DUAL_OBJ_LIM
606 // CPX_STAT_ABORT_IT_LIM
607 // CPX_STAT_ABORT_OBJ_LIM
608 // CPX_STAT_ABORT_PRIM_OBJ_LIM
609 // CPX_STAT_ABORT_TIME_LIM
610 // CPX_STAT_ABORT_USER
611 // CPX_STAT_FEASIBLE_RELAXED
612 // CPX_STAT_INFEASIBLE
613 // CPX_STAT_INForUNBD
616 // CPX_STAT_OPTIMAL_FACE_UNBOUNDED
617 // CPX_STAT_OPTIMAL_INFEAS
618 // CPX_STAT_OPTIMAL_RELAXED
619 // CPX_STAT_UNBOUNDED
621 LpCplex::SolutionStatus LpCplex::_getDualStatus() const
623 int stat = CPXgetstat(env, lp);
624 #if CPX_VERSION >= 800
627 case CPX_STAT_OPTIMAL:
629 case CPX_STAT_UNBOUNDED:
635 statusSwitch(env,stat);
638 return UNDEFINED; //Undefined
639 case CPX_OPTIMAL://Optimal
644 return UNDEFINED; //Everything else comes here
650 LpCplex::ProblemTypes LpCplex::_getProblemType() const
652 int stat = CPXgetstat(env, lp);
653 #if CPX_VERSION >= 800
656 case CPX_STAT_OPTIMAL:
657 return PRIMAL_DUAL_FEASIBLE;
658 case CPX_STAT_UNBOUNDED:
659 return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
665 case CPX_OPTIMAL://Optimal
666 return PRIMAL_DUAL_FEASIBLE;
668 return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
669 // return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;
670 // return PRIMAL_DUAL_INFEASIBLE;
672 //Seems to be that this is all we can say for sure
681 void LpCplex::_setMax()
683 CPXchgobjsen(env, lp, CPX_MAX);
685 void LpCplex::_setMin()
687 CPXchgobjsen(env, lp, CPX_MIN);
690 bool LpCplex::_isMax() const
692 if (CPXgetobjsen(env, lp)==CPX_MAX)