Invited Session Tue.2.H 2013

Tuesday, 13:15 - 14:45 h, Room: H 2013

Cluster 11: Integer & mixed-integer programming [...]

Advances in mixed integer programming


Chair: Andrea Lodi



Tuesday, 13:15 - 13:40 h, Room: H 2013, Talk 1

Alejandro Toriello
Optimal toll design: A lower bound framework for the traveling salesman problem


We propose a framework of lower bounds for the asymmetric traveling salesman problem based on approximating the dynamic programming formulation, and give an economic interpretation wherein the salesman must pay tolls as he travels between cities. We then introduce an exact reformulation that generates a family of successively tighter lower bounds, all solvable in polynomial time, and compare these new bounds to the well-known Held-Karp bound.



Tuesday, 13:45 - 14:10 h, Room: H 2013, Talk 2

Minjiao Zhang
Cardinality-constrained continuous mixing set

Coauthor: Simge Kucukyavuz


We study the polyhedron of continuous mixing set with a cardinality constraint (CMC), which arises as a substructure of a dynamic decision-making problem under a joint chance constraint. We give valid inequalities and alternative extended formulations for CMC. We develop a branch-and-cut algorithm and test it on a dynamic lot-sizing problem with stochastic demand in which a specific service level must be met over the finite planning horizon. Our computational experience shows that the branch-and-cut algorithm is effective in solving the probabilistic dynamic lot-sizing problems with a moderate number of scenarios.



Tuesday, 14:15 - 14:40 h, Room: H 2013, Talk 3

Ricardo Fukasawa
New inequalities for mixing sets arising in chance constrained programming

Coauthor: Ahmad Abdi


Luedtke et al (2010) and Kucukyavuz (2010) study a mixing set arising when reformulating chance-constrained programs with joint probabilistic constraints in which the right-hand-side vector is random with a finite discrete distribution. These two papers introduce facet-defining inequalities for the convex hull of such sets, like the strengthened star inequalities and the (T,\PiL) inequalities. We present a new class of inequalities that generalizes all these previously derived inequalities (both for the equal and unequal probabilites case).


  Illinois Payday Loans should not be obtained by people who do not have the capacity to repay the lenders. What can cause long-term use of Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.