Halaby, M. E., On the Weighted Partial Maximum Satisfiability Problem, : Department of Mathematics, Faculty of Science, Cairo University, 2015. Abstract

This thesis is concerned with the Weighted Partial Maximum Satisfiability problem (WPMax-SAT). The WPMax-SAT problem for a weighted Boolean formula φ = S U H in Conjunctive Normal Form (CNF) is finding an assignment that satisfies all the clauses in H and maximizes the sum of the weights of the satisfied clauses in S. We discuss four aspects of WPMax-SAT. The first is the computational complexity of the problem from the classical and the parametrized perspectives. Secondly, the two solving techniques of WPMax-SAT: branch and bound and SAT-based methods. Third, our experimental investigation on a number of selected solvers. Finally, the applications of WPMax-SAT in real-life.

Halaby, M. E., and A. Abdalla, "Fuzzy Maximum Satisfiability", 10th International Conference on Informatics and Systems (INFOS 2016), ACM ICPS, Giza, Egypt, 2016. Abstract

In this paper, we extend the Maximum Satisfiability (MaxSAT) problem to Łukasiewicz logic. The MaxSAT problem for a set of formulae Φ is the problem of finding an assignment to the variables in Φ that satisfies the maximum number of formulae. Three possible solutions (encodings) are proposed to the new problem: (1) Disjunctive Linear Relations (DLRs), (2) Mixed Integer Linear Programming (MILP) and (3) Weighted Constraint Satisfaction Problem (WCSP). Like its Boolean counterpart, the extended fuzzy MaxSAT will have numerous applications in optimization problems that involve vagueness.

Halaby, M. E., "Solving MaxSAT by Successive Calls to a SAT Solver", SAI Intelligent Systems Conference, IEEE Xplore, London, UK, 2016.
Halaby, M. E., "On the Computational Complexity of MaxSAT", ECCC (Electronic Colloquium on Computational Complexity), 2016. on_the_computational_complexity_of_maxsat.pdf

Discrete Mathematics

Semester: 
Spring
Halaby, M. E., and R. Shaheen, "Solving the Course Timetabling Problem of the Faculty of Science, Cairo University Using Max-SAT", International Conference New Horizons in Basic and Applied Science (ICNHBAS), Hurghada, Egypt, 23 Sep. 2013.