LP file

I have a .lp file which takes very long time (more than 40 hours
without finish) when it is run on CPLEX's Interactive Optimizer
version 10.2.

As I only have CPLEX v.10.2, I was wondering if someone could run
the .lp file for me on the latest version of CPLEX (or Gurobi or other
solvers), and then tell me the results.

After you finish running the case, please tell me:
    (1) The software you use and the software version.
    (2) How long does it take to finish?
    (3) The spec. of the computer that are used to run the .lp file,
and whether the multi-thread function is turned on.
    (4) The final values of all the variables.
    (5) Why the .lp file takes so long?

This is a MIP model. An LP file (or MPS file) is a bad way to look at a MIP problem and give advice about better formulations. Difficult MIP models should always be implemented in a modeling language so you can look at the model, actually understand it and think about it.

Another good example how not to disseminate models is http://www.gamsworld.org/performance/index.htm. The models are totally obscured so they loose any meaning, and don’t allow any reasoning why a certain model gives performance problems for certain solvers.

When we want to learn something about the performance of a model I would argue that it is not helpful to use a format (LP/MPS) that hides the structure and that prohibits reformulations. This is especially the case for discrete models, but also for non-linear models.

Max Likelihood problems

1. I have this maximum likelihood problem. When I maximize the
likelihood function, I get some results; when I take the log of the
likelihood function and maximize it, I get different results. I
suppose this is due to the other problem I seem to have, which is too
many local maxima. Is this the typical case? Or is there something
fundamentally wrong in the way I am posing the problem?

2. Econometricians and statisticians like to use log-likelihood
functions instead of likelihood functions. The official argument is
that "it is easier to manipulate/optimize". Yes, it is easier to
derive, for humans. But it transforms a function that is bounded into
something unbounded. If the optimization is going to be made by a
computer does that really help or does that make it more difficult for
the computer/algorithm? I want to do whatever is the more reliable
technique. I hope this is not one of those "case-by-case" things.

Some points:

1. Taking the log can make the likelihood function better behaved. Some of the very large values that can be formed in sub-expressions can often be prevented this way.
2. Many good NLP solvers allow for bounds on the variables that allow you to steer the NLP solver away from the regions where the function can not be evaluated.
3. Use an alternative method to find a good starting point, e.g. a method of moments estimate.
4. Some of these problems can be difficult. Mixture models are a good example.

MSF Solver: DEA via Excel plug-in

he Excel plug-in allows only for one model. Data Envelopment Analysis models however consist of a number of small LP models: one for each DMU (Decision-Making Unit). However the individual LP models are very small. So it is reasonable to combine all small LP’s into one bigger LP. Basically we form:

max	+c1'x1	+c2'x2	...	+cK'xK
	A1x1=b1
		A2x2=b2
			...
				AKxK=bK

A basic CCR model can look like:

// DEA: combine all LPs into bigger LP
Model[
  Parameters[Sets,DMU,Inp,Outp],
  Parameters[Reals,x[DMU,Inp],y[DMU,Outp]],
  Decisions[Reals[0,Infinity],v[DMU,Inp],u[DMU,Outp]],
  Decisions[Reals,efficiency[DMU]],
  Constraints[
      // objectives:
      Foreach[{j0,DMU},efficiency[j0]==Sum[{o,Outp},u[j0,o]*y[j0,o]]],
      // normalize:
      Foreach[{j0,DMU},Sum[{in,Inp}, v[j0,in]*x[j0,in]] == 1],
      // limit:
      Foreach[{i,DMU},{j0,DMU},Sum[{o,Outp}, u[j0,o]*y[i,o]] <= Sum[{in,Inp}, v[j0,in]*x[i,in]]]
  ],
  Goals[Maximize[totaleff -> Sum[{j0,DMU},efficiency[j0]]]]
]

See also http://www.amsterdamoptimization.com/models/msf/oml.pdf. A similar trick was used in http://yetanothermathprogrammingconsultant.blogspot.com/2009/03/efficient-portfolio-frontier-in-msf.html.

Of course if you prefer to work at the API level there is no problem in solving a series of LP’s.

The Excel interface makes it easy to sort the results. In this case that is done with the Filter facility in Excel.

(click to enlarge)

GAMS: GDXXRW new option CheckDate

GDXXRW is a tool to exchange (read/write) data between GDX files and Excel spreadsheet files. The option CheckDate is helpful to speed up thing when importing data from Excel. If the GDX file is newer than the XLS file it will skip the actual data transfer. As this is COM based this step is somewhat expensive even fro small amounts of data (there is some overhead involved in starting Excel).

GAMS: log file problems

When running a large NLP in the GAMS/IDE with the new 23.1 version, I noticed that the log from KNITRO is buffered. This is not ideal: a log line should appear right away. Also the log from XA is completely disappeared since a few versions. In both cases the result is staring at a blank window when the job is running. The log is really the user-interface for a solver, so it would be good if a little bit more care is devoted to this.

Formulation: sum{i in I} binvar[i]*intvar[i]<=C

> How to linearize sum{i in I} binvar[i]*intvar[i] ≤ C where binvar is a binary variable and intvar is an integer variable.

In general we can linearize y[i] = binvar[i]*intvar[i] as:

0 ≤ y[i] ≤ intvar.up[i]
y[i] ≤ binvar[i]*intvar.up[i]
y[i] ≤ intvar[i]
y[i] ≥ intvar[i] - intvar.up[i]*(1-binvar[i])

In this case we can drop the ≤ inequalities, so we have:

0 ≤ y[i] ≤ intvar.up[i]
y[i] ≥ intvar[i] - intvar.up[i]*(1-binvar[i])
sum{i in I} y[i] ≤ C

Formulation c[i]=min(a[i],b[i])

> How to formulate c[i]=min(a[i],b[i]) for use with Cplex. A and b are integer.

There is not much we can exploit knowing that a, b are integer. In this formulation I use an extra binary variable bv[i] that implements the OR-functionality. The AMPL/Cplex formulation can look like:

var bv{I} binary;
e1{i in I}: c[i] <= a[i];
e2{i in I}: c[i] <= b[i];
e3{i in I}: bv[i]=0 ==> c[i]=a[i] else c[i]=b[i];

e3 implements c[i] = a[i] or c[i] = b[i] and e1,e2 make sure the minimum of the two is chosen.

GAMS: x**2 not allowed in QCP

> I have the the following model:

positive variable x;
free variable z;
equation obj;

obj.. z =e= x**2;
model m/all/;

solve m minimizing z using qcp;

> it is refused by GAMS.

I would consider that a bug. You can use any of the following alternative formulations:

z =e= x*x;
z =e= sqr(x);
z =e= power(x,2);

Formulation: c = Min(a,b) for binary a,b

> How to formulate c=min(a,b) where a,b are binary in a MIP.

This is like c = a×b. See: http://yetanothermathprogrammingconsultant.blogspot.com/2008/05/multiplication-of-binary-variables.html.

I.e.

c ≤ a
c ≤ b
c ≥ a + b − 1
c in [0,1] (continuous)
a,b in {0,1} (binary)

Similarly c = max(a,b) can be modeled via the constraints:

c ≥ a
c ≥ b
c ≤ a + b
c in [0,1] (continuous)
a,b in {0,1} (binary)

Formulation: Multiplication of integer variable with binary variable

> How to linearize z = x × b with x integer and b binary?

Use the formulation from http://yetanothermathprogrammingconsultant.blogspot.com/2008/05/multiplication-of-continuous-and-binary.html.