[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Andrew Makhorin
Subject: [Help-glpk] [Fwd: primal and dual simplex solves multiobjective problems]
Date: Mon, 07 Dec 2015 18:48:36 +0300

-------- 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


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  

The following new api functions are added:
  sets the number of auxiliary objectives; set to zero to delete  
previous objectives.
  set the objno-th auxiliary objective coefficient
  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  

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 Csirmaz
Alfred Renyi Mathematical Institute

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

Attachment: patch.txt
Description: Text document

reply via email to

[Prev in Thread] Current Thread [Next in Thread]