[Coin-lpsolver] A bug. Custom strong branching

Mon Sep 24 07:53:04 EDT 2007

Dear Developers,

thank you for the hint, my first example was really infeasible.

But the small example is a bug, because after the last primal(), the LP 
value should be 9 again as in the initial model.
Indeed, adding a column and setting all var bounds to MAX we obtain just 
a model which extends the first one!

However, for custom strong branching I decided to save factorization. I 
save also var status array and the pivot array. Is that enough or maybe 
too much? Moreover, to access the pivot array I had to derive a class 
from ClpSimplex... ?

The whole example illustrating the bug and factorization saving is below:

File strBr_1.mps:
NAME          BLANK  
ROWS
 N  OBJROW
 E  R0000000
 E  R0000001
 E  R0000002
COLUMNS
    C0000000  OBJROW    100000.        R0000000  1.         
    C0000001  OBJROW    100000.        R0000001  1.         
    C0000002  OBJROW    100000.        R0000002  1.         
    C0000003  OBJROW    1.             R0000001  1.         
    C0000003  R0000002  1.         
    C0000004  OBJROW    1.             R0000000  1.         
    C0000004  R0000002  1.         
    C0000005  OBJROW    1.             R0000002  1.         
RHS
    RHS       R0000000  3.             R0000001  5.         
    RHS       R0000002  9.         
ENDATA

#include "ClpInterior.hpp"
#include "ClpSimplex.hpp"
#include "ClpCholeskyWssmp.hpp"
#include "ClpCholeskyDense.hpp"
#include "ClpFactorization.hpp"
#include <iostream>
#include <vector>
using namespace std;

class ClpWrap : public ClpSimplex {
public:
  struct SaveWarmStart {
    ClpFactorization fct;
//    vector<double> sol ;
    vector<unsigned char> statCol, statRow;
    // no bounds...
    vector<int> piv;
  };
  void markWarmStart(SaveWarmStart& sws) {
    cout << "Start save warm start.";
    sws.fct = (*factorization_);
//    sol.assign(solution_, solution_ + numberRows_+numberColumns_);
    sws.statCol.assign(status_,status_ + numberColumns_);
    sws.statRow.assign(status_,status_ + numberRows_);
    sws.piv.assign(pivotVariable_, pivotVariable_ + numberRows_);
  }
  void restoreWarmStart(SaveWarmStart& sws) {
//    copy(sol.begin()
    copy(sws.statCol.begin(), sws.statCol.end(), status_);
    fill(status_ + sws.statCol.size(), status_ + numberColumns_, 0);
    copy(sws.statRow.begin(), sws.statRow.end(), status_ + 
numberColumns_); // assume no cuts added
    copy(sws.piv.begin(), sws.piv.end(), pivotVariable_);
    delete factorization_;
    factorization_ = new ClpFactorization(sws.fct);
  }
};
void PrintSol(ClpSimplex & model) {
  cout << "Primal sol: ";
  for(size_t j=0;j<model.getNumCols();++j) cout << 
model.getColSolution()[j] << ' ';
  cout << endl;
  cout << "Dual sol: ";
  for(size_t j=0;j<model.getNumRows();++j) cout << 
model.dualRowSolution()[j] << ' ';
  cout << endl;
}
int main (int argc, const char *argv[])
{
  ClpWrap model;
  int status;
  status=model.readMps("strBr_1.mps");
  if (status) {
    printf("errors on input\n");
    cin.get();
    exit(77);
  }
  model.initialSolve();
  model.primal(0,7);
  double saveObj = model.getObjValue();

  ClpWrap::SaveWarmStart sws;
  model.markWarmStart(sws);
  model.setColUpper(4,0.0);
  model.dual(0,7);
  double saveObj1 = model.getObjValue();
  PrintSol(model);

  int i=0; double coef = 1.0;
  model.addColumn(1, &i, &coef, 0.0, 1e100, 1.0);
  model.primal(0,7);
  model.setColUpper(4,1e100);
  model.writeMps("modif2.mps");
  model.primal(0,7);
  double newObj = model.getObjValue();
  if (newObj > saveObj - 1e-6)
    cout << "ERROR!!! The LP value is "<<newObj
    <<", but should be at most "<<saveObj<<endl<<endl;

  model.restoreWarmStart(sws);
  model.setColUpper(4,0.0);
  model.setColUpper(6,0.0);
  model.dual(0,7);
  double newObj1 = model.getObjValue();
  if (fabs(newObj1 - saveObj1) > 1e-6)
    cout << "PROBLEM: Factorization is not properly restored.\
            The LP value is "<<newObj1<<", but should be "<<saveObj1<<endl;
  else
    cout << "YESSSS! Factorization saving seems to work." << endl;
  PrintSol(model);

  std::cin.get();
  return 0;
}   

Sincerely,
Gleb
> Today's Topics:
>
>    1. Re: A bug. Re: Coin-lpsolver Digest, Vol 34, Issue 9
>       (John J Forrest)
>    2. Examples using CLP (CBS) as subroutine (forming the	LP or MIP
>       model from scratch) with Visual C ++ 6 and Visual	Compact Fortran
>       6.6 (Jose Luis Ceciliano Meza)
>    3. Re: Examples using CLP (CBS) as subroutine (forming	the	LP	or
>       MIP model from scratch) with Visual C ++ 6 and Visual	Compact
>       Fortran 6.6 (John J Forrest)
>
>
> ----------------------------------------------------------------------
>
> Message: 1
> Date: Thu, 20 Sep 2007 12:16:32 -0400
> From: John J Forrest <jjforre at us.ibm.com>
> Subject: Re: [Coin-lpsolver] A bug. Re: Coin-lpsolver Digest, Vol 34,
> 	Issue 9
> Cc: coin-lpsolver at list.coin-or.org
> Message-ID:
> 	<OFFA9E2BFD.48B0D9A3-ON8525735C.0058CA52-8525735C.005967B8 at us.ibm.com>
> Content-Type: text/plain; charset="us-ascii"
>
> Gleb,
>
> You have not given enough information to track down your bug.  The matrix 
> you point to has 418 rows and 563 columns (and is infeasible) so I don't 
> see how columns and cuts can alternate.  Adding column C0000050 is fine, 
> adding row R0000050 (with first 51 columns) is infeasible as there are no 
> entries in row.
>
> As to your other reported bug.  I can reproduce in 1.4 but not in 1.5.
>
> I suggest you upgrade to 1.5 and see if this bug also goes away.
>
> John Forrest
>
>   

-- 
Mit freundlichen Gruessen

G. Belov
----------------------------------------------------------------------
Dr. Gleb Belov                                Gleb.Belov at tu-dresden.de
Wiss. Assistent                   http://www.math.tu-dresden.de/~belov
Technische Universitaet Dresden                 Tel: +49 351 463 34186
Institut fuer Numerische Mathematik             Fax: +49 351 463 34268
Mommsenstr. 13                            Tel. priv.:+49 351 3743754
01062 Dresden