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