I have a Binary linear programming problem with a maximization objective and a set of assignment constraints like

a + b + c + d + e = 1; x + y + z + w + k = 1 and so on. All the variables are binary. I am trying to solve the problem using CPLEX and the upper bounds i.e., LP relaxation is very weak. The LP solution takes the values a=b=c=d=e=1/5 and x=y=z=w=k=1/5 and so one. This makes the convergence of the branch and cut in CPLEX very bad. I was wondering if there is a way to tighten the bounds or if there are a class of valid inequalities that is capable of doing so when we have such assignment constraints.

Thanks in advance.

asked 11 Jul '14, 17:07

pondy's gravatar image

accept rate: 0%

There does not exist cutting planes or valid inequalities which cut into the polytope defined by \[ \text{conv}(\{ x\in\{ 0,1\}^n \ :\ \sum_{i\in S_j}x_i=1,\forall j\in J \}) \] where \( (S_j)_{j\in J}\) is a partition of the set \( S\) of variables. This is simply due to the polytope having all integral extreme points, wherefore the linear relaxation of the set of integer points is exactly the convex hull of integer points. This means that whenever you have a point satisfying the equalities it is in the convex hull of integer solutions and cannot be cut of.

Instead you should focus on other substructures of your program or combinations of the assignment constraints and and other substructures.


answered 12 Jul '14, 05:43

Sune's gravatar image

accept rate: 20%

I can't offer any wisdom about tightening bounds. If you have any problem-specific information that hints at some variables being preferable to others in a solution, it might be worth telling CPLEX to treat those constraints as SOS1 instances. The key (besides being lucky) is to provide useful weights; if you create SOS1 constraints with all variables given equal (default) weights, it will not help. One possibility would be too weight variables according to the ratio of their objective coefficient to the number of constraints they cover.


answered 12 Jul '14, 16:22

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
accept rate: 19%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 11 Jul '14, 17:07

Seen: 793 times

Last updated: 12 Jul '14, 16:22

OR-Exchange! Your site for questions, answers, and announcements about operations research.