Originally posted by: ChiaWeng

I have read an article (www-eio.upc.es/~dbaena/pub/2010/dr2010-01.pdf) where CPLEX was used to calculate the analytic center of a polytope consisting of linear inequalities.
In a typical linear program (e.g. my problem):
c(T) x
Ax<B

According to the authors, if c(T) is set to 0, the solution will be at the analytic center of the inequalities, **if** the barrier method proceeds to solve the problem. For this to work, the authors used the barrier method to solve the lp, and turned off the crossover option and presolve option. They also mentioned in the article that CPLEX did not always find the analytic center for them because there had been excessive presolving. I am now facing such difficulties now. I have turned off presolve, but I noticed that the CPLEX presolve appears to have (correctly) eliminated the problem (see the output below). I would appreciate it if someone could point out the way to go around this, so that CPLEX continues to perform the barrier iteration to get the analytic center.

status = CPXsetintparam (env, CPX_PARAM_THREADS, 1);
status = CPXsetintparam (env, CPX_PARAM_PREIND, 0);
status = CPXsetintparam (env, CPX_PARAM_LPMETHOD, CPX_ALG_BARRIER);
status = CPXsetintparam (env, CPX_PARAM_BARCROSSALG, CPX_ALG_NONE);
status = CPXsetintparam (env, CPX_PARAM_BARALG, 1);
status = CPXsetdblparam (env, CPX_PARAM_BAREPCOMP, 1.0e-8);
status = CPXsetintparam (env, CPX_PARAM_DEPIND, 0);
status = CPXsetintparam (env, CPX_PARAM_REDUCE, 0);
status = CPXsetintparam (env, CPX_PARAM_SYMMETRY, 0);
status = CPXsetintparam (env, CPX_PARAM_AGGIND, 0);
status = CPXsetintparam (env, CPX_PARAM_COEREDIND, 0);
status = CPXsetintparam (env, CPX_PARAM_PRELINEAR, 0);
status = CPXsetintparam (env, CPX_PARAM_PREPASS, 0);
status = CPXsetintparam (env, CPX_PARAM_PRESLVND, 0);
status = CPXsetintparam (env, CPX_PARAM_PREDUAL, -1);
status = CPXsetintparam (env, CPX_PARAM_PREIND, 0);
status = CPXsetintparam (env, CPX_PARAM_RELAXPREIND, 0);
status = CPXsetintparam (env, CPX_PARAM_REPEATPRESOLVE, 0);
OUTPUT:__________________________________________________________

Tried aggregator 0 times.
Presolve time = 0.00 sec.
Tried aggregator 0 times.
LP Presolve eliminated 6 rows and 3 columns.
All rows and columns eliminated.
Presolve time = 0.00 sec.
After network optimization, objective is 0
Solution status 1
Objective value 0
Solution is:
x[0] = -2
x[1] = -2
x[2] = -2

In this example, A=1 0 0; -1 0 0; 0 1 0; 0 -1 0; 0 0 1; 0 0 -1 and B = 2 2 2 2 2 2 and c = 0 0 0. Expected analytic center is at (0,0,0).

Yours faithfully,

ChiaWeng
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

This is weird. Are you sure that all the parameters settings you listed are actually applied. Maybe write out a file with changed parameter settings (CPXwriteparam()) right before the solve and double check that the parameters are indeed set.
Usually CPX_PARAM_REDUCE=0 and CPX_PARAM_PREIND=0 should be enough to avoid presolve.
I also wonder why the network optimizer shows up in the output. Did you use that explicitly?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> dju358 wrote:
> This is weird. Are you sure that all the parameters settings you listed are actually applied. Maybe write out a file with changed parameter settings (CPXwriteparam()) right before the solve and double check that the parameters are indeed set.
> Usually CPX_PARAM_REDUCE=0 and CPX_PARAM_PREIND=0 should be enough to avoid presolve.
> I also wonder why the network optimizer shows up in the output. Did you use that explicitly?
When using the barrier method, CPLEX will always do a limited amount of presolve to removed fixed
variables (which you have in your small sample problem). CPLEX needs to do that because with
a fixed variable, the feasible region has no interior in the dimension of that variable. That creates
numerical difficulties that hamper the barrier method.

