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 0x7fc5984306d0>
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 0x7fc54f173ed0>
problem.expr
{'obj5': Variable((1,), obj5, boolean=True),
'obj4': Variable((1,), obj4, boolean=True),
'obj1': Variable((1,), obj1, boolean=True),
'obj3': Variable((1,), obj3, boolean=True),
'obj2': Variable((1,), obj2, 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) Jan 20 09:58:28 AM: Your problem has 50 variables, 1 constraints, and 0 parameters.
(CVXPY) Jan 20 09:58:28 AM: It is compliant with the following grammars: DCP, DQCP
(CVXPY) Jan 20 09:58:28 AM: (If you need to solve this problem multiple times, but with different data, consider using parameters.)
(CVXPY) Jan 20 09:58:28 AM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.
(CVXPY) Jan 20 09:58:28 AM: Your problem is compiled with the CPP canonicalization backend.
-------------------------------------------------------------------------------
Compilation
-------------------------------------------------------------------------------
(CVXPY) Jan 20 09:58:28 AM: Compiling problem (target solver=SCIP).
(CVXPY) Jan 20 09:58:28 AM: Reduction chain: FlipObjective -> Dcp2Cone -> CvxAttr2Constr -> ConeMatrixStuffing -> SCIP
(CVXPY) Jan 20 09:58:28 AM: Applying reduction FlipObjective
(CVXPY) Jan 20 09:58:28 AM: Applying reduction Dcp2Cone
(CVXPY) Jan 20 09:58:28 AM: Applying reduction CvxAttr2Constr
(CVXPY) Jan 20 09:58:28 AM: Applying reduction ConeMatrixStuffing
(CVXPY) Jan 20 09:58:28 AM: Applying reduction SCIP
(CVXPY) Jan 20 09:58:28 AM: Finished problem compilation (took 8.054e-03 seconds).
-------------------------------------------------------------------------------
Numerical solver
-------------------------------------------------------------------------------
(CVXPY) Jan 20 09:58:28 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) Jan 20 09:58:28 AM: Problem status: optimal
(CVXPY) Jan 20 09:58:28 AM: Optimal value: 7.534e+03
(CVXPY) Jan 20 09:58:28 AM: Compilation took 8.054e-03 seconds
(CVXPY) Jan 20 09:58:28 AM: Solver (including time spent in interface) took 4.368e-03 seconds
Problem(Maximize(Expression(AFFINE, NONNEGATIVE, ())), [Inequality(Expression(AFFINE, NONNEGATIVE, ()))])
total_value.value, total_weight.value
(7534.0, 850.0)