An ILP based heuristic for a generalization of the post-enrollment course timetabling problem

We consider a new timetabling problem arising from a real-world application in a private university in Buenos Aires, Argentina. In this paper we describe the problem in detail, which generalizes the Post-Enrollment Course Timetabling Problem (PECTP), propose an ILP model and a heuristic approach based on this formulation. This algorithm has been implemented and tested on instances obtained from real data, showing that the approach is feasible in practice and produces good quality solutions.     

School timetabling for quality student and teacher schedules

The school timetabling problem, although less complicated than its counterpart for the university, still provides a ground for interesting and innovative approaches that promise solutions of high quality. In this work, a Shift Assignment Problem is solved first and work shifts are assigned to teachers. In the sequel, the actual Timetabling Problem is solved while the optimal shift assignments that resulted from the previous problem help in defining the values for the cost coefficients in the objective function. Both problems are modelled using Integer Programming and by this combined approach we succeed in modelling all operational and practical rules that the Hellenic secondary educational system imposes. The resulting timetables are conflict free, complete, fully compact and well balanced for the students. They also handle simultaneous, collaborative and parallel teaching as well as blocks of consecutive lectures for certain courses. In addition, they are highly compact for the teachers, satisfy the teachers’ preferences at a high degree, and assign core courses towards the beginning of each day. Dr. Birbas is currently the Director for Primary and Secondary Education in the Region of Western Greece.     

Mixed integer programming for minimizing the period of a cyclic railway timetable for a single track with two train types

In this paper we extend the work of Bergmann (1975) to investigate the capacity of a single track, unidirectional rail line that adheres to a cyclic timetable. A set of intermediate stations lies between an origin and destination with one siding at each station. Two types of trains—express and local—are dispatched from the origin in alternating fashion. The local stops at every intermediate station and the express stops at no intermediate stations. A mixed integer linear program is developed in order to minimize the length of the dispatching cycle and minimize the total stopping (dwell) time of the local train at all stations combined. Constraints include a minimum dwell time for the local train at each station, a maximum total dwell time for the local train, and headway considerations on the main line and in stations. Hundreds of randomly generated problem instances with up to 70 stations are considered and solved to optimality in a reasonable amount of time using IBM ILOG CPLEX.     

高效求解整数线性规划问题的分支算法

为了提高求解一般整数线性规划问题的效率,提出了一种基于目标函数超平面移动的分支算法。对于给定的目标函数整数值,首先利用线性规划松弛问题的最优单纯形表确定变量的上、下界,然后将变量的上、下界条件加入约束条件中对相应的目标函数超平面进行切割,最后应用分支定界算法中的分支方法来搜寻目标函数超平面上的可行解。通过对一些经典的数值例子的求解计算并与经典的分支定界算法进行比较,结果表明,该算法减少了分支数和单纯形迭代数,具有较大的实用价值。     

Detecting infeasibility and generating cuts for mixed integer programming using constraint programming

We study a hybrid MIP/CP solution approach in which CP is used for detecting infeasibilities and generating cuts within a branch-and-cut algorithm for MIP. Our framework applies to MIP problems augmented by monotone constraints that can be handled by CP. We illustrate our approach on a generic multiple machine scheduling problem, and present a number of computational experiments.     

A survey of approaches for university course timetabling problem

Scheduling is one of the problems which so many researches have been conducted on it over the years. The university course timetabling problem which is an NP-hard problem is a type of scheduling problem. Timetabling process must be done for each semester frequently, which is an exhausting and time consuming task. The allocation of whole of events in timeslots and rooms performs by the university course timetabling process considering the list of hard and soft constraints presented in one semester, so that no conflict is created in such allocations. In the university course timetabling problem (UCTTP), the hard constraints should not be violated under any conditions; soft constraints also should not be violated as much as possible. The aim of the present paper is to analyze available approaches in the study of university course timetabling problems, including operational researches, metaheuristic methods and intelligent novel methods; also the distributed multi agent systems based approach (Cooperative Search method) is investigated due to its scalability which enables the timetabling of common events between departments. In addition, in this work a complete introduction of reliable datasets has been given to test and evaluation of the structure of considered algorithms.     

Automatic structural identification and relaxation for integer programming