However, as Daniel points out, the output you posted suggests you invoked the network optimizer rather
than the barrier method. In addition to the previous recommendation of writing out a parameter file
just before the optimization, can you post the segment of code that actually performs the optimization?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: ChiaWeng

Thank you all for the replies. The 'network' was not supposed to show up. I modified an example and forgot to change it in the printf command. My full code is shown below using version Academic version 12.3 together with the output from CPXwriteparam(). My suspicion is that the SIMPLEX was used to get the answer(feasible starting point) and the barrier method was not used at all since the problem formulation was meaningless. But I hope there would be a way to force the barrier method to accept the original formulation and proceed with the iteration.
#include <ilcplex/cplex.h>
#include <stdio.h>
#include <stdlib.h>
#define COLSORIG 3
#define ROWSSUB 6
#define NZSUB (2*COLSORIG)
#define ROWSCOMP 0
#define NZCOMP (ROWSCOMP*COLSORIG)
#define ROWSTOT (ROWSSUB+ROWSCOMP)
#define NZTOT (NZCOMP+NZSUB)
int
main()
{
/* Data for original problem. Arrays have to be big enough to hold
problem plus additional constraints. */

double HrhsROWSTOT = { 2, 2, 2, 2, 2,2};
double HlbCOLSORIG = { -CPX_INFBOUND, -CPX_INFBOUND, -CPX_INFBOUND};
double HubCOLSORIG = { CPX_INFBOUND, CPX_INFBOUND, CPX_INFBOUND};
double HcostCOLSORIG = { 0.0000000000000000, 0.0000000000000000, 0.0000000000000000};
char HsenseROWSTOT = { 'L', 'L', 'L', 'L', 'L', 'L'};
int HmatbegCOLSORIG = { 0, 2, 4};
int HmatcntCOLSORIG = { 2, 2, 2};
int HmatindNZTOT = { 0, 1, 2, 3, 4, 5};
double HmatvalNZTOT = { 1.0, -1.0, 1.0, -1.0, 1.0, -1.0};
double xCOLSORIG; x[0]=1.0; x[1]=0.0; x[2]=0.0;
CPXENVptr env = NULL;
CPXLPptr lp = NULL;
int j;
int status, lpstat;
double objval;
env = CPXopenCPLEX (&status);

if ( env == NULL ) {
char errmsg1024;
fprintf (stderr, "Could not open CPLEX environment.\n");
CPXgeterrorstring (env, status, errmsg);
fprintf (stderr, "%s", errmsg);
goto TERMINATE;
}
status = CPXsetintparam (env, CPX_PARAM_SCRIND, CPX_ON);
if ( status ) {
fprintf (stderr,
"Failure to turn on screen indicator, error %d.\n", status);
goto TERMINATE;
}

status = CPXsetintparam (env, CPX_PARAM_BARDISPLAY, 2);
if ( status ) {
fprintf (stderr,"Failed to turn up simplex display level.\n");
goto TERMINATE;
}

/* Create the problem */

lp = CPXcreateprob (env, &status, "chvatal");

if ( lp == NULL ) {
fprintf (stderr,"Failed to create subproblem\n");
status = 1;
goto TERMINATE;
}

status = CPXcopylp (env, lp, COLSORIG, ROWSSUB, CPX_MIN, Hcost, Hrhs,
Hsense, Hmatbeg, Hmatcnt, Hmatind, Hmatval,
Hlb, Hub, NULL);

if ( status ) {
fprintf (stderr, "CPXcopylp failed.\n");
goto TERMINATE;
}

status = CPXsetintparam (env, CPX_PARAM_THREADS, 1);
status = CPXsetintparam (env, CPX_PARAM_PREIND, 0);
status = CPXsetintparam (env, CPX_PARAM_LPMETHOD, CPX_ALG_BARRIER);
status = CPXsetintparam (env, CPX_PARAM_BARCROSSALG, CPX_ALG_NONE);
status = CPXsetintparam (env, CPX_PARAM_BARALG, 3);
status = CPXsetdblparam (env, CPX_PARAM_BAREPCOMP, 1.0e-8);
status = CPXsetintparam (env, CPX_PARAM_DEPIND, 0);
status = CPXsetintparam (env, CPX_PARAM_REDUCE, 0);
status = CPXsetintparam (env, CPX_PARAM_SYMMETRY, 0);
status = CPXsetintparam (env, CPX_PARAM_AGGIND, 0);
status = CPXsetintparam (env, CPX_PARAM_COEREDIND, 0);
status = CPXsetintparam (env, CPX_PARAM_PRELINEAR, 0);
status = CPXsetintparam (env, CPX_PARAM_PREPASS, 0);
status = CPXsetintparam (env, CPX_PARAM_PRESLVND, 0);
status = CPXsetintparam (env, CPX_PARAM_PREDUAL, -1);
status = CPXsetintparam (env, CPX_PARAM_PREIND, 0);
status = CPXsetintparam (env, CPX_PARAM_RELAXPREIND, 0);
status = CPXsetintparam (env, CPX_PARAM_REPEATPRESOLVE, 0);
status = CPXwriteparam (env, "analyticCenter.prm");

if ( status ) {
fprintf (stderr,
"Failed to set the optimization method, error %d.\n", status);
goto TERMINATE;
}

status = CPXlpopt (env, lp);
if ( status ) {
fprintf (stderr, "Failed to optimize LP.\n");
goto TERMINATE;
}

status = CPXgetobjval (env, lp, &objval);
if ( status ) {
fprintf (stderr,"CPXgetobjval failed\n");
goto TERMINATE;
}

printf ("After barrier optimization, objective is %.10g\n", objval);

status = CPXsolution (env, lp, &lpstat, &objval, x, NULL, NULL, NULL);
if ( status ) {
fprintf (stderr,"CPXsolution failed.\n");
goto TERMINATE;
}

printf ("Solution status %d\n",lpstat);
printf ("Objective value %g\n",objval);
printf ("Solution is:\n");
for (j = 0; j < COLSORIG; j++) {
printf ("x%d = %g\n",j,x[j]);
}

TERMINATE:

/* Free up the problem as allocated by CPXcreateprob, if necessary */

if ( lp != NULL ) {
status = CPXfreeprob (env, &lp);
if ( status ) {
fprintf (stderr, "CPXfreeprob failed, error code %d.\n", status);
}
}

/* Free up the CPLEX environment, if necessary */

if ( env != NULL ) {
status = CPXcloseCPLEX (&env);

/* Note that CPXcloseCPLEX produces no output,
so the only way to see the cause of the error is to use
CPXgeterrorstring. For other CPLEX routines, the errors will
be seen if the CPX_PARAM_SCRIND indicator is set to CPX_ON. */

if ( status ) {
char errmsg1024;
fprintf (stderr, "Could not close CPLEX environment.\n");
CPXgeterrorstring (env, status, errmsg);
fprintf (stderr, "%s", errmsg);
}
}

return (status);

} /* END main */
___________________________________________________________
IBM ILOG License Manager: "IBM ILOG Optimization Suite for Academic Initiative" is accessing CPLEX 12 with option(s): "e m b q ".
Tried aggregator 0 times.
Presolve time = 0.00 sec.
Tried aggregator 0 times.
LP Presolve eliminated 6 rows and 3 columns.
All rows and columns eliminated.
Presolve time = 0.00 sec.

