**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**2608

# Search results for: Binary Integer Linear Programming

##### 2608 Minimizing Energy Consumption in Wireless Sensor Networks using Binary Integer Linear Programming

**Authors:**
Chompunut Jantarasorn,
Chutima Prommak

**Abstract:**

The important issue considered in the widespread deployment of Wireless Sensor Networks (WSNs) is an efficiency of the energy consumption. In this paper, we present a study of the optimal relay station planning problems using Binary Integer Linear Programming (BILP) model to minimize the energy consumption in WSNs. Our key contribution is that the proposed model not only ensures the required network lifetime but also guarantees the radio connectivity at high level of communication quality. Specially, we take into account effects of noise, signal quality limitation and bit error rate characteristics. Numerical experiments were conducted in various network scenarios. We analyzed the effects of different sensor node densities and distribution on the energy consumption.

**Keywords:**
Binary Integer Linear Programming,
BILP,
Energy
consumption,
Optimal node placement and Wireless sensor networks.

##### 2607 Robot Path Planning in 3D Space Using Binary Integer Programming

**Authors:**
Ellips Masehian,
Golnaz Habibi

**Abstract:**

**Keywords:**
3D C-space,
Binary Integer Programming (BIP),
Delaunay Tessellation,
Robot Motion Planning.

##### 2606 Generic Model for Timetabling Problems by Integer Linear Programming Approach

**Authors:**
N. A. H. Aizam,
V. Uvaraja

**Abstract:**

The agenda of showing the scheduled time for performing certain tasks is known as timetabling. It is widely used in many departments such as transportation, education, and production. Some difficulties arise to ensure all tasks happen in the time and place allocated. Therefore, many researchers invented various programming models to solve the scheduling problems from several fields. However, the studies in developing the general integer programming model for many timetabling problems are still questionable. Meanwhile, this thesis describes about creating a general model which solves different types of timetabling problems by considering the basic constraints. Initially, the common basic constraints from five different fields are selected and analyzed. A general basic integer programming model was created and then verified by using the medium set of data obtained randomly which is much similar to realistic data. The mathematical software, AIMMS with CPLEX as a solver has been used to solve the model. The model obtained is significant in solving many timetabling problems easily since it is modifiable to all types of scheduling problems which have same basic constraints.

**Keywords:**
AIMMS mathematical software,
integer linear
programming,
scheduling problems,
timetabling.

##### 2605 Use of Linear Programming for Optimal Production in a Production Line in Saudi Food Co.

**Authors:**
Qasim M. Kriri

**Abstract:**

Few Saudi Arabia production companies face financial profit issues until this moment. This work presents a linear integer programming model that solves a production problem of a Saudi Food Company in Saudi Arabia. An optimal solution to the above-mentioned problem is a Linear Programming solution. In this regard, the main purpose of this project is to maximize profit. Linear Programming Technique has been used to derive the maximum profit from production of natural juice at Saudi Food Co. The operations of production of the company were formulated and optimal results are found out by using Lindo Software that employed Sensitivity Analysis and Parametric linear programming in order develop Linear Programming. In addition, the parameter values are increased, then the values of the objective function will be increased.

**Keywords:**
Parameter linear programming,
objective function,
sensitivity analysis,
optimize profit.

##### 2604 A Mixed Integer Linear Programming Model for Flexible Job Shop Scheduling Problem

**Authors:**
Mohsen Ziaee

**Abstract:**

**Keywords:**
Scheduling,
flexible job shop,
makespan,
mixed integer linear programming.

##### 2603 Timetabling Communities’ Demands for an Effective Examination Timetabling Using Integer Linear Programming

**Authors:**
N. F. Jamaluddin,
N. A. H. Aizam

**Abstract:**

