Quick start

OptFrame Python is built upon OptFrame C++, a framework focused in solving challenging optimization problems, specially by means of metaheuristic techniques. This package abstracts away the C++ complexity and makes it easier for users to model efficient optimization techniques directly on Python.

After installing OptFrame Python (maybe using pip), user can start building a solution to the problem at hand.

Hint

The examples from OptFrame Python project follow the same idea from OptFrame C++. Understanding both can be interesting to gain more confidence on the framework. If feeling brave, take a look at OptFrame C++ on ReadTheDocs

First Example: 0-1 Knapsack Problem and Simulated Annealing

Let’s consider a classic problem: the 0-1 Knapsack Problem (KP).

By: Dake CC BY-SA 2.5

Given a set of items \(I\), the KP consists in selecting some items \(S \subseteq I\), such that the sum of weights \(w_i\) (for each selected item) do not exceed knapsack capacity \(Q\), and profit \(p_i\) of the selected items is maximized.

$$maximize\; \sum_{i \in S} p_i$$ $$\sum_{i \in S} w_i \leq Q$$ $$S \subseteq I$$

Solution and Evaluation Types

Users must first define a Representation, which is a data structure that represents an element in the Solution Space for the KP. A natural candidate here is a list of booleans, since we need to decide if we are going to carry each item or not. In Python, an interesting approach is to use native list or even advanced containers of numpy for greater performance.

User also needs to specify the data type for the Objective Space, in general a numeric type. The standard API of OptFrame Python adopts float64 or double type, and this API is called API1d.

Hint

There are more advanced APIs, other than API1d, which we will explore in the future.

We declare a XSolution class implemented as SolutionKP. Note that XSolution concept requires solution to be printable (through __str__ method) and fully copiable (through __deepcopy__ method):

class SolutionKP(object):
    def __init__(self):
        self.n   : int = 0        # number of items in solution
        self.bag : List[int] = [] # selected items in solution
    def __str__(self):
        return f"SolutionKP(n={self.n};bag={self.bag})"
    

Hint

For more advanced APIs, we will need a XESolution pair, containing the solution and evaluation value. In the future we will see more of this.

Problem Context

Users will need to store general problem information (such as profits and weights of items), so a ProblemContextKP can be introduced.

class ExampleKP(object):
    def __init__(self):
        self.engine = Engine()
        self.n : int = 0          # number of items
        self.w : List[float] = [] # item weights
        self.p : List[float] = [] # item profits
        self.Q : float = 0.0      # knapsack capacity

    def load(self, filename : str):
        with open(filename, 'r') as f:
            lines = f.readlines()
            self.n = int(lines[0])
            self.Q = int(lines[1])
            p_lines = lines[2].split()
            self.p = [int(i) for i in p_lines] 
            w_lines = lines[3].split()
            self.w = [int(i) for i in w_lines] 

    def __str__(self):
        return f"ExampleKP(n={self.n};Q={self.Q};w={self.w};p={self.p})"

Hint

ProblemContext is a user-defined class that can have any desired format. A ‘load’ function is just a suggestion, but not at all necessary. An OptFrame engine is also suggested to be stored here, since this problem will be available to all components.

Random Constructive

We need to have some initial solution for the search process, so we just proceed in a random manner. For simplicity, we allow infeasible solutions to be generated (as if capacity was infinite). Any function name is acceptable (such as mycallback_constructive), but pay attention to the function parameters (receives problem and returns solution):

# continuation of ExampleKP class...
    @staticmethod
    def generateSolution(problem: 'ExampleKP') -> SolutionKP:
        import random
        sol = SolutionKP()
        sol.n = problem.n
        sol.bag = [random.randint(0, 1) for _ in range(sol.n)]
        return sol

Hint

User can also define many advanced constructive techniques in a similar manner, such as greedy and greedy randomized approaches.

Evaluator

