Huanfa Chen

Huanfa Chen

he/him

Associate Professor in Spatial Data Science, UCL CASA

Notes on multiple objective combinatorial optimisation problems

1 minute read

Published:

Updates 2024/01/31

This post records some notes on multi-objective combinatorial optimization (MOCO) problems.

Categorisation of strategies

Ehrgott and Gandibleux [7] categorised solution methods for addressing multi-objective optimization problems into three groups, based on the information provided by decision-makers. These groups are as follows:

  • Priori mode: In this strategy, decision-makers express their preferences at the beginning of the process. An example of this approach is goal programming, where decision-makers specify their objectives upfront.
  • Posteriori mode: The preferences of decision-makers are analyzed after obtaining all the non-dominated points. This mode focuses on evaluating and comparing different solutions based on the decision-makers’ preferences. Some algorithms of this approach aim to obtain the entire non-dominated frontier. These algorithms involve reformulating the multiple-objective problem as a collection of single-objective models. Two effective approaches are the two-phase method and $\epsilon$-constraint method.
  • Interactive mode: This strategy involves active involvement and collaboration between decision-makers and the decision-making process. Decision-makers play a significant role, providing feedback and refining their preferences during the computation steps.

Goal programming

Here, for each of the objectives a target value (goal) is specified by the decision maker. The overall aim is to minimize the deviation from the specified goals. This approach is sometimes considered a different field from multiobjective optimization.

A good example of goal programming can be found here.

Other references on GP

  • Ignizio JP (1976) Goal programming and extensions. Lexington Books,Lexington, KY

  • Lee SM (1972) Goal Programming for decision analysis. Auerbach,Philadelphia,PA

Efficient solution and supported solution

Lexicographic optimization

Max-ordering problem

As far as the other definitions of optimality in (MOCO) are concerned,we note that the max-ordering problem with sum objectives is INP -hard in general (see [22]), but can be reduced to a single objective problem in the case of bottleneck objectives.

For lexicographic optimization it is known that a lexicographically optimal solution is always efficient,and even a supported efficient solution

Comments

Introduction to Overleaf

3 minute read

Published:

Updates 2025/02/11 TL;DR: Using overleaf is much better than Microsoft Word (or MS Word) for academic writing that involves lots of formulas, and is very convenient for collaborative writing. UCL provides free and life-long Overleaf license.

Problems of MS Word in academic writing

  1. There are obvious differences between the desktop software of MS Word and the MS Word 365 on a browser, especially the formulas and figures.
  2. MS Word would crash if the file contains more than 100 pages, such as PhD dissertations.
  3. It is very hard to maintain lots of mathematical formulas in MS Word.
  4. It is time-consuming to change the template of MS Word. For example, IEEE journals requires two-column layout in submissions, which is a nightmare for MS Word.
  5. There is always a conflict if multiple people are simultaneously editing a Word doc via OneDrive, Dropbox, etc.
  6. etc …

Benefits of using Overleaf

  1. It is totally web-based and no installation is required.
  2. Many universities (e.g. UCL) provide free and life-long license of Overleaf, which allows many collaborators for one project.
  3. It is very easy to change the template. For example, if my paper submission to Journal A is rejected and I want to submit it to Journal B, it may take 30 minutes to change the template on Overleaf and resubmit. If I use MS Word, it might take hours or days.
  4. It has a rich text mode (see link), which resembles MS Word interface.
  5. It has functionality of “Track Changes” (see link) and “Add comments” (see link).
  6. It can be integrated with Github, Zotero, etc.
  7. There are lots of template of Overleaf. You can use it to write papers, prepare slides (using Beamer), prepare and update CVs.

Problems of using Overleaf

  1. The learning curve of Overleaf is quite steep. However, it is worthy for a four-year PhD and you don’t need to learn everything about Overleaf in one go (think about how you learn Python).
  2. As Overleaf is on a browser and depends on their server, sometimes the connection is unstable (but this is quite rare!).
  3. Some people don’t use Overleaf or resist using Overleaf. If your coauthor is one of them, you can either teach them to use Overleaf or download the Overleaf paper as MS Word document and send it to them. The latter way is really a pain, as you will maintain two versions of a paper in two different formats.

Tutorials of Overleaf

  1. UCL webpage and overleaf course at UCL: see link.
  2. 30-minute tutorial from Overleaf (link). Please note that you don’t need to learn everything about overleaf and Latex in one go. You can download an Overleaf template and write your own draft using template, and gradually learn Overleaf techniques when needed.
  3. Overleaf templates (link). Here you can find templates for UCL dissertation, Springer Nature LaTeX Template, etc. You can find more templates from Google/Github/CASA folks.
Read more