[Clp] restricted basis entry rule

[John Forrest]

Osman,

It may be a quick question but there is no easy answer.

The outgoing variable is chosen in a fairly complicated way - the main
factor being that large pivot values are preferred to small so you run
into all sorts of acceptability issues.  The work needed to determine
this is fairly compute intensive and would have to be similar to current
code (which could change in the future).

Assuming that in most cases you can find a valid pivot row, given an
incoming variable, this is how I would go about it.

I would add extra functionality on a configure
CXXDEFS="-DCLP_USER_DRIVEN1" in a few places e.g. when testing whether a
particular pivot is allowed in ClpSimplexPrimal::primalRow

#ifdef CLP_USER_DRIVEN1
  if(!userChoiceValid1(this,sequenceOut))
	continue;
#endif
this would probably be in two or three places

and also after primalRow and no pivot found (when would normally be
declared unbounded)

#ifdef CLP_USER_DRIVEN1
  if (!userChoiceValid2(this)) {
	// flag sequenceIn_ as unacceptable inside userChoiceValid2 and go
round again
}
#endif

If you think this is a possible way forward I can add code to Clp/trunk.
It would obviously take several iterations to get it to work as there
will be extra subtleties to consider to do with accuracy, composite
objective function etc.

John Forrest

On Mon, 2011-01-03 at 01:56 -0500, OYO1 at pitt.edu wrote:
> Thank you very much for the answer. I have one more quick question.
> 
> For a given  entering variable, how can I find the leaving variable
> corresponding to that entering variable without actually doing the pivot?
> I mean changing the basis. Is there a built-in function which can do that?
> I just need the index of the leaving variable.
> 
> I need this because in my restricted basis entry rule certain variables
> are allowed to enter the basis only if some other certain variables leave
> the basis in the same iteration.
> 
> I tried primalPivotResult() function of ClpSimplex class, but it does not
> seem to do the trick
> 
> Thanks again.
> 
> Osman
> 
> 
> 
> > On Tue, 2010-12-28 at 01:29 -0500, OYO1 at pitt.edu wrote:
> >> Hi,
> >>
> >> I would like to implement a restricted basis entry rule where the
> >> entering
> >> variable will be the one whose reduced cost is most negative (or some
> >> other rule) provided that its complementary variable is not in the basis
> >> or would leave the basis on the same iteration.
> >>
> >> Obviously, I want to do this for solving a KKT system. Is such a rule
> >> already implemented in CLP? If so, how do I use it? If not, where should
> >> I
> >> start? I do not have any former experience with CLP.
> >
> > To implement such a rule -
> >
> > Let us assume you downloaded Clp and built a debug version e.g. created
> > a directory debug and in that directory did
> > ../configure --enable-debug
> > and
> > make install
> >
> > Go to debug/Clp/examples, copy Clp/examples/minimum.cpp as test.cpp
> > check that works with
> > make DRIVER=test
> > and
> > test .../Netlib/25fv47.mps
> >
> > modify test.cpp and add before model.primal();
> >  ClpPrimalColumnDantzig dantzig;
> >
> > model.setPrimalColumnPivotAlgorithm(dantzig);
> >
> > do make and test again to check still works (should be a bit slower)
> >
> > Copy ClpPrimalColumnDantzig.?pp as ClpPrimalColumnKKT.?pp and
> > edit all occurrences of Dantzig to KKT (and in test.cpp)
> >
> > add
> > ClpPrimalColumnKKT.o
> > to OBJS list in Makefile
> >
> > do make and test - results should be same as last run.
> >
> > Now you are ready to modify ClpPrimalColumnKKT.?pp to change which
> > incoming variables are allowed.
> >
> > Good Luck (instructions are approximate).
> >>
> >> Also, is there a CLP example source code for solving linear programs
> >> with
> >> quadratic objectives?
> >>
> >
> > Try Clp/examples/testQP.cpp
> >
> > with no arguments it should solve a small problem using interior point
> > method.  Or give it a model (with objective specified by QUADOBJ in mps
> > file) to use simplex.
> >
> > Hope that helps
> >
> > John Forrest
> >
> > _______________________________________________
> > Clp mailing list
> > Clp at list.coin-or.org
> > http://list.coin-or.org/mailman/listinfo/clp
> >
> 
> 
> Osman Y. Ozaltin
> PhD Candidate
> 1048 Benedum Hall
> Department of Industrial Engineering
> University of Pittsburgh
> Pittsburgh PA 15261
> URL. www.pitt.edu/~oyo1
> E-mail. oyo1 at pitt.edu
> Phone. 724-234-8490
> 
> _______________________________________________
> Clp mailing list
> Clp at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/clp
>