Constrained balanced optimization problems

We consider the balanced optimization problem with an additional linear constraint under a general combinatorial optimization setting. It is shown that this Constrained Balanced Optimization Problem (CBOP) can be solved in polynomial time whenever an associated minsum problem can be solved in polynomial time. A modification of this basic algorithm is also suggested with improved average performance. This modified algorithm is applicable to the unconstrained version also and has better average performance than existing algorithms. Computational results are presented which establish the superiority of the modified algorithm on both, constrained and unconstrained models. Some variants of CBOP are also discussed in brief. (C) 1999 Elsevier Science Ltd. All rights reserved.