flopt: powerful optimization modeling tool

Nariaki Tateiwa — Fri, 19 Aug 2022 03:28:50 +0000

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.

Install
Introduction
General usage
- Available solvers
- Case Study
Linearization of problems
Standard form transformations for linear programming problems
Summary

Install

We can install flopt by pip.

pip install flopt

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

Introduction

There are some optimization modeling tools, Pulp andScipy are known for linear programming (LP) modeling, CVXOPT and Pyomo 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

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 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. In addition, we use Solver with algo="auto",

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.

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,

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

When timelimit=10,

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.

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.

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.

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.

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.

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.

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,

lp = lp.toAllEq()

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

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.

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!