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

 

Abstract:
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

 

Abstract:
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

 

Abstract:
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).

 

  The majority of financial loan companies provide the service of getting North Carolina Payday Loans for U.S. citizens. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.