Now it’s time to define an evaluation (or objective) function. According to the goal of maximizing the profits, we iterate over selected items to accumulate profit and weights. As discussed in constructive section, we allow accumulated weight to surpass knapsack capacity, for infeasible configurations. To discourage that, we introduce negative penalization whenever capacity is exceeded (assuming weight -1000000):

# continuation of ExampleKP class...
    @staticmethod
    def maximize(pKP: 'ExampleKP', sol: SolutionKP) -> float:
        import numpy as np
        wsum = np.dot(sol.bag, pKP.w)
        if wsum > pKP.Q:
            return -1000.0*(wsum - pKP.Q)
        return np.dot(sol.bag, pKP.p)

# optional tests...
assert isinstance(SolutionKP, XSolution)     # composition tests 
assert isinstance(ExampleKP,  XProblem)      # composition tests 
assert isinstance(ExampleKP,  XConstructive) # composition tests    
assert isinstance(ExampleKP,  XMaximize)     # composition tests

We have defined maximize function, and later we will define its optimization direction.

Hint

User can also choose to minimize if dealing with a minimization problem. For multi-objective problems and Pareto optimization, user should visit Multi-Objective section.

Neighborhood Structure

In order to improve a given solution, several metaheuristics employ Local Search Optimization techniques based on the concept of Neighborhood Structure. Every neighborhood is related to a move operator, which is required (on FCore) to have an undo operation (capable of reverting the effects of the move).

We create a BitFlip move, that changes the true/false selection of a given item \(k\). In this case, the move structure (representation of the move) is just an int, that represents the flipped item.

Note the three class methods apply, canBeApplied and equals.

from optframe.components import Move

class MoveBitFlip(Move):
    def __init__(self, _k :int):
        self.k = _k
    def apply(self, problemCtx: ExampleKP, sol: SolutionKP) -> 'MoveBitFlip':
        sol.bag[self.k] = 1 - sol.bag[self.k]
        return MoveBitFlip(self.k)
    def canBeApplied(self, problemCtx: ExampleKP, sol: SolutionKP) -> bool:
        return True
    def eq(self, problemCtx: ExampleKP, m2: 'MoveBitFlip') -> bool:
        return self.k == m2.k
    

Now, it’s time to define a neighborhood generator for the move. OptFrame has three main types of neighborhoods: NS, NSSeq and NSEnum.

In this example, we will use NS, since it only requires the generation of random moves:

class NSBitFlip(object):
    @staticmethod
    def randomMove(pKP: ExampleKP, sol: SolutionKP) -> MoveBitFlip:
        import random
        return MoveBitFlip(random.randint(0, pKP.n - 1))

assert isinstance(NSBitFlip, XNS)     # composition tests

Hint

It is usually a good idea to start developing over the simplest neighborhood, which is NS. Most (non-deterministic) metaheuristics only requires a NS, as it only requires the generation of random moves. More advanced neighborhoods based on iterators, such as NSSeq and NSEnum are only required for advanced Local Search methods.

Time to Test!

At this point, you can already test many nice metaheuristics and solve your knapsack problem! We use the following code to load a problem instance (see Complete Example after):

# set random seed for system
# random.seed(10)

# loads problem from filesystem
pKP = ExampleKP()
pKP.load('knapsack-example.txt')
#pKP.n = 5
#pKP.w = [1, 2, 3, 7, 8]
#pKP.p = [1, 1, 1, 5, 5]
#pKP.Q = 10.0

Hint

It is useful to test every FCore structure independently, so as to develop unit testing for them.

Now we register evaluation and constructive into the engine. Then we test the constructive and evaluator:

# register model components (evaluation function, constructive, ...)
pKP.engine.setup(pKP)
ev_idx = 0
c_idx = 0
is_idx = 0
# is_idx = pKP.engine.create_initial_search(ev_idx, c_idx)

# register NS class
pKP.engine.add_ns_class(pKP, NSBitFlip) 
ns_idx = 0

# make engine silent (loglevel 0)
pKP.engine.experimental_set_parameter("ENGINE_LOG_LEVEL", "0")

# ======= play a little bit ========