Total time on 1 threads = 0.00 sec.

Total time on 1 threads = 0.00 sec.
After barrier optimization, objective is 0
Solution status 1
Objective value 0
Solution is:
x[0] = -2
x[1] = -2
x[2] = -2

Expected answer from barrier should be (0,0,0).

___________________________________________________________________________________
CPLEX Parameter File Version 12.3.0.0
CPX_PARAM_AGGIND 0
CPX_PARAM_DEPIND 0
CPX_PARAM_PREIND 0
CPX_PARAM_SCRIND 1
CPX_PARAM_PREDUAL -1
CPX_PARAM_PREPASS 0
CPX_PARAM_REDUCE 0
CPX_PARAM_PRELINEAR 0
CPX_PARAM_LPMETHOD 4
CPX_PARAM_THREADS 1
CPX_PARAM_COEREDIND 0
CPX_PARAM_RELAXPREIND 0
CPX_PARAM_SYMMETRY 0
CPX_PARAM_REPEATPRESOLVE 0
CPX_PARAM_BARALG 3
CPX_PARAM_BARDISPLAY 2
CPX_PARAM_BARCROSSALG -1

Yours,

Boon
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> ___________________________________________________________
> IBM ILOG License Manager: "IBM ILOG Optimization Suite for Academic Initiative" is accessing CPLEX 12 with option(s): "e m b q ".
> Tried aggregator 0 times.
> Presolve time = 0.00 sec.
> Tried aggregator 0 times.
> LP Presolve eliminated 6 rows and 3 columns.
> All rows and columns eliminated.

This output indicates presolve solved the problem for you, and CPLEX therefore
never invoked the barrier method. Once that happens, it's no surprise that
CPLEX's presolve will find a solution with variables at their bounds rather than
at the center of the region of optimal solutions (which in this case is the center
of the feasible region given your objective function of 0). However, your model
does not have any fixed variables with no interior, so I don't see why presolve
would need to operate on your model given that you have set parameters to disable it.

Furthermore, the issue does not involve your program, as I can reproduce it on your
model in interactive CPLEX:
Barrier - Optimal: Objective = 0.0000000000e+00
Solution time = 0.00 sec. Iterations = 0
CPLEX> d sol var -
Variable Name Solution Value
x1 -2.000000
x2 -2.000000
x3 -2.000000

CPLEX> d pr all
Minimize
obj:
Subject To
c1: x1 <= 2
c2: x1 >= -2
c3: x2 <= 2
c4: x2 >= -2
c5: x3 <= 2
c6: x3 >= -2
Bounds
x1 Free
x2 Free
x3 Free
CPLEX>
I had a closer look at this and found that CPLEX performs more presolve reductions than it should
given the parameter settings you have provided. I am checking to see if there is a way to avoid this
behavior and will get back to you shortly.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: ChiaWeng

EdKlotz, thank you! I deeply appreciate your effort in helping me out.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: ChiaWeng

It's been awhile and I'm curious whether anyone knows the way to go around this problem?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> EdKlotz wrote:
> > ___________________________________________________________
> > IBM ILOG License Manager: "IBM ILOG Optimization Suite for Academic Initiative" is accessing CPLEX 12 with option(s): "e m b q ".
> > Tried aggregator 0 times.
> > Presolve time = 0.00 sec.
> > Tried aggregator 0 times.
> > LP Presolve eliminated 6 rows and 3 columns.
> > All rows and columns eliminated.
>
> This output indicates presolve solved the problem for you, and CPLEX therefore
> never invoked the barrier method. Once that happens, it's no surprise that
> CPLEX's presolve will find a solution with variables at their bounds rather than
> at the center of the region of optimal solutions (which in this case is the center
> of the feasible region given your objective function of 0). However, your model
> does not have any fixed variables with no interior, so I don't see why presolve
> would need to operate on your model given that you have set parameters to disable it.
>
> Furthermore, the issue does not involve your program, as I can reproduce it on your
> model in interactive CPLEX:
>
>
> Barrier - Optimal: Objective = 0.0000000000e+00
> Solution time = 0.00 sec. Iterations = 0
>
>
> CPLEX> d sol var -
> Variable Name Solution Value
> x1 -2.000000
> x2 -2.000000
> x3 -2.000000
>
> CPLEX> d pr all
> Minimize
> obj:
> Subject To
> c1: x1 <= 2
> c2: x1 >= -2
> c3: x2 <= 2
> c4: x2 >= -2
> c5: x3 <= 2
> c6: x3 >= -2
> Bounds
> x1 Free
> x2 Free
> x3 Free
> CPLEX>
>
>
>
>
> I had a closer look at this and found that CPLEX performs more presolve reductions than it should
> given the parameter settings you have provided. I am checking to see if there is a way to avoid this
> behavior and will get back to you shortly.
I had a closer look and discussed this with our developers.
CPLEX indeed does perform more presolve reductions than the
absolute minimum guaranteed to result in nonempty primal and
dual interiors. The decision to do this started back in
the year 2000 with the release of CPLEX 7.0. This was done
because we found that additional variable fixings tended to
improve numerical performance. Unfortunately, these
additional reductions also prevent you from getting a solution
that is the analytic center for your model. I have tried
various different tactics to trick CPLEX into doing fewer
presolve reductions on this model, but none of them work.

