4 results
Search Results
2. Flow formulations for curriculum-based course timetabling.
- Author
-
Bagger, Niels-Christian F., Kristiansen, Simon, Sørensen, Matias, and Stidsen, Thomas R.
- Subjects
INTEGER programming ,LINEAR programming ,INTERNATIONAL competition ,INTEGERS - Abstract
In this paper we present two mixed-integer programming formulations for the curriculum based course timetabling problem (CTT). We show that the formulations contain underlying network structures by dividing the CTT into two separate models and then connect the two models using flow formulation techniques. The first mixed-integer programming formulation is based on an underlying minimum cost flow problem, which decreases the number of integer variables significantly and improves the performance compared to an intuitive mixed-integer programming formulation. The second formulation is based on a multi-commodity flow problem which in general is NP-hard, however, we prove that it suffices to solve the linear programming relaxation of the model. The formulations show competitiveness with other approaches based on mixed-integer programming from the literature and improve the currently best known lower bound on one data instance in the benchmark data set from the second international timetabling competition. Regarding upper bounds, the formulation based on the minimum cost flow problem performs better on average than other mixed integer programming approaches for the CTT. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
3. Mathematical political districting taking care of minority groups.
- Author
-
Arredondo, Verónica, Martínez-Panero, Miguel, Peña, Teresa, and Ricca, Federica
- Subjects
MINORITIES ,PROBLEM solving ,LINEAR programming ,INTEGER programming ,INTEGERS ,LEGISLATIVE bodies - Abstract
Political districting (PD) is a wide studied topic in the literature since the 60s. It typically requires a multi-criteria approach, and mathematical programs are frequently suggested to model the many aspects of this difficult problem. This implies that exact models cannot be solved to optimality when the size of the territory is too large. In spite of this, an exact formulation can also be exploited in a heuristic framework to find at least a sub-optimal solution for large size problem instances. We study the design of electoral districts in Mexico, where the population is characterized by the presence of minority groups ("indigenous community") who have a special right to be represented in the Parliament. For this, the Mexican electoral law prescribes that a fixed number of districts must be designed to support the representation of the indigenous community. We formulate mixed integer linear programs (MILP) following these two principles, but also including the basic PD criteria of contiguity and population balance. The district map is obtained in two stages: first we produce the fixed number of indigenous districts established by the Law; then we complete the district map by forming the non-indigenous districts. This two-phase approach has two advantages: a dedicated objective function can be formulated in Phase 1 to form indigenous districts at best; in the second phase the instance size is reduced (both in the number of territorial units and in the number of districts) so that the computational effort to solve the problem is reduced as well. We test our procedure on the territory of Chiapas in Mexico and on some fictitious problem instances in which the territory is represented by a grid graph. We also compare our district map with the Institutional one currently adopted in Chiapas. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
4. A note on solving multi-objective integer indefinite quadratic fractional programs.
- Author
-
Kushwah, Prerna and Sharma, Vikas
- Subjects
FRACTIONAL programming ,INTEGERS ,SIMPLEX algorithm ,QUADRATIC programming ,LINEAR programming - Abstract
In this note we have discussed that a simplex like algorithm to solve a indefinite quadratic fractional programming problem proposed by Mekhilef et al. (Ann Oper Res, 2019. https://doi.org/10.1007/s10479-019-03178-2) fails to find its optimal solution and so it may not generate the actual set of efficient points of the corresponding multi-objective integer indefinite quadratic fractional programs. A counter example in support of this argument is also given. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.