James Bond uses CPLEX (OPL) to save his life.

Inspiration

Our inspiration was trying to use the concepts learns in few subjects from the Master in Innovation and Research in Informatics and the specialization of the Computer Networks and Distributed systems. We have learned so many things related in the field of Optimization and Machine Learning, and we thing that this project could have some future works in the same line.

What it does

The code builds a mixed integer linear programming model for a problem and implement it in OPL. The statement of the problem is the following:

A set S of n codes must be entered in a door lock to unlock the door. The codes are sequences of m digits that can be either 0s or 1s. All codes must be entered exactly once except for the first and last codes which have to be a sequence of m 0s, this code is also inside of the S set. The zeros sequence must be entered at the beginning and at the end of the code entering
The codes are entered using a display which has a sequence of m zeros as the first sequence and a cursor that is placed in the leftmost position. The system has three keys:

RIGHT is used to move the cursor on the display one step to the right.
FLIP is used to change the value of the position where the cursor is placed to the opposite value.
ENTER is used to enter the code in the system. It can only be used when the cursor is at the rightmost position. Whenever enter is used, the cursor moves to the leftmost position and the entered code remains in the display.

The set of codes that have to be entered is given as data. The set sizes (m columns n rows) is also given in the data as input.

The CPLEX implementation outputs the minimum number of FLIPs that have to be done while entering the code and the order of the entered codes. We had problems in the ordering output, it works for some of the datasets but fails to give a good order (respecting the constraints imposed in the model) in some cases.

How we built it

We built our project using the IDE by IBM and the optimization software package called IBM CPLEX OPL. The code was developed using the OPL C++ as the programming language.

Challenges we ran into

The main problem was formalizing the problem. Also we had problems with the code entering order. As mentioned before, there are some cases where theoutput doesent acomplish some of the constraints.

Accomplishments that we're proud of

To have a working function thet outputs the minimum number of flips needed to enter the codes. And the possibility to implement this use of case in a different scenarios, included as data files in the project.

What we learned

We learned how to implement a mathematical model (mathematical formalization of a model) in CPLEX. The model implemented has a lot of similarities compare to the travelling salesman problem.

What's next for HackUPC-2022

We are planning to implement some more features in the project, e.g. Greedy algorithm. This algorithm could be useful due to multiple minimum locals that have the problem.