The core issue here involves the two different types of presolve reductions. Primal based reductions are
based purely on the constraints. Variable fixings associated
with primal reductions do not compromise the analytic center
in the computed solution. If a primal based presolve reduction fixes a variable, it does so because the only possible solution value for that variable is that fixed value.
In that case, even though no interior exists in the space of that variable, that variable resides at its analytic center.
By contrast, dual presolve reductions are based on dual constraints; therefore they make use of the primal objective vector. We see that occurs in your model above. Your variables don't intersect any constraints, so CPLEX looks at
the objective coefficient for the variable and moves it to a bound based on that value. With an objective value of 0,
CPLEX can actually move the variables to their lower or upper bounds, but it (arbitrarily) chooses lower bounds. If your objective had been

max x1 + x2 + x3

dual presolve reductions would have set all 3 variables to their upper bounds of 2. But, in your situation, where you
need the objective to be 0 for the analytic center, this type
of reduction moves you away from the center in a way that primal presolve reductions cannot do.

So, what does this mean for you situation? As I said above,
all my attempts to disable dual presolve reductions with the
barrier method did not succeed. I can add a user request to
our database to provide support for this, but that won't help you for several months. However, here's what I can say.

1. You are more likely to encounter this on simple models like the ones above where the analytic center can be directly
computed.

2. You could try creating the presolved model first, then
computing the analytic center on the presolved model. That should avoid this issue, as once presolve is finished with the model, the odds are the next run with presolve disabled and barrier method will not do any more presolve reductions that would compromise the analytic center. Note that with the C API, CPLEX has some advanced presolve routines that allow you
to keep track of the variable and constraint mappings between the presolved model and your original model, so you could then map back the analytic center solution to your original model.
If you want to follow up on this approach and have additional questions, post them to this thread.

3. If you have access, use CPLEX 6.6 or earlier, or some other solver that will provide you the analytic center. Looking at
page 8 of http://www.optimization-online.org/DB_FILE/2010/11/2793.pdf, GLPK and PCx appear to provide the analytic center,
but there are more difficult to use and run much longer.
Hopefully one of these will help. I will let you know if any other ideas come to mind. Sorry I don't have a better answer.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: ChiaWeng

Thank you EdKlotz for the info. I appreciate the thorough reply. While still using CPLEX 12.3 for my LP problems, I will use other codes for my analytic center problem.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Maybe you can trick CPLEX to do what you want. You need to modify your model such that CPLEX will no longer find those simple dual presolve reductions.

If I replicate all the columns and force equality of the original and replicated variables like this:

Minimize
obj:
Subject To
c1: 0.5 x1 + 0.5 y1 <= 2
c2: 0.5 x1 + 0.5 y1 >= -2
c3: 0.5 x2 + 0.5 y2 <= 2
c4: 0.5 x2 + 0.5 y2 >= -2
c5: 0.5 x3 + 0.5 y3 <= 2
c6: 0.5 x3 + 0.5 y3 >= -2
x1 - y1 = 0
x2 - y2 = 0
x3 - y3 = 0
Bounds
x1 Free
x2 Free
x3 Free
y1 Free
y2 Free
y3 Free
End

then in this particular case the barrier (without presolve and without crossover) spits out the 0 as solution, which is the analytic center here.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: dbaena

Hi,
yes, in this article (www-eio.upc.es/~dbaena/pub/2010/dr2010-01.pdf) we want to calculate the analytic center of a polytope but
even deactivating all the preprocessing options and removing the
crossover postprocess, CPLEX was not always able to provide the analytic center because of its aggressive
reduced preprocessing (which can not be deactivated as we were told by CPLEX developers).
However, GLPK and PCx solvers reported the right analytic center, but GLPK and PCx are less efficient than CPLEX.

We spoke with CPLEX developers about it and yours answer was:
+italics"We cannot completely turn off the presolve for the barrier method in CPLEX.
If the presolve is turned off, then CPLEX will only do a restricted presolve that are necessary for the barrier algorithm.
CPLEX performs some reductions that are potentially troublesome for the barrier method if not done.
This is mentionned in the followig section of the documentation:
User's Manual for CPLEX > Continuous optimization > Solving LPs: barrier optimizer > Tuning barrier optimizer performance > Preprocessing "italics

Good luck!
#CPLEXOptimizers
#DecisionOptimization