This research investigates the automatic identification of typical embedded structures in the Integer Programming (IP) models and automatic transformation of the problem to an adequate Lagrangian problem which can provide tight bounds within the acceptable run time. For this purpose, the structural distinctivenesses of variables, constants, blocks of terms, and constraint chunks are identified to specify the structure of the IP model. To assist the identification of the structural distinctiveness, the representation by the knowledge based IP model formulator, UNIK-IP, is adopted. To reason for the structural identification, the hybrid of bottom-up, top-down, and case-based approaches are proposed. A system UNIK-RELAX is developed to implement the approaches proposed in this research.     

A two-phase optimization procedure for integer programming problems

This paper presents a simple two-phase method for optimizing integer programming problems with a linear or nonlinear objective function subject to multiple linear or nonlinear constraints. The primary phase is based on a variation of the method of steepest descent in the feasible region, and a hem-stitching approach when a constraint is violated. The secondary phase zeros on the optimum solution by exploring the neighborhood of the suboptimum found in the first phase of the optimization process. The effectiveness of this method is illustrated through the optimization of several examples. The results from the proposed optimization approach are compared to those from methods developed specially for dealing with integer problems. The proposed method is simple, easy to implement yet very effective in dealing with a wide class of integer problems such as spare allocation, reliability optimization, and transportation problems.     

一种求解整数规划与混合整数规划非线性罚函数方法

证明了任何一个变量有界的整数规划问题（IP）和混合整数规划问题（MIP）都可以转化为一个等价的非整数（或连续化）规划问题（NIP），并给出一个用非线性精确罚函数法来求解该等价NIP的方法，从而达到求解IP或MIP的目的，数值实验表明了算法的可行性。该方法可广泛用于各应用领域里IP和MIP的求解，特别是为非线性IP和MIP问题提供了一条通用 的求解途径，对解决许多实际优化问题具有重要意义。     

A Hybrid approach for integer programming combining genetic algorithms, linear programming and ordinal optimization

Hybrid methods are promising tools in integer programming, as they combine the best features of different methods in a complementary fashion. This paper presents such a framework, integrating the notions of genetic algorithm, linear programming, and ordinal optimization in an effort to shorten computation times for large and/or difficult integer programming problems. Capitalizing on the central idea of ordinal optimization and on the learning capability of genetic algorithms to quickly generate good feasible solutions, and then using linear programming to solve the problem that results from fixing the integer part of the solution, one may be able to obtain solutions that are close to optimal. Indeed ordinal optimization guarantees the quality of the solutions found. Numerical testing on a real-life complex scheduling problem demonstrates the effectiveness and efficiency of this approach.     

Solving the single-machine sequencing problem using integer programming

Various integer programming models have been proposed for sequencing problems. However, little is known about the practical value of these models. This paper reports a comparison of six different integer programming formulations of the single-machine total tardiness problem. We created a set of especially difficult test problems and attempted to solve them with each of the formulations, using CPLEX software. We found that one formulation performs much more effectively than the others. A generic integer programming approach is still not capable of solving problems with hundreds of jobs, so in that respect, it does not compete with state-of-the-art tardiness algorithms. However, the integer programming approach remains viable for problems containing as many as 40 or 50 jobs and may be the better algorithmic choice when convenience in implementation is considered.     

Integer programming methods for large-scale practical classroom assignment problems

In this paper we present an integer programming method for solving the Classroom Assignment Problem in University Course Timetabling. We introduce a novel formulation of the problem which generalises existing models and maintains tractability even for large instances. The model is validated through computational results based on our experiences at the University of Auckland, and on instances from the 2007 International Timetabling Competition. We also expand upon existing results into the computational difficulty of room assignment problems.     

多周期混合整数规划购油模型及应用

采用PIMS软件中的多周期混合整数规划技术建立炼油企业购油计划模型，使优化结果与实际购油方式相吻合；采用虚拟周期方法解决原油期末库存质量控制问题；采用滚动处理方式解决炼厂月、季原油选购计划的衔接和全局优化问题。文中还给出了多周期MIP模型技术在某炼厂中的应用以及不同方案的效益对比。     

Lower time bounds for integer programming with two variables

