[Help-glpk] [Fwd: primal and dual simplex solves multiobjective problems]

[Andrew Makhorin]

-------- Forwarded Message --------
From: address@hidden
To: address@hidden
Subject: primal and dual simplex solves multiobjective problems
Date: Mon, 07 Dec 2015 15:34:33 +0100

Hi,

The attached patch against version 4.57 implements a kind of "multiobjective"
optimization. Given the "main" objective c_1,...,c_n and "auxiliary"  
objectives <e_11,...e_1n>, <e_21,...,e_2n>,...<e_p1,...,e_pn>, find  
the optimal value of the "main" objective, then within the solution  
space minimize (maximize) the first auxiliary objective, within the  
solution space minimize (maximize) the second auxiliary objective,  
etc. It is a kind of generalization of asking the lexicographically  
minimal optimal solution of the LP problem.

Please consider this patch as a tentative contribution to the package;  
use it as you like. I would be happy to receive comments what I did  
wrongly.

The following new api functions are added:
glp_set_multiobj_number(P,nobjs)
  sets the number of auxiliary objectives; set to zero to delete  
previous objectives.
glp_set_multiobj_coef(P,objno,j,coef)
  set the objno-th auxiliary objective coefficient
glp_get_multiobj_coef(P,objno,j)
  retrieve the coefficient

A new parameter in glp_smcp is parm->mobj, which should be set to  
GLP_ON to do multiobjective optimization.

All added lines are between #ifdef CSL and #endif; there is only one  
disabled line which checks the consistency of bound flags in the dual  
problem.

In the primal/dual algorithm, primal_simplex()/dual_simplex() is  
called repeatedly after calling next_objective() which goes over all  
non-basic variables and fixes the value of those which have active  
bound (by making the lower and upper bounds the same), and then  
replaces the objective values with the next objective.

It is not clear whether csa->phase has to be set to zero in the dual  
problem; and whether the when PSE pricing is on, whether it should be  
invalidated from one invocation to the next.

Laszlo

Laszlo Csirmaz
CEU,
Alfred Renyi Mathematical Institute
Budapest





----------------------------------------------------------------
This message was sent using IMP, the Internet Messaging Program.

patch.txt
Description: Text document