Questions Tagged With dual-boundhttp://www.or-exchange.com/tags/dual-bound/?type=rssquestions tagged <span class="tag">dual-bound</span>enSat, 16 Jul 2016 03:22:05 -0400What will happen in dual problem if lower bound of primal variables is positive?http://www.or-exchange.com/questions/14005/what-will-happen-in-dual-problem-if-lower-bound-of-primal-variables-is-positive<p>When I am solving linear programming with lower bound of decision variables is positive I am getting all dual solution zero. How can I get correct dual solution?</p>Amit SarkarSat, 16 Jul 2016 03:22:05 -0400http://www.or-exchange.com/questions/14005/what-will-happen-in-dual-problem-if-lower-bound-of-primal-variables-is-positivelinear-programmingdualitydual-boundImproving dual bounds using combinatorial informationhttp://www.or-exchange.com/questions/8950/improving-dual-bounds-using-combinatorial-information<p>I have a series of difficult 0/1 IPs that I'm solving. The objective function, which I want to minimize, has the property that its value at any feasible integer point is of the form x.y where 1 <= y <= x < 10. In watching the output of Cplex I see a lot of instances where the dual bound is of the form z.w... where w > z, and it stays that way for a long time. If, in fact, the optimum objective is >= z.w..., then it is certainly going to be >= (z+1).1. So how can I persuade Cplex to make this inference?</p>
<p>[added later] I should say something about how I encode the problem: I have a bunch of subsets (each of cardinality <= 10) of the variables. If S is such a subset, denote by [S] the sum of the 0/1 variables in that set. I want to find a solution that minimizes the maximal [S] over all of my subsets. I'm also interested in finding the minimum of [S] + 0.1*[T] where S and T range over all pairs of sets so that [S] >= [T] (i.e. I want to find a setting of my 0/1 variables that minimizes the maximal [S], and then, over all of those minimizes the second largest). I encode it by having two continuous variables, w and z and adding the inequalities</p>
<p>[S] <= w and [S] + [T] <= z, where S and T range over all distinct subsets. I then make my objective</p>
<p>\[0.9 \ast w + 0.1 \ast z\]</p>VictorSMillerMon, 23 Dec 2013 13:04:19 -0500http://www.or-exchange.com/questions/8950/improving-dual-bounds-using-combinatorial-informationmipcplexdual-bound