In this paper an elementary version of the integer programming problem is considered, namely that of deciding whether a given triangle in the plane contains a point with integer coordinates. We prove two lower bounds for the number of operations necessary to solve this problem: (i) Ω(p) steps are necessary if operations from {+, -,%,, ?} are admissible, (ii) Ω(log p) steps are necessary if operations from {+, -, ?·?, ?} are admissible. Here, p denotes the binary length of the input and ?·? denotes the floor function. New techniques are necessary for relating the bounds to the length of the input—known methods only yield uniform bounds assuming all real inputs to be allowed—and for handling the floor function which prevents us from applying the well-known algebraic arguments.The best known algorithm is due to H.W. Lenstra, Jr. (preprint) and needs O(p) steps over {+, -, 1, %, ?·?, ?} (P. van Emde Boas, 1984).     

On-line fault detection in discrete event systems by Petri nets and integer linear programming

The paper addresses the fault detection problem for discrete event systems in a Petri Net (PN) framework. Assuming that the structure of the PN model and the initial marking are known, faults are modelled by unobservable transitions. Moreover, we assume that there may be additional unobservable transitions associated with the system legal behaviour and that the marking reached after the firing of any transition is unknown. The proposed diagnoser works on-line: it waits for the firing of an observable transition and employs an algorithm based on the definition and solution of some integer linear programming problems to decide whether the system behaviour is normal or exhibits some possible faults. The results characterize the properties that the PN modelling the system fault behaviour has to fulfill in order to reduce the on-line computational effort.     

An integer program and a hybrid genetic algorithm for the university timetabling problem

The university timetabling problem (UTP) has been studied by numerous research groups for decades. In addition to addressing hard and soft constraints, we extend the UTP by considering consecutiveness and periodicity constraints of multi-session lectures, which are common in many eastern Asian universities. Because schedulers can decide the consecutiveness and periodicity constraints for the multi-session lectures within a limited ratio, we consider these novel decision variables in our model. We develop a mixed integer linear program for the UTP. For the analysis, we convert the UTP into the three-dimensional container packing problem (3DCPP) and create a hybrid genetic algorithm (HGA), which has been shown to be efficient in solving the 3DCPP. We also develop a tabu search algorithm based on the existing UTP literature and compare the findings with that of our HGA. The results show that our HGA obtains a better solution than the tabu search algorithm in a reasonable amount of time.     

Scheduling the professional Ecuadorian football league by integer programming

A sports schedule sets the dates and venues of games among teams in a sports league. Constructing a sports schedule is a highly restrictive problem. The schedule must meet constraints due to regulations of a particular sports league federation and it must guarantee the participation of all teams on equal terms. Moreover, economic benefits of the teams and other agents involved in this activity are expected. Until 2011, the Ecuadorian football federation (FEF) had developed schedules for their professional football championship manually. In early 2011, the authors presented to the FEF authorities evidence that the use of mathematical programming to create feasible sports schedules could easily exceed the benefits obtained by the empirical method. Under this premise, this work presents an integer programming formulation, solved to optimality, for scheduling the professional football league in Ecuador, and also a heuristic approach based on three-phases for its solution. The schedules obtained met the expectations of the FEF and one of them was adopted as the official schedule for the 2012 edition of the Ecuadorian professional football championship.     

Gamma deployment problem in grids: hardness and new integer linear programming formulation

Vehicular networks are mobile networks designed for the domain of vehicles and pedestrians. These networks are an essential component of intelligent transportation systems and have the potential to ease traffic management, lower accident rates, and offer other solutions to smart cities. One of the most challenging aspects in the design of a vehicular network is the distribution of its infrastructure units, which are called roadside units (RSUs). In this work, we tackle the gamma deployment problem that consists of deploying the minimum number of RSUs in a vehicular network in accordance with a quality of service metric called gamma deployment. This metric defines a vehicle as covered if it connects to some RSUs at least once in a given time interval during its whole trip. Then, the metric parameterizes the minimum percentage of covered vehicles necessary to make a deployment acceptable or feasible. In this paper, we prove that the decision version of the gamma deployment problem in grids is NP‐complete. Moreover, we correct the multiflow integer linear programming formulation present in the literature and introduce a new formulation based on set covering that is at least as strong as the multiflow formulation. In experiments with a commercial solver, the set covering formulation widely outperforms the multiflow formulation with respect to running time and linear programming relaxation gap.