flopt: powerful optimization modeling tool
Tags: optimization, modeling, python, lp
Published: 2022-08-19 03:28:50

In this post, I introduce the basic usage of the powerful optimization modeling tool **flopt** and some specific examples of its features. (I am one of the developers of flopt)

https://github.com/flab-coder/flopt

An optimization modeling tool is a software that **supports the users in the task of expressing and realizing the problem they want to solve**.

In flopt.

- (Constrained) (non-)linear programming problems
- Black box optimization
- Satisfaction Maximization
- Problems with permutations as variables, such as traveling salesman problems
- quadratic programming problems
- Second-order programming problems
- etc.

In this paper, flopt: version 0.5.3 will be used for the explanation.

## Table of Contents

- [Install](#install)
- [Introduction](#introduction)
- [General usage](#general-usage)
  * [Available solvers](#available-solvers)
  * [Case Study](#case-study)
- [Linearization of problems](#linearization-of-problems)
- [Standard form transformations for linear programming problems](#standard-form-transformations-for-linear-programming-problems)
- [Summary](#summary)

## Install

We can install flopt by pip.

```sh
pip install flopt
```

Source codes can be available in https://github.com/flab-coder/flopt .

## Introduction

There are some optimization modeling tools, [Pulp](https://coin-or.github.io/pulp/) and[Scipy](https://scipy.org/) are known for linear programming (LP) modeling, [CVXOPT](https://cvxopt.org/) and [Pyomo](http://www.pyomo.org/) for quadratic programming (QP).

In general, a formulation can be expressed in other optimization problems (e.g., the Ising model can be reformulated as a QP or QUBO), so we have several choices of solvers that can be used, depending on the formulation type. However, the user must implement the modeling code for each solver to use, which can be very time-consuming.

*flopt* is developed as a Python library to solve such problems, aiming to be an intermediate modeling tool. **Users can only model problems in flopt and then convert to other modeling tools or use multiple solvers with ease**.

In flopt, currently, users can choose solvers from external libraries such as Scipy (linprog, milp, minimize), Optuna, Hyperopt, Pulp, CVXOPT, or internal implementation algorithms such as random sampling or 2-Opt.


## General usage

Let us model and optimize the following constrained nonlinear problem.
It consists of a nonlinear objective function consisting of two variables *a* and *b*, and constraints.

```
minimize  2*(3*a+b**2)+3
s.t.      a*b >= 2
          a+b >= 2
          0 <= a <= 1, a is integer
          1 <= b <= 2, b is continuous
```

```python
import flopt

# create variables
a = flopt.Variable("a", lowBound=0, upBound=1, cat="Continuous")
b = flopt.Variable("b", lowBound=1, upBound=2, cat="Continuous")

# create problem
prob = flopt.Problem(name="Test")
prob += 2*(3*a+b**2)+3  # set the objective function
prob += a*b >= 2        # add constraint
prob += a+b >= 2        # add constraint

# create solver
solver = flopt.Solver(algo="ScipySearch")

# run solver
prob.solve(solver, timelimit=10)

# get best solution
print("obj value　=", prob.getObjectiveValue())
print("a =", a.value())
print("b =", b.value())
```

Unlike Pulp and other modeling tools, flopt can flexibility express multiplication and power calculations between variables.
We add objective functions and constraints to the Problem object with `+=`. (You can also use the `.setObjective()` and `.addConstraint()` functions, respectively.) Whether it is an objective function or a constraint that is added is determined by whether the expression contains (==, <=, >=).

In the example above, the [ScipySearch](https://flopt.readthedocs.io/en/latest/solvers/nonLP.html) solver is used. Internally, the scipy.optimize.minimize solver is running, which is a solver that can handle constrained nonlinear problems.

### Available solvers

flopt can execute several external solvers (Scipy, Optuna, Hyperopt, Pulp, CVXOPT, etc.) and internally implemented algorithms (random sampling and 2-Opt, etc.) as Solvers. A list of supported solvers can be found [**here**](https://flopt.readthedocs.io/en/latest/solvers/index.html). In addition, we use Solver with `algo="auto"`,

```python
solver = flopt.Solver(algo="auto")
```

**the recommended solver is automatically selected**.　You can check which solver is selected by ``solver.select(prob).name``.
The solver selection depends on the problem and the time limit. Let's look at the following unconstrained problem case.

```python
a = flopt.Variable("a", 0, 1, cat="Continuous")
b = flopt.Variable("b", 1, 2, cat="Continuous")

prob = flopt.Problem(name="Test")
prob += 2*a + 3*b # set the objective function
```

When timelimit=1 is set,

```python
solver = flopt.Solver(algo="auto")
solver.setParams(timelimit=1)
solver.select(prob).name
>>> 'RandomSearch'
```

When timelimit=10,

```python
solver = flopt.Solver(algo="auto")
solver.setParams(timelimit=10)
solver.select(prob).name
>>> 'OptunaCmaEsSearch'
```

The selected solver has changed.


### Case Study

There are some case study in the document.

- [Sudoku](https://flopt.readthedocs.io/en/latest/case_studies/sudoku.html)
- [Number Partitioning](https://flopt.readthedocs.io/en/latest/case_studies/number_partitioning.html)

## Linearization of problems

I introduce the flopt's powerful feature that automatically transforms the objective function and constraints to linear if they have variable products. As far as I know, flopt is the only modeling tool that has such a function.

Let us take the following problem as an example to perform the linearization.

```
minimize  a * b * c + 2
s.t.      a * c == 2
          0 <= a <= 1, a is integer
          1 <= b <= 2, b is integer
          1 <= c <= 3, c is continuous
```

First, we modeling above problem in flopt.

```python
import flopt

a = flopt.Variable(name="a", lowBound=0, upBound=1, cat="Integer")
b = flopt.Variable(name="b", lowBound=1, upBound=2, cat="Integer")
c = flopt.Variable(name="c", lowBound=1, upBound=3, cat="Continuous")

prob = flopt.Problem()
prob += a * b + c + 2
prob += a * c == 2
```

Next, we execute `flopt.convert.linearize` function.

```python
flopt.convert.linearize(prob)
print(prob.show())
>>> Name: None
>>>   Type         : Problem
>>>   sense        : minimize
>>>   objective    : mul_0+2*mul_1+c+2
>>>   #constraints : 15
>>>   #variables   : 10 (Continuous 2, Integer 2, Binary 6)
>>> 
>>>   C 0, name None, mul_2-2 == 0
>>>   C 1, name for_bin_a_sum, bin_a_0+bin_a_1-1 == 0
>>>   C 2, name for_bin_a_eq, a-bin_a_1 == 0
>>>   C 3, name for_bin_b_sum, bin_b_0+bin_b_1-1 == 0
>>>   C 4, name for_bin_b_eq, b-bin_b_0-(2*bin_b_1) == 0
>>>   C 5, name for_mul_0_1, mul_0-bin_a_1 <= 0
>>>   C 6, name for_mul_0_2, mul_0-bin_b_0 <= 0
>>>   C 7, name for_mul_0_3, mul_0-(bin_a_1+bin_b_0-1) >= 0
>>>   C 8, name for_mul_1_1, mul_1-bin_a_1 <= 0
>>>   C 9, name for_mul_1_2, mul_1-bin_b_1 <= 0
>>>   C 10, name for_mul_1_3, mul_1-(bin_a_1+bin_b_1-1) >= 0
>>>   C 11, name for_mul_2_1, mul_2-bin_a_1 >= 0
>>>   C 12, name for_mul_2_2, mul_2-(3*bin_a_1) <= 0
>>>   C 13, name for_mul_2_3, mul_2-(c-(1-bin_a_1)) >= 0
>>>   C 14, name for_mul_2_4, mul_2-(c-(3*(1-bin_a_1))) <= 0
```

You will notice that a new variable has been added. Internally, the linearization is done by decomposing integer constraints into binary variables, adding the variable z=xy, which represents the product of the variables x and y, and so on. Then, you can specify LP solver and obtain the solution.

```python
solver = flopt.Solver("auto")
prob.solve(solver, msg=True)
```

## Standard form transformations for linear programming problems

In this section, we show the function to convert a linear programming problem to standard form.
Consider the following simple linear programming problem.

```
minimize  a + b + c + 2
s.t.      a + b == 2
          b - c <= 3
          0 <= a <= 1, a is integer
          1 <= b <= 2, b is continuous
          1 <= c <= 3, c is continuous
```

First, we model above problem in flopt.


```python
import flopt

# variables
a = flopt.Variable(name="a", lowBound=0, upBound=1, cat="Integer")
b = flopt.Variable(name="b", lowBound=1, upBound=2, cat="Continuous")
c = flopt.Variable(name="c", lowBound=1, upBound=3, cat="Continuous")

# problem
prob = flopt.Problem(name="LP")
prob += a + b + c + 2
prob += a + b == 2
prob += b - c <= 3
```

Next, we execute `LpStructure.fromFlopt` function to convert problem to LpStructure.

```python
from flopt.convert import LpStructure
lp = LpStructure.fromFlopt(prob)
print(lp.show())
```

Then the matrices G, A and vectors h, b are stored in the LpStructure object when the problem is expressed in the following form. We can access them as an attribute of LpStructure, for example, lp.A.

```
>>> LpStructure
>>> obj  c.T.dot(x) + C
>>> s.t. Gx <= h
>>>      Ax == b
>>>      lb <= x <= ub
```

Also,

```python
lp = lp.toAllEq()
```

will convert **all constraints to equality**. This is called equational standard form. In the example problem above, it would be

```python
print(lp.toAllEq().toFlopt().show())
>>> Name: None
>>>   Type         : Problem
>>>   sense        : minimize
>>>   objective    : a+b+c+2
>>>   #constraints : 2
>>>   #variables   : 4 (Continuous 3, Integer 1)
>>> 
>>>   C 0, name None, a+b-2.0 == 0
>>>   C 1, name None, -c+b+__s_0-3.0 == 0
```

You see that flopt have added a slack variable `__s` to convert to equality constraints.

Also use `.toAllNeq()` to **convert all constraints to inequality form**.

```python
print(lp.toAllNeq().toFlopt().show())
>>> Name: None
>>>   Type         : Problem
>>>   sense        : minimize
>>>   objective    : a+b+c+2
>>>   #constraints : 3
>>>   #variables   : 3 (Continuous 2, Integer 1)
>>> 
>>>   C 0, name None, -c+b-3.0 <= 0
>>>   C 1, name None, a+b-2.0 <= 0
>>>   C 2, name None, -a-b+2.0 <= 0
```

The constraint a+b-2.0 == 0 is converted to two inequality constraints a+b-2.0 <= 0 and -a-b+2.0 <= 0.

## Summary

In this paper, we introduced modeling tool flopt, and implementation examples of flopt, linearization of automatic variable products, and standard form conversion. flopt is available on Github, and we would be happy to receive your comments on the issue! Please contact us!

https://github.com/flab-coder/flopt

Thank you.