Given a set of sets of vectors V={V_1={v_(11),v_(12),..,v_(1n)},...,V_m{v_(m1),v_(m2),..,v_(mn)}},v_(ij) in {−1,0,1}^r. We choose one vector from each set, so that the maximum component of their sum is minimal. Can you advise on how best to approximate the optimal solution of the problem?

Aidyn Crosby

Aidyn Crosby

Answered question

2022-09-01

Given a set of sets of vectors V = { V 1 = { v 11 , v 12 , . . , v 1 n } , . . . , V m { v m 1 , v m 2 , . . , v m n } }, v i j { 1 , 0 , 1 } r . We choose one vector from each set, so that the maximum component of their sum is minimal. Can you advise on how best to approximate the optimal solution of the problem?

Answer & Explanation

Adelaide Kemp

Adelaide Kemp

Beginner2022-09-02Added 10 answers

You can solve the problem via mixed integer linear programming as follows. Let binary decision variable x i , j indicate whether vector v i , j is chosen, and let z represent the maximum component of the sum of the chosen vectors. The problem is to minimize z subject to
(1) j = 1 n x i , j = 1 for  i { 1 , , m } (2) i = 1 m j = 1 n ( v i , j ) k x i , j z for  k { 1 , , r }
Constraint (1) chooses one vector from each set. Constraint (2) enforces the min-max objective.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?