Constrained Optimization#
Constrained optimization is a cornerstone of many scientific and engineering disciplines, aiming to find the best solution to a problem within a set of specified boundaries or constraints. Common types of constrained optimization problems include linear, nonlinear, integer or mixed-integer programming, among others. Specifically, Linear Programming (LP) and (Mixed)Integer Linear Programming (MILP) are two widely used techniques in this domain. LP involves problems where both the objective function and the constraints are linear, and the decision variables can take any continuous values. On the other hand, (M)ILP is a more specialized form where some or all of the decision variables are required to be integers. Both LP and (M)ILP are particularly useful in modeling network problems, including many problems typically used in network biology, due to their ability to handle complex interrelationships and constraints inherent in such systems.
CORNETO offers an unified framwork for network learning from prior knowledge, where network inference problems are modelled through constrained optimization. Thanks to its modular backend implementation, different specialized mathematical optimization frameworks such as CVXPY or PICOS can be used to model and solve the optimization problems.
Here we will see how can we use CORNETO as a multi-backend constrained optimization framework for very basic optimization problems.
The Knapsack Problem#
The knapsack problem is an optimization problem in which we are given a set of items, each with a weight and a value. We are also given a knapsack with a limited capacity. The goal is to select a subset of the items to put in the knapsack so that the total value of the items is maximized, while the total weight does not exceed the capacity of the knapsack.
Figure 1: Knapsack problem.
The knapsack problem can be formulated as a constrained optimization problem with binary variables as follows:
We will see how to use CORNETO to easily model and solve to optimality this problem.
import corneto as cn
cn.info()
|
|
# CORNETO automatically selects one of the available mathematical programming backends.
# By default, CVXPY is preferred. The default backend can be accessed with:
cn.opt
<corneto.backend._cvxpy_backend.CvxpyBackend at 0x7f5b50152310>
obj1 = cn.opt.Variable("obj1", 1, vartype=cn.VarType.BINARY)
obj2 = cn.opt.Variable("obj2", 1, vartype=cn.VarType.BINARY)
obj3 = cn.opt.Variable("obj3", 1, vartype=cn.VarType.BINARY)
obj4 = cn.opt.Variable("obj4", 1, vartype=cn.VarType.BINARY)
obj5 = cn.opt.Variable("obj5", 1, vartype=cn.VarType.BINARY)
total_value = 4 * obj1 + 2 * obj2 + 10 * obj3 + 1 * obj4 + 2 * obj5
weight = 12 * obj1 + 1 * obj2 + 4 * obj3 + 1 * obj4 + 2 * obj5
total_value
Expression(AFFINE, NONNEGATIVE, (1,))
problem = cn.opt.Problem(
constraints=sum(weight) <= 15,
objectives=sum(total_value),
direction=cn.Direction.MAX,
)
problem
<corneto.backend._base.ProblemDef at 0x7f5b10301490>
problem.expr
{'obj5': obj5: Variable((1,), obj5, boolean=True),
'obj4': obj4: Variable((1,), obj4, boolean=True),
'obj3': obj3: Variable((1,), obj3, boolean=True),
'obj2': obj2: Variable((1,), obj2, boolean=True),
'obj1': obj1: Variable((1,), obj1, boolean=True)}
# Now we solve the problem using a specific solver. If solver is not provided
# one is automatically selected by the backend.
sol = problem.solve()
print(f"The max. value you can get with the backpack is ${total_value.value[0]}")
The max. value you can get with the backpack is $15.0
# Variables have the attribute 'value' to see their optimal value
# Before solving the problem, the 'value' attribute is None
obj1.value
array([-0.])