Relationship between multiple-choice constraint and Total unimodularity

回答済み

Max Boonbandansook

2023年11月14日 15:02

• 
• 

I have an integer programming model where I am imposing a multiple-choice constraint (x1+x2+...+xn <= 1). My question is, when solving using the LP Relaxation, will I ever get fractional values as my solutions since the multiple-choice constraint is a very tight bound on the variables? Will my model ever perform branch and bound if a multiple-choice constraint is imposed?

Take for example a model where I am maximizing 5x1 + 3x2 and my constraint is x1 + x2 <= 1. The LP relaxation will always give me x1 = 1 as my solution with an objective value of 5. When will the model give me fractional solutions? To frame my question more broadly, what is the relationship between imposing a multiple-choice constraint and total unimodularity in an integer programming model?

 

関連

• Branch-and-Cut

0

• 

  Matthias Miltenberger

  • Gurobi Staff

  2023年11月16日 09:48

  That question is not so easy to answer. I am not aware of a relationship between such constraints and the total unimodularity of the matrix. In general, adding several of these constraints can easily destroy the TU of the matrix as there can be more than two nonzeros in a column which is an easy-to-check requirement for TU matrices. You can read more about the topic here: Unimodular matrix - Wikipedia

  0

サインインしてコメントを残してください。