New solving methods for constrained optimization problems

Author: 

Amine Lamine

School: 

National Engineering School of Sfax

Supervisors: 

Prof. Dr. Brahim Hnich
Prof. Dr. Habib Chabchoub
Dr. Mahdi Khemakhem

Abstract: 

This thesis focuses on solving constrained optimization problems. In this work, the aim is multiple, (i) we study the relationship between a set of knapsack problems (ii) we provide a filtering algorithm for the new global constraint \emph{mcmdk} and, we design a new strategy for solving constrained optimization problems.

We first study the relationship between a set of knapsack problems involving dimensions, demands and multiple choice constraints such as: the MKP, the MDMKP, the MCKP, the MMKP and the GUBMKP. This study lead to define the generalized problem called the multiple demand multidimensional multiple choice knapsack problem (MDMMKP) as a generalization of these problems. And by applying a set of defined transformations between the different integer linear programs of these knapsack extensions, algorithm for that generalization is assumed as a a solver. Evenly, results show that the transformations is able to generate reasonable computing time compared with the original ones.

Secondly, we define a new global constraint belonging to the weighted constraints and closely related to the knapsack constraint denoted mcmdk. We modeled the mcmdk constraint using the conjunction of sum and implies constraints and we associate it a filtering algorithm "based reasoning". Experiments show that propagating the mcmdk constraint via the proposed filtering algorithm is more effective and efficient than propagating it using the straightforward conjunction.

And finally, we present a new strategy for solving Constrained Optimization Problems (COPs) called solve and decompose (or $S&D$ for short). The proposed strategy is a systematic iterative depth-first strategy that is based on problem decomposition. $S&D$ uses a feasible solution of the COP, found by any exact method, to further decompose the original problem into a bounded number of subproblems which are considerably smaller in size. The number of subproblems is bounded and is controlled by parameter $p$ whereas their size is controlled by $depth$ which is a depth limit after which we stop the decomposition process. The proposed algorithm is designed so (i) to speed up the time to finding the optimal solution by problem decomposition and visiting of promising subproblems first; and (ii) to speed up the proof of optimality by strengthening the cost-based filtering. Results on two benchmark problems show that $S&D$ may reach improvements of up to three orders of magnitude in terms of runtime when compared to Branch and Bound.

Graduated: 

Tuesday, November 1, 2016

PDF of thesis: