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

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2026年11月13日 01:34

  This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
• 

  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

投稿コメントは受け付けていません。