This paper explains the educational timetabling problem, a type of scheduling problem that is considered as one of the most challenging problem in optimization and operational research. The university examination timetabling problem (UETP), which involves assigning a set number of exams into a set number of timeslots whilst fulfilling all required conditions, has been widely investigated. The limitation of available timeslots and resources with the increasing number of examinations are the main reasons in the difficulty of solving this problem. Dynamical change in the examination scheduling system adds up the complication particularly in coping up with the demand and new requirements by the communities. Our objective is to investigate these demands and requirements with subjects taken from Universiti Malaysia Terengganu (UMT), through questionnaires. Integer linear programming model which reflects the preferences obtained to produce an effective examination timetabling was formed.

**Keywords:**
Demands,
educational timetabling,
integer linear programming,
scheduling,
university examination timetabling problem.

##### 2602 Optimal Production Planning in Aromatic Coconuts Supply Chain Based On Mixed-Integer Linear Programming

**Authors:**
Chaimongkol Limpianchob

**Abstract:**

This work addresses the problem of production planning that arises in the production of aromatic coconuts from Samudsakhorn province in Thailand. The planning involves the forwarding of aromatic coconuts from the harvest areas to the factory, which is classified into two groups; self-owned areas and contracted areas, the decisions of aromatic coconuts flow in the plant, and addressing a question of which warehouse will be in use. The problem is formulated as a mixed-integer linear programming model within supply chain management framework. The objective function seeks to minimize the total cost including the harvesting, labor and inventory costs. Constraints on the system include the production activities in the company and demand requirements. Numerical results are presented to demonstrate the feasibility of coconuts supply chain model compared with base case.

**Keywords:**
Aromatic coconut,
supply chain management,
production planning,
mixed-integer linear programming.

##### 2601 A new Heuristic Algorithm for the Dynamic Facility Layout Problem with Budget Constraint

**Authors:**
Parham Azimi,
Hamid Reza Charmchi

**Abstract:**

**Keywords:**
Budget constraint,
Dynamic facility layout problem,
Integer programming,
Simulation

##### 2600 Development of a Comprehensive Electricity Generation Simulation Model Using a Mixed Integer Programming Approach

**Authors:**
Erik Delarue,
David Bekaert,
Ronnie Belmans,
William D'haeseleer

**Abstract:**

This paper presents the development of an electricity simulation model taking into account electrical network constraints, applied on the Belgian power system. The base of the model is optimizing an extensive Unit Commitment (UC) problem through the use of Mixed Integer Linear Programming (MILP). Electrical constraints are incorporated through the implementation of a DC load flow. The model encloses the Belgian power system in a 220 – 380 kV high voltage network (i.e., 93 power plants and 106 nodes). The model features the use of pumping storage facilities as well as the inclusion of spinning reserves in a single optimization process. Solution times of the model stay below reasonable values.

**Keywords:**
Electricity generation modeling,
Unit Commitment(UC),
Mixed Integer Linear Programming (MILP),
DC load flow.

##### 2599 Optimal Planning of Waste-to-Energy through Mixed Integer Linear Programming

**Authors:**
S. T. Tan,
H. Hashim,
W. S. Ho,
C. T. Lee

**Abstract:**

**Keywords:**
Mixed Integer Linear Programming (MILP),
optimization,
solid waste management (SWM),
Waste-to-energy (WTE).

##### 2598 Dynamic Slope Scaling Procedure for Stochastic Integer Programming Problem

**Authors:**
Takayuki Shiina

**Abstract:**

**Keywords:**
stochastic programming problem with recourse,
simple
integer recourse,
dynamic slope scaling procedure

##### 2597 Determining Optimum Time Multiplier Setting of Overcurrent Relays Using Mixed Integer Linear Programming

**Authors:**
P. N. Korde,
P. P. Bedekar

**Abstract:**

The time coordination of overcurrent relays (OCR) in a power distribution network is of great importance, as it reduces the power outages by avoiding the mal-operation of the backup relays. For this, the optimum value of the time multiplier setting (TMS) of OCRs should be chosen. The problem of determining the optimum value of TMS of OCRs in power distribution networks is formulated as a constrained optimization problem. The objective is to find the optimum value of TMS of OCRs to minimize the time of operation of relays under the constraint of maintaining the coordination of relays. A power distribution network can have a combination of numerical and electromechanical relays. The TMS of numerical relays can be set to any real value (which satisfies the constraints of the problem), whereas the TMS of electromechanical relays can be set in fixed step (0 to 1 in steps of 0.05). The main contribution of this paper is a formulation of the problem as a mixed-integer linear programming (MILP) problem and application of Gomory's cutting plane method to find the optimum value of TMS of OCRs. The TMS of electromechanical relays are taken as integers in the range 1 to 20 in the step of 1, and these values are mapped to 0.05 to 1 in the step of 0.05. The results obtained are compared with those obtained using a simplex method and its variants. It has been shown that the mixed-integer linear programming method outperforms the simplex method (and its variants) in the case of a system having a combination of numerical and electromechanical relays.

**Keywords:**
Backup protection,
constrained optimization,
Gomory's cutting plane method,
mixed-integer linear programming,
overcurrent relay coordination,
simplex method.

##### 2596 Stochastic Programming Model for Power Generation

**Authors:**
Takayuki Shiina

**Abstract:**

**Keywords:**
electric power capacity expansion problem,
integerprogramming,
L-shaped method,
stochastic programming

##### 2595 Simplex Method for Fuzzy Variable Linear Programming Problems

**Authors:**
S.H. Nasseri,
E. Ardil

**Abstract:**

Fuzzy linear programming is an application of fuzzy set theory in linear decision making problems and most of these problems are related to linear programming with fuzzy variables. A convenient method for solving these problems is based on using of auxiliary problem. In this paper a new method for solving fuzzy variable linear programming problems directly using linear ranking functions is proposed. This method uses simplex tableau which is used for solving linear programming problems in crisp environment before.

**Keywords:**
Fuzzy variable linear programming,
fuzzy number,
ranking function,
simplex method.

##### 2594 Modern Method for Solving Pure Integer Programming Models

**Authors:**
G. Shojatalab

**Abstract:**

**Keywords:**
Integer,
Programming,
Operation Research,
Variables of decision.

##### 2593 Discrete Time Optimal Solution for the Connection Admission Control Problem

**Authors:**
C. Bruni,
F. Delli Priscoli,
G. Koch,
I. Marchetti

**Abstract:**

The Connection Admission Control (CAC) problem is formulated in this paper as a discrete time optimal control problem. The control variables account for the acceptance/ rejection of new connections and forced dropping of in-progress connections. These variables are constrained to meet suitable conditions which account for the QoS requirements (Link Availability, Blocking Probability, Dropping Probability). The performance index evaluates the total throughput. At each discrete time, the problem is solved as an integer-valued linear programming one. The proposed procedure was successfully tested against suitably simulated data.

**Keywords:**
Connection Admission Control,
Optimal Control,
Integer valued Linear Programming,
Quality of Service Requirements,
Robust Control.

##### 2592 Simplex Method for Solving Linear Programming Problems with Fuzzy Numbers

**Authors:**
S. H. Nasseri,
E. Ardil,
A. Yazdani,
R. Zaefarian

**Abstract:**

**Keywords:**
Fuzzy number linear programming,
rankingfunction,
simplex method.

##### 2591 A New Integer Programming Formulation for the Chinese Postman Problem with Time Dependent Travel Times

**Authors:**
Jinghao Sun,
Guozhen Tan,
Guangjian Hou

**Abstract:**

**Keywords:**
Chinese Postman Problem,
Time Dependent,
Integer Programming,
Upper Bound Analysis.

##### 2590 Optimization of Petroleum Refinery Configuration Design with Logic Propositions

**Authors:**
Cheng Seong Khor,
Xiao Qi Yeoh

**Abstract:**

**Keywords:**
Mixed-integer linear programming (MILP),
petroleum refinery,
process synthesis,
superstructure.

##### 2589 Linear Programming Application in Unit Commitment of Wind Farms with Considering Uncertainties

**Authors:**
M. Esmaeeli Shahrakht,
A. Kazemi

**Abstract:**

Due to uncertainty of wind velocity, wind power generators don’t have deterministic output power. Utilizing wind power generation and thermal power plants together create new concerns for operation engineers of power systems. In this paper, a model is presented to implement the uncertainty of load and generated wind power which can be utilized in power system operation planning. Stochastic behavior of parameters is simulated by generating scenarios that can be solved by deterministic method. A mixed-integer linear programming method is used for solving deterministic generation scheduling problem. The proposed approach is applied to a 12-unit test system including 10 thermal units and 2 wind farms. The results show affectivity of piecewise linear model in unit commitment problems. Also using linear programming causes a considerable reduction in calculation times and guarantees convergence to the global optimum. Neglecting the uncertainty of wind velocity causes higher cost assessment of generation scheduling.

**Keywords:**
Load uncertainty,
linear programming,
scenario generation,
unit commitment,
wind farm.

##### 2588 Low-Level Modeling for Optimal Train Routing and Scheduling in Busy Railway Stations

**Authors:**
Quoc Khanh Dang,
Thomas Bourdeaud’huy,
Khaled Mesghouni,
Armand Toguy´eni

**Abstract:**

**Keywords:**
Busy railway stations,
mixed-integer linear
programming,
offline railway station management,
train platforming,
train routing,
train scheduling.

##### 2587 Multi-Objective Optimization of Combined System Reliability and Redundancy Allocation Problem

**Authors:**
Vijaya K. Srivastava,
Davide Spinello

**Abstract:**

This paper presents established 3** ^{n}** enumeration procedure for mixed integer optimization problems for solving multi-objective reliability and redundancy allocation problem subject to design constraints. The formulated problem is to find the optimum level of unit reliability and the number of units for each subsystem. A number of illustrative examples are provided and compared to indicate the application of the superiority of the proposed method.

**Keywords:**
Integer programming,
mixed integer programming,
multi-objective optimization,
reliability redundancy allocation.

##### 2586 Airport Check-In Optimization by IP and Simulation in Combination

**Authors:**
Ahmad Thanyan Al-Sultan

**Abstract:**

The check-in area of airport terminal is one of the busiest sections at airports at certain periods. The passengers are subjected to queues and delays during the check-in process. These delays and queues are due to constraints in the capacity of service facilities. In this project, the airport terminal is decomposed into several check-in areas. The airport check-in scheduling problem requires both a deterministic (integer programming) and stochastic (simulation) approach. Integer programming formulations are provided to minimize the total number of counters in each check-in area under the realistic constraint that counters for one and the same flight should be adjacent and the desired number of counters remaining in each area should be fixed during check-in operations. By using simulation, the airport system can be modeled to study the effects of various parameters such as number of passengers on a flight and check-in counter opening and closing time.

**Keywords:**
Airport terminal,
Integer programming,
Scheduling,
Simulation.

##### 2585 Application of De Novo Programming Approach for Optimizing the Business Process

**Authors:**
Z. Babic,
I. Veza,
A. Balic,
M. Crnjac

**Abstract:**

**Keywords:**
De Novo Programming,
production plan,
stone souvenirs,
variable prices.

##### 2584 Efficiency of Robust Heuristic Gradient Based Enumerative and Tunneling Algorithms for Constrained Integer Programming Problems

**Authors:**
Vijaya K. Srivastava,
Davide Spinello

**Abstract:**

This paper presents performance of two robust gradient-based heuristic optimization procedures based on 3^{n} enumeration and tunneling approach to seek global optimum of constrained integer problems. Both these procedures consist of two distinct phases for locating the global optimum of integer problems with a linear or non-linear objective function subject to linear or non-linear constraints. In both procedures, in the first phase, a local minimum of the function is found using the gradient approach coupled with hemstitching moves when a constraint is violated in order to return the search to the feasible region. In the second phase, in one optimization procedure, the second sub-procedure examines 3^{n} integer combinations on the boundary and within hypercube volume encompassing the result neighboring the result from the first phase and in the second optimization procedure a tunneling function is constructed at the local minimum of the first phase so as to find another point on the other side of the barrier where the function value is approximately the same. In the next cycle, the search for the global optimum commences in both optimization procedures again using this new-found point as the starting vector. The search continues and repeated for various step sizes along the function gradient as well as that along the vector normal to the violated constraints until no improvement in optimum value is found. The results from both these proposed optimization methods are presented and compared with one provided by popular MS Excel solver that is provided within MS Office suite and other published results.

**Keywords:**
Constrained integer problems,
enumerative search algorithm,
Heuristic algorithm,
tunneling algorithm.

##### 2583 Integer Programming Model for the Network Design Problem with Facility Dependent Shortest Path Routing

**Authors:**
Taehan Lee

**Abstract:**

**Keywords:**
Integer programming,
multicommodity network
design,
routing,
shortest path.

##### 2582 Mathematical Rescheduling Models for Railway Services

**Authors:**
Zuraida Alwadood,
Adibah Shuib,
Norlida Abd Hamid

**Abstract:**

This paper presents the review of past studies concerning mathematical models for rescheduling passenger railway services, as part of delay management in the occurrence of railway disruption. Many past mathematical models highlighted were aimed at minimizing the service delays experienced by passengers during service disruptions. Integer programming (IP) and mixed-integer programming (MIP) models are critically discussed, focusing on the model approach, decision variables, sets and parameters. Some of them have been tested on real-life data of railway companies worldwide, while a few have been validated on fictive data. Based on selected literatures on train rescheduling, this paper is able to assist researchers in the model formulation by providing comprehensive analyses towards the model building. These analyses would be able to help in the development of new approaches in rescheduling strategies or perhaps to enhance the existing rescheduling models and make them more powerful or more applicable with shorter computing time.

**Keywords:**
Mathematical modelling,
Mixed-integer
programming,
Railway rescheduling,
Service delays.

##### 2581 Algorithmic Method for Efficient Cruise Program

**Authors:**
Pelaez Verdet,
Antonio,
Loscertales Sanchez,
Pilar

**Abstract:**

**Keywords:**
Itinerary design,
cruise programming,
goalprogramming,
linear programming

##### 2580 A Multi-Objective Model for Supply Chain Network Design under Stochastic Demand

**Authors:**
F. Alborzi,
H. Vafaei,
M.H. Gholami,
M.M. S. Esfahani

**Abstract:**

**Keywords:**
Mixed Integer Programming,
Multi-objective
Optimization,
Stochastic Demand,
Supply Chain Design,
Two Stage
Programming

##### 2579 Solving the Teacher Assignment-Course Scheduling Problem by a Hybrid Algorithm

**Authors:**
Aldy Gunawan,
Kien Ming Ng,
Kim Leng Poh

**Abstract:**

This paper presents a hybrid algorithm for solving a timetabling problem, which is commonly encountered in many universities. The problem combines both teacher assignment and course scheduling problems simultaneously, and is presented as a mathematical programming model. However, this problem becomes intractable and it is unlikely that a proven optimal solution can be obtained by an integer programming approach, especially for large problem instances. A hybrid algorithm that combines an integer programming approach, a greedy heuristic and a modified simulated annealing algorithm collaboratively is proposed to solve the problem. Several randomly generated data sets of sizes comparable to that of an institution in Indonesia are solved using the proposed algorithm. Computational results indicate that the algorithm can overcome difficulties of large problem sizes encountered in previous related works.

**Keywords:**
Timetabling problem,
mathematical programming
model,
hybrid algorithm,
simulated annealing.