Contributed Session Tue.1.H 2013

Tuesday, 10:30 - 12:00 h, Room: H 2013

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

MILP formulations III


Chair: Magnus Önnheim



Tuesday, 10:30 - 10:55 h, Room: H 2013, Talk 1

Ramiro Daniel Torres
Optimizing the Ecuadorian football league third division.

Coauthors: Diego Recalde, Polo Vaca


In this work, a real-world application arising in the Ecuadorian football league third division is considered. Currently, this league is played by a set of teams which is empirically partitioned by a geographical nearness criterion. After identifying such partition, teams on each group play an independent double round robin tournament.
The problem consists in partitioning the set of teams into groups such that the distance travelled by each team in away-matches is minimized. Moreover, the number of teams in a group is fixed by regulations of the football league. Balanced groups, according to football level, are desired and other aspects like rivalry between teams and geographical constraints must be considered. An integer programming approach is proposed to solve this problem. Computational experiments are performed, where instances provided by the Ecuadorian
Football Federation can be solved quite well, and significant
improvements compared with the current situation are shown.



Tuesday, 11:00 - 11:25 h, Room: H 2013, Talk 2

Keisuke Hotta
Enumeration and characterization of the electoral districting for the decision support


In Japan, 300 members of the House of Representatives, the Lower House, are elected by the single-seat constituency system. Each electoral district is made by the apportionment to the 47 prefectures and the redistricting in each prefecture. The apportionment gives the lower bound of the gap in the value of individual votes. Because of the density of population in an urban area, the lower bound of the ratio is close to 2 times. As a result, the gap is more than 2 by the redistricting. In Japan, the state of the same condition has been continuing for over ten years.
By optimizing both the apportionment problem and the redistricting problems respectively, the limit of the disparity is 1.939 for the population in 2010 and the provinces in 2011. The 0-1 IP model to optimize the redistricting was studied by Nemoto and Hotta in 2003. The optimal district gives the limit of the disparity, but it is not always practical. So, it is better to enumerate some practical district, to point out the similarity to the current district, and to characterize the district candidates. This research provides them for the decision support.



Tuesday, 11:30 - 11:55 h, Room: H 2013, Talk 3

Magnus Önnheim
The opportunistic replacement problem: Model, theory and numerics

Coauthors: Torgny Almgren, Niclas Andréasson, Michael Patriksson, Ann-Brith Strömberg, Adam Wojciechowski


We present a 0-1 integer linear programming (ILP) model for determining optimal opportunistic maintenance schedules for a system of components with maximum replacement intervals; it is a natural starting point for modelling replacement schedules of more complex systems. We show that this problem is NP-hard and that all the necessary inequalities induce facets. We further present a new class of facets defined by {0,1⁄2}-Chvátal-Gomory cuts. For costs monotone with time a class of elimination constraints, allowing for maintenance only when replacement is necessary for at least one component, is defined. For fixed maintenance occasions the remaining linear program is solvable by a greedy procedure.
Results from a case study on aircraft engine maintenance illustrate the advantage of the 0-1 ILP model over simpler policies. We include the new class of facets in a branch&cut framework and note a decrease in number of branch&bound nodes and simplex iterations for most instance classes with time dependent costs. For instance classes with time independent costs and few components the elimination constraints are used favourably.


  There are three major facts that should be watched out for in all payday loans in the United States. If you have already decided to take Buy Generic Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.