fev = pKP.engine.get_evaluator(ev_idx)
pKP.engine.print_component(fev)

fc = pKP.engine.get_constructive(c_idx)
pKP.engine.print_component(fc)

solxx = pKP.engine.fconstructive_gensolution(fc)
print("solxx:", solxx)

z1 = pKP.engine.fevaluator_evaluate(fev, False, solxx)
print("evaluation:", z1)

# ====== end playing ======

Now we give an example with of the most well-known metaheuristics: the Simulated Annealing. It has few parameters, including: initial temperature T0, cooling factor alpha, and iterations per temperature iterT.

Hint

Note that we will use OptFrame Component Builder syntax, to automatically generate a native C++ Component based on a build string. For more details, see the (TODO) Component Builder list on OptFrame C++ ReadTheDocs (TODO).

# list the required parameters for OptFrame SA ComponentBuilder
print("engine will list builders for :BasicSA ")
nbuilders=pKP.engine.list_builders(":BasicSA")
print("nbuilders =", nbuilders)

# pack NS into a NS list
list_idx = pKP.engine.create_component_list(
    "[ OptFrame:NS 0 ]", "OptFrame:NS[]")

# make global search silent (loglevel 0)
pKP.engine.experimental_set_parameter("COMPONENT_LOG_LEVEL", "0")

# check components!
print("will invoke check module")
pKP.engine.check(100, 10, False)

# build Simulated Annealing with alpha=0.98 T0=99999 and IterMax=100
sa = BasicSimulatedAnnealing(pKP.engine, 0, 0, list_idx, 0.98, 100, 99999)
print("will invoke Simulated Annealing")
sout = sa.search(10.0)
print("Best solution: ",   sout.best_s)
print("Best evaluation: ", sout.best_e)

Complete Example

Warning

We present a complete example below. Note that some small differences may exist due to updates in tutorial, including language details. Feel free to check OptFrame C++ folder OptFrame/Examples for other examples on FCore and OptFrame Classic.

Example is divided in two files: KP-fcore-ex.py and mainKP-fcore-ex.py. The file mainKP-fcore-ex.py aggregates all components for execution.

Hint

This example could be made in a single file, to be even simpler. However, we recommend users to have a clear separation for the header declaration of FCore components (on KP-fcore-ex.py) from the main() entrypoint (on mainKP-fcore-ex.py), since unit testing is much simpler when these are decoupled.

mainKP-fcore-ex.py

File 'mainKP-fcore-ex.py' located in 'demo/02_QuickstartKP_SA/'

# OptFrame Python Demo 0-1 Knapsack Problem + Simulated Annealing

from typing import List

from optframe import *
from optframe.protocols import *


class SolutionKP(object):
    def __init__(self):
        self.n   : int = 0        # number of items in solution
        self.bag : List[int] = [] # selected items in solution
    def __str__(self):
        return f"SolutionKP(n={self.n};bag={self.bag})"
    


class ExampleKP(object):
    def __init__(self):
        self.engine = Engine()
        self.n : int = 0          # number of items
        self.w : List[float] = [] # item weights
        self.p : List[float] = [] # item profits
        self.Q : float = 0.0      # knapsack capacity

    def load(self, filename : str):
        with open(filename, 'r') as f:
            lines = f.readlines()
            self.n = int(lines[0])
            self.Q = int(lines[1])
            p_lines = lines[2].split()
            self.p = [int(i) for i in p_lines] 
            w_lines = lines[3].split()
            self.w = [int(i) for i in w_lines] 

    def __str__(self):
        return f"ExampleKP(n={self.n};Q={self.Q};w={self.w};p={self.p})"

# continuation of ExampleKP class...
    @staticmethod
    def generateSolution(problem: 'ExampleKP') -> SolutionKP:
        import random
        sol = SolutionKP()
        sol.n = problem.n
        sol.bag = [random.randint(0, 1) for _ in range(sol.n)]
        return sol

# continuation of ExampleKP class...
    @staticmethod
    def maximize(pKP: 'ExampleKP', sol: SolutionKP) -> float:
        import numpy as np
        wsum = np.dot(sol.bag, pKP.w)
        if wsum > pKP.Q:
            return -1000.0*(wsum - pKP.Q)
        return np.dot(sol.bag, pKP.p)

# optional tests...
assert isinstance(SolutionKP, XSolution)     # composition tests 
assert isinstance(ExampleKP,  XProblem)      # composition tests 
assert isinstance(ExampleKP,  XConstructive) # composition tests    
assert isinstance(ExampleKP,  XMaximize)     # composition tests

from optframe.components import Move

class MoveBitFlip(Move):
    def __init__(self, _k :int):
        self.k = _k
    def apply(self, problemCtx: ExampleKP, sol: SolutionKP) -> 'MoveBitFlip':
        sol.bag[self.k] = 1 - sol.bag[self.k]
        return MoveBitFlip(self.k)
    def canBeApplied(self, problemCtx: ExampleKP, sol: SolutionKP) -> bool:
        return True
    def eq(self, problemCtx: ExampleKP, m2: 'MoveBitFlip') -> bool:
        return self.k == m2.k
    
class NSBitFlip(object):
    @staticmethod
    def randomMove(pKP: ExampleKP, sol: SolutionKP) -> MoveBitFlip:
        import random
        return MoveBitFlip(random.randint(0, pKP.n - 1))

assert isinstance(NSBitFlip, XNS)     # composition tests

# ===========================
# begins main() python script
# ===========================

# get SimulatedAnnealing
from optframe.heuristics import *

# set random seed for system
# random.seed(10)

# loads problem from filesystem
pKP = ExampleKP()
pKP.load('knapsack-example.txt')
#pKP.n = 5
#pKP.w = [1, 2, 3, 7, 8]
#pKP.p = [1, 1, 1, 5, 5]
#pKP.Q = 10.0



# register model components (evaluation function, constructive, ...)
pKP.engine.setup(pKP)
ev_idx = 0
c_idx = 0
is_idx = 0
# is_idx = pKP.engine.create_initial_search(ev_idx, c_idx)

# register NS class
pKP.engine.add_ns_class(pKP, NSBitFlip) 
ns_idx = 0

# make engine silent (loglevel 0)
pKP.engine.experimental_set_parameter("ENGINE_LOG_LEVEL", "0")

# ======= play a little bit ========

fev = pKP.engine.get_evaluator(ev_idx)
pKP.engine.print_component(fev)

fc = pKP.engine.get_constructive(c_idx)
pKP.engine.print_component(fc)

solxx = pKP.engine.fconstructive_gensolution(fc)
print("solxx:", solxx)

z1 = pKP.engine.fevaluator_evaluate(fev, False, solxx)
print("evaluation:", z1)

# ====== end playing ======

# list the required parameters for OptFrame SA ComponentBuilder
print("engine will list builders for :BasicSA ")
nbuilders=pKP.engine.list_builders(":BasicSA")
print("nbuilders =", nbuilders)

# pack NS into a NS list
list_idx = pKP.engine.create_component_list(
    "[ OptFrame:NS 0 ]", "OptFrame:NS[]")

# make global search silent (loglevel 0)
pKP.engine.experimental_set_parameter("COMPONENT_LOG_LEVEL", "0")

# check components!
print("will invoke check module")
pKP.engine.check(100, 10, False)

# build Simulated Annealing with alpha=0.98 T0=99999 and IterMax=100
sa = BasicSimulatedAnnealing(pKP.engine, 0, 0, list_idx, 0.98, 100, 99999)
print("will invoke Simulated Annealing")
sout = sa.search(10.0)
print("Best solution: ",   sout.best_s)
print("Best evaluation: ", sout.best_e)

# =========================
# ends main() python script
# =========================

knapsack-example.txt

File 'knapsack-example.txt' located in 'demo/02_QuickstartKP_SA/'

5
10
1 1 1 5 5
1 2 3 7 8

To run it:

python3 mainKP-fcore-ex.py