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.K
<corneto.DeprecatedBackend at 0x7fe5a86240d0>
obj1 = cn.K.Variable("obj1", 1, vartype=cn.VarType.BINARY)
obj2 = cn.K.Variable("obj2", 1, vartype=cn.VarType.BINARY)
obj3 = cn.K.Variable("obj3", 1, vartype=cn.VarType.BINARY)
obj4 = cn.K.Variable("obj4", 1, vartype=cn.VarType.BINARY)
obj5 = cn.K.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.K.Problem(
constraints=sum(weight) <= 15,
objectives=sum(total_value),
direction=cn.Direction.MAX,
)
problem
<corneto.backend._base.ProblemDef at 0x7fe55e1bd850>
problem.expr
{'obj5': Variable((1,), obj5, boolean=True),
'obj4': Variable((1,), obj4, boolean=True),
'obj3': Variable((1,), obj3, boolean=True),
'obj2': Variable((1,), obj2, boolean=True),
'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.])
A more complex knapsack#
# A larger example from:
# https://developers.google.com/optimization/pack/knapsack
values = [
360,
83,
59,
130,
431,
67,
230,
52,
93,
125,
670,
892,
600,
38,
48,
147,
78,
256,
63,
17,
120,
164,
432,
35,
92,
110,
22,
42,
50,
323,
514,
28,
87,
73,
78,
15,
26,
78,
210,
36,
85,
189,
274,
43,
33,
10,
19,
389,
276,
312,
]
weights = [
7,
0,
30,
22,
80,
94,
11,
81,
70,
64,
59,
18,
0,
36,
3,
8,
15,
42,
9,
0,
42,
47,
52,
32,
26,
48,
55,
6,
29,
84,
2,
4,
18,
56,
7,
29,
93,
44,
71,
3,
86,
66,
31,
65,
0,
79,
20,
65,
52,
13,
]
# We use matrix notation form
obj = cn.K.Variable("obj", len(values), vartype=cn.VarType.BINARY)
total_value = values @ obj # matrix mul (1, values) x (objects, 1)
total_weight = weights @ obj
cn.K.Problem(
constraints=total_weight <= 850, objectives=total_value, direction=cn.Direction.MAX
).solve(verbosity=1)
===============================================================================
CVXPY
v1.5.3
===============================================================================
(CVXPY) Sep 18 07:38:10 AM: Your problem has 50 variables, 1 constraints, and 0 parameters.
(CVXPY) Sep 18 07:38:10 AM: It is compliant with the following grammars: DCP, DQCP
(CVXPY) Sep 18 07:38:10 AM: (If you need to solve this problem multiple times, but with different data, consider using parameters.)
(CVXPY) Sep 18 07:38:10 AM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.
(CVXPY) Sep 18 07:38:10 AM: Your problem is compiled with the CPP canonicalization backend.
-------------------------------------------------------------------------------
Compilation
-------------------------------------------------------------------------------
(CVXPY) Sep 18 07:38:10 AM: Compiling problem (target solver=SCIP).
(CVXPY) Sep 18 07:38:10 AM: Reduction chain: FlipObjective -> Dcp2Cone -> CvxAttr2Constr -> ConeMatrixStuffing -> SCIP
(CVXPY) Sep 18 07:38:10 AM: Applying reduction FlipObjective
(CVXPY) Sep 18 07:38:10 AM: Applying reduction Dcp2Cone
(CVXPY) Sep 18 07:38:10 AM: Applying reduction CvxAttr2Constr
(CVXPY) Sep 18 07:38:10 AM: Applying reduction ConeMatrixStuffing
(CVXPY) Sep 18 07:38:10 AM: Applying reduction SCIP
(CVXPY) Sep 18 07:38:10 AM: Finished problem compilation (took 6.652e-03 seconds).
-------------------------------------------------------------------------------
Numerical solver
-------------------------------------------------------------------------------
(CVXPY) Sep 18 07:38:10 AM: Invoking solver SCIP to obtain a solution.
feasible solution found by trivial heuristic after 0.0 seconds, objective value -6.000000e+02
presolving:
(round 1, fast) 4 del vars, 0 del conss, 0 add conss, 0 chg bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 2, exhaustive) 4 del vars, 0 del conss, 0 add conss, 0 chg bounds, 0 chg sides, 0 chg coeffs, 1 upgd conss, 0 impls, 0 clqs
(round 3, medium) 4 del vars, 1 del conss, 0 add conss, 46 chg bounds, 0 chg sides, 0 chg coeffs, 1 upgd conss, 0 impls, 0 clqs
presolving (4 rounds: 4 fast, 3 medium, 2 exhaustive):
50 deleted vars, 1 deleted constraints, 0 added constraints, 46 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients
0 implications, 0 cliques
transformed 1/3 original solutions to the transformed problem space
Presolving Time: 0.00
SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 0.00
Solving Nodes : 0
Primal Bound : -7.53400000000000e+03 (3 solutions)
Dual Bound : -7.53400000000000e+03
Gap : 0.00 %
-------------------------------------------------------------------------------
Summary
-------------------------------------------------------------------------------
(CVXPY) Sep 18 07:38:10 AM: Problem status: optimal
(CVXPY) Sep 18 07:38:10 AM: Optimal value: 7.534e+03
(CVXPY) Sep 18 07:38:10 AM: Compilation took 6.652e-03 seconds
(CVXPY) Sep 18 07:38:10 AM: Solver (including time spent in interface) took 3.526e-03 seconds
Problem(Maximize(Expression(AFFINE, NONNEGATIVE, ())), [Inequality(Expression(AFFINE, NONNEGATIVE, ()))])
total_value.value, total_weight.value
(7534.0, 850.0)