Documents
Presentation Slides
ICASSP 2015 Tutorial: Mixed-integer programming in signal processing and communications
![](https://sigport.org/sites/default/files/styles/home/public/Tx-beamforming2.png?itok=7TyDQOgH)
- Citation Author(s):
- Submitted by:
- Marius Pesavento
- Last updated:
- 19 February 2023 - 3:18pm
- Document Type:
- Presentation Slides
- Document Year:
- 2015
- Presenters:
- Marius Pesavento, Yong Cheng
- Categories:
- Keywords:
- Log in to post comments
There exists a large variety of applications, for instance in estimation and detection as well as network optimization, that involve both integer (discrete) decision making andthe optimization of continuous parameters. The integer decision making requirementsusually stem from the nature of the problem. In many applications, the physical quantitiesto be optimized are naturally undividable. Think for example of a cellular networkin which a subset of users needs to be selected for transmission. For a given user aconnection is either established or not. In source localization the number of sourcesto be estimated is an integer countable quantity that needs to be optimally selected.Or consider a multi-hop sensor network where the number of hops needs to be minimizedto achieve minimum latency services, to mention just a few examples. In otherapplications, integer decision making is imposed by technical standards. For example,in cellular communication networks built on the current 3GPP standard LTE-Advanceda large variety of cellular resources and parameters have to be optimized that conventionallyin academic research are often treated as continuous. One interesting exampleis the design of optimal beamformers in multiuser communication systems. It is wellestablished that optimal beamforming vectors can theoretically be computed with lowcomputational complexity, e.g., in closed form or from the solution of a convex optimizationproblem. However, due to signaling requirements, the LTE standard admitsbeamforming vectors that are selected from a codebook of predefined candidate beamformers.This involves integer decision making. Similarly, the data rate at which a userin the network is served depends on the modulation scheme (QPSK, 16-QAM, 64-QAM,etc.) as well as the block size of channel coding scheme. Thus rate adaptation in cellularsystems generally involves mixed-integer optimization. Another prominent example isMIMO detection and channel decoding. Here integer decision making is involved in thesense that the detected symbols are confined to the alphabet of constellation symbols orthe codewords defined in the communication standard.Due to the coupling of the decision variables, mixed-integer optimization problems areoften of combinatorial nature and exhibit a complexity that grows exponentially withthe problem dimension. The computationally complexity required to exhaustively testall combinations becomes prohibitive even if the problem size is medium. A popular andstraight forward approach that is often considered in practice is to model the integerdecision variables as continuous and then quantize the solution obtained from the continuousproblem. However, despite its simplicity, this approach, commonly referred toas continuous relaxation, leads in most of the cases to highly suboptimal solutions andoften infeasible points of the original mixed-integer problem.The branch-and-cut algorithm and its variants represent a standard framework forhandling mixed-integer programs. Branch-and-cut algorithms are particularly successfulin reducing the complexity of the combinatorial search if they are customized to theparticular problem under consideration. This requires the development of smart reformulationsof the original problem that exhibits tight continuous relaxations, i.e., problemreformulations which after relaxation of some of the integer variables the continuous domainprovide close bounds for the original problem. In recent years, a number of problemcustomization concepts have been developed to accomplish this task, such as the liftingtechnique in which additional variables are introduced to the problem, the concept ofcuts which consists in the introduction of additional redundant constraints that tightenthe continuous relaxations, as well as the big-M method which, e.g., allows to avoid(non-convex) bi-linear and tri-linear expressions in the continuous relaxations. While thebranch-and-cut method provides a universal framework for a large variety of applicationsand mixed-integer problems it generally suffers from slow and non-deterministic convergence.Provably optimal solutions can only be obtained for small problem dimensions.In particular applications it is however, despite the combinatorial problem structure,possible to overcome the limitations of the standard techniques and to transform theproblem into equivalent formulations with decoupled binary variables. One interestingexample is the codebook-based beamforming in cellular downlink networks for whicha particular form of uplink-downlink duality result can be established to convert theoriginally combinatorial problem into a much simpler non-combinatorial mixed-integerproblem. Recent works have shown increasing interest in developing efficient heuristicsfor computing approximate solutions in reasonable run-time. In many cases the underlyingproblem structure can be exploited to develop tight approximations that oftenlead to significant savings in the computational complexity and close-to-optimal feasiblesolutions.The objective of this tutorial is to introduce a general framework for addressing mixedintegerlinear and nonlinear programs and to provide the audience with insight andguidelines how to use existing tools for solving this difficult class of problems. We startthe tutorial revising well-known example applications widely known in signal processingand communication applications where mixed-integer decision making plays an importantrole. Based on these examples we will discuss important properties commonlyencountered in mixed-integer programming and introduce the underlying theoreticaltools and methods that can be applied to compute optimal solutions. In this context wewill revise the branch-and-cut algorithm and its variants. We will provide examples forstandard customization techniques that can be applied to a large variety of problems.We will outline basic steps that can be used in the theoretical analysis to prove thatparticular reformulations are preferable over others. After covering the basic concepts ofmixed-integer programming we will draw our attention to the software tools and solversthat are available for free, academic or commercial use. We will discuss their distinctfeatures and provide references and benchmark results regarding their respective performances.This shall enable the audience to find a quick starting point for their ownproblem treatment and code generation. The third part of the tutorial will then focuson advanced applications and recent research results. We will demonstrate with commonexamples how problem structures can be exploited to develop smart heuristics thatcan be used to obtain close-to-optimal solutions in just a fraction of time required forcomputing certified optimal solutions. We conclude the tutorial with some advanced exemplary applications in which particularly elegant algorithmic procedures have been developed that lead beyond branch-and-cut and that allow the design algorithms that reach proven global optimality with polynomial complexity.