TDA206 - Discrete Optimisation

Lecture notes - Lecture 3

1 About these notes

These notes were not written in class as I was away on vacation during this lecture, therefore it is instead based on last year's lecture notes for the second week. These notes will mainly be paraphrases of those notes. That's why there might be some overlap between these notes and last lecture's notes.

2 Linear Programming (cont.)

Linear programming is a special case of convex optimization that was one of the first optimization problems to be carefully studied and solved as it is tightly bound to linear algebra. Much of the advancements in other areas of optimization theory were inspired by Linear programming. In the same way that affine functions and half-spaces are the building blocks of convex functions and convex sets, linear programming is the foundation of all convex optimization problems.

Linear programming is interesting in this course because it is used heavily in the theory of discrete optimization. We can formulate many interesting problems as Integer Linear Programs (ILP) which are similar to LP's but have discrete variable space instead of continuous. However, before we dive into ILP's we will focus a bit more on LP's and possibly recap a bit from last lecture's notes.

2.1 Definition 1

An optimization problem is linear if:

  1. The variable domain is notes-3_954a4299b596365494d6fcaf76833c2301e7ca4b.png for som notes-3_d15a4e4ae61385fcd2221a2be30a7f59da7bd4ca.png.
  2. The cost function notes-3_b783764022e71d56bf828db824b3e93e17b7ef24.png and the constraint functions notes-3_4a79acd1b8c3ec3e60c8942a2d4088ffde128063.png and notes-3_4b4c5291a2755772a0c83d9014d9957a2c822c53.png are all affine functions.

It is popular to write an LP as


2.2 Matrix definition

This could easily be written using matrices, like this:


Now the optimization can be written as


2.3 Alternative forms of expressing LPs

Often we don't need all the matrices A, b, c, D and e to express an LP. There are two common forms to express an LP: standard form (or canonical form) and the augmented form.

Standard form:


Augmented form:


To turn a general form of LP into one of these forms, the following modifications are straightforward:

  • Minimization of notes-3_26a5780bade89b30b287281815bae136ca2107c6.png can be turned into maximization of notes-3_6b4bf84dcb22d11ad139a4d06793338499e38b57.png.
  • Lower bounds notes-3_6256be45450dd0ff50fc2cd375475f1fb93b3232.png can be turned into notes-3_b5febfefe5040999ca2a95976744e6e9699bfa14.png.
  • Equality constraints notes-3_374d784afb10be3b0159c3a44c7d3d8d8e251ae0.png can be turned into two inequality constraints notes-3_dcc29a1da9b43d76bcfcf6bf5e6fd6a910f9eb97.png and notes-3_5f05b3d7ba630f2c9c030dcd0dee1c04cd8ea4ab.png
  • Inequalities notes-3_bda9d4f4e7aa9ab3faac5ca948605e9642c2fcd1.png can be turned into equalities by introducing a new slack variable notes-3_f0decfeb90fd553d070d0a9ca10d6e839324c65f.png (hence the term "augmented" form), and replacing the constraint by notes-3_170bc14b939a8c2116b871c4ff3916677c1cecd9.png.
  • Unconstrained variables notes-3_ab74ecd8196b720353b9b7a6a36f3ff6b0afce73.png can be replaced by notes-3_7fd7a81bc6f18b595b317e504e50c35dff56e0b4.png.

2.4 Primal and dual LPs

Given a primal problem P


The dual problem D is defined as


2.5 Weak duality in LP

By minimizing the objective function for D (notes-3_0399f048a0f99889a07e0fe365df4d36404b3cc5.png) we can obtain an upper bound for the maximal solution of P.

Theorem (Weak duality in LP).
If there exists a feasible notes-3_df9707624e869ffae005be60251ba021972a7f02.png in P, and a feasible notes-3_6b223d2f7712fe6f24a55cf6953eaadde7e7d1b6.png in D, then notes-3_0c877d7831b84e7e670f144dd0d401f53474aacc.png.

Proof. If we left-multiply the constraint in P (notes-3_1e67d656aa323260f2b5d1a66f385ec93c3df648.png) with a non-negative vector notes-3_1f7fba0941f7561c46153b673780dd0ad1b4f955.png we will get the inequality notes-3_75283f4bfc47307a8755d98ed5be8ca5a48a37dd.png. Doing the same thing for the constraint in D with another non-negative vector notes-3_d51cd9d75bf91c1436663993349b5130ad5861e1.png gives us notes-3_a772ced9cb2a652becff8a3cbbdfd25ad943fbf0.png and transposing that leaves us with notes-3_6606d7777f9d36ad9a835fba7b4d5121b7ca8339.png Assuming that the feasible regions of P and D are note empty we can pick a notes-3_9c6d769bff6769c31779a841536351d2ec247901.png and an notes-3_6486daf8b9c9d200bf37df8595b088213206b4db.png to obtain the inequality notes-3_90cbeb193a4a02d5badbe520218a006516f0ca35.png. notes-3_7c7e311df2347862b48a120e2934049b09eb314d.png

The difference between two objectives is called the duality gap. There is for linear programs an even stronger theorem which we are not going to prove.

2.6 Strong duality of LP

Theorem (Strong duality of LP).
If P has a feasible optimal solution notes-3_010120ee7f873d7e91eed70a55d828b03a04d225.png, then D has an optimal feasible solution notes-3_3d1f2ce226d7f6666a320dd27e7ba08a808a90b1.png, and notes-3_2d032547b1c912cf272c40b1988b591d099ccac5.png. If P is unbounded, then D is infeasible. If D is unbounded, then P is infeasible. If either one is infeasible, the other is infeasible or unbounded.

In other words, the duality gap in LP is zero, except when both are infeasible, then it is infinite. Strong duality tells us that we can solve a maximization problem by solving its dual and vice versa. We can quickly decide if a problem in unbounded. Also, in LP, the dual of the dual is the primal.

2.7 Complementary slackness

There is another way to determine whether a solution to a promal is optimal, using a property called complementary slackness. Consider the first equality in the strong duality theorem, notes-3_39c7d1a991945ee0931d5429f8487daf8244bf16.png. This can be written as follows:


Since notes-3_dfbfec3aef69ec6dca9e703b7f00bae3c0e319f3.png is feasible, we know that notes-3_ca7d3a89c41d83ddb55cd3ef76319019aa5747e5.png and therefore notes-3_91f6dbdc3b2a2ff24702a5b3d1717ffd872d2fbd.png for all notes-3_0d663a1356e8b1cd88f5a469d39f98749c61328d.png. On the other hand, we know that notes-3_394f98b74387dbfff669229b458ff5827034f989.png for all notes-3_0d663a1356e8b1cd88f5a469d39f98749c61328d.png since notes-3_010120ee7f873d7e91eed70a55d828b03a04d225.png is also feasible. Since


and none of its terms can be positive, we have


because there can be no positive terms to cancel out any negative ones. This menas that in order to satisfy the equation above, for every notes-3_0d663a1356e8b1cd88f5a469d39f98749c61328d.png, at least one of notes-3_ea510dca96ed6112acbe59a8a38bcc6934a01c94.png and notes-3_836faf77b05dfe791c9e01b410b354b408bc8767.png must be 0. notes-3_d9d23a27535d27857a7e00eb1865109b8c47e3f5.png means that notes-3_e641b703bf2fe9f7c11201844e1b0c9697a2e11a.png is satisfied with equality.

2.8 Active constraints, constraint with slack and complementary slackness

Definition An inequality constraint notes-3_77e3b73f60cf3f55ee4de17399076b4b522bb58c.png is said to be binding or active if for some given notes-3_c7cec6eba855b37ac0506b8c3b62ebf8cc0a6bdf.png it is satisfied with equality, i.e notes-3_7b5ff8cb96bf83f70de996270221979ba2b0fd8a.png. It is said to have slack /if it is not binding.

An analogous argument can be made for notes-3_4e669d72a7160cfd739ea60550c9854a8b91c28f.png. This yields the following important result:

Theorem (Complementary slackness).
If optimal solutions notes-3_802c6127b1e2e300aa150a5c402cd4890ca281f4.png exist for the primal and dual LPs P and D, then the following holds:

  • If the i-th primal constraint notes-3_05a0c599342501ec260eeb06141c22d62488aa5e.png has slack, then the i-th dual variable notes-3_2c2cb8f522fd3f0f7e21c605a8afa8ddac5e6a6e.png is zero.
  • If the j-th dual constraint notes-3_e641b703bf2fe9f7c11201844e1b0c9697a2e11a.png has slack, then the j-th primal variable notes-3_e2459e6e25a7badf4fcbdc8bd99bc91aab90c362.png is zero.
  • If the i-th dual variable notes-3_2c2cb8f522fd3f0f7e21c605a8afa8ddac5e6a6e.png is positive, then the i-th primal constraint is binding.
  • If the j-th primal variable notes-3_e2459e6e25a7badf4fcbdc8bd99bc91aab90c362.png is positive, then the j-th dual constraint is binding.

The following might be useful for visualizing the correspondence of variables in the primal-dual relation:

2.8.1 Complementary slackness matrix


Author: Jacob Jonsson

Created: 2019-01-22 tis 19:54