Algorithms for Intelligent Decision Making

From MyInfoRepo
Jump to navigation Jump to search

Initial notes Algorithms and programming are used often in programming. However, these are very time-intensive to create and are subject to bugs. We can avoid these problems and still find answers to problems with Constraint Programming.

Personal (maybe subjective / TUDelft specific) notes: Notes:Algorithms_for_Intelligent_Decision_Making https://sofdem.github.io/gccat/gccat/sec5.html

First lecture

Constraint Programming

Combinatorial problem

Find solutions that satisfy contraints for domains. the objective function may be optimal.

[refactor, for AA] This Combinatorial Optimisation(CO) problem may be NP-hard. A CO consists of making decisions, yes/no questions, for example, whether to include a part of the domain in a solution. Linear programs are not part of CO, integer, traveling salesmen problem are. Solutions are limited by constraints, these will limit the objective function to a space of valid answers, with a possible optimum.


For solving the COs, we use solving technology, we model the constraint problems in a declarative language. The solving program has to solve a problem from these constraints, we want to do this intelligently. Three techniques are often used:

  • Search, find an answer by looking through solutions simply by calculating your way to the optimal answer.
  • Inference, find the answer by inference, one answer being excluded, may exclude others.
  • Relaxation, create an easier problem, which provides an answer (valid, but not necessarily correct).

The way this solving is done by a computer has many aspects. We have to formalize the way we input and handle data. By using these formal constraints, we do something akin to functional programming. We allow the program to work within all the constraints and with the data we have provided and expect a valid answer.

How to model and solve Combinatorial problems

How solvers work

Solvers use all three of the techniques mentioned before. Search, inference and relaxation. For different problems, there exist different solvers. There are languages that support modelling solvers, MatLab and MiniZinc are two examples.


Second lecture

Deeper dive into MiniZinc

Basic Features of MiniZinc (Modelling Concepts)

By using features of MiniZinc and backend models we can create models to solve many different problems.

(Decision) Variables are defined in models as part of a mzn program. These take values when satisfying the constraints of the modelled problem, bounded by its domain. Variable expressions take values depending on one or more variables. Parameters are given values by a problem description. All of these are typed. MiniZinc types: array, set, bool, int, float, enum, str. But not all can be used as variable types.

Variables and parameters in models are different from other programming languages. In models, the variables are more like we see in math, the value is not assigned to it. The value will only be fixed in a solution, if a solution exists.

Parametric models are models where some variables (parameters) are defined outside the model. A parametric model has uninstantiated parameters, an instance is a model along with the data provided into it.

Constraints are restrictions on values that variables can take. Its an expression that has a boolean-valued output which must be true.

The target (solution) of the model is the objective function, which is a numeric variable expression, which will be maximized or minimized. An objective states what is being asked for, whether it is a single (first) solution, all solutions, the extremum of an objective function, the amount of solution, the absence of a solution, or any other possibilities.

Art of Modeling

The models which you create on a solver could take different time for the same instance, they may need optimization or multiple models may be tested. These models will also scale differently on the same solver, for instances of growing size. Besides the model, the solver may also impact the solving duration on the same instance for the same model.

Problems to models

We need to define the characteristics of a good model, before we can create one. For a model to be a good (intermediate) solution for a constraint problem, it should adhere to some key principles. Of course it should correctly represent the problem. It should also be easy to understand and maintain. We also aim to find an efficiently solvable model with: short solving time, good solutions (within limited time) and a small search space. These terms, correct, easy, short are of course not the same in any context.

We have to think about how and what we model. The decision variables and their domains need to be picked carefully, to avoid unnecessary complexity. The same holds for the constraint predicates. Optionally, we can choose to have consistent constraints (must be satisfyable) and look at the variable and selection strategy for search.

Correctness should always come before efficiency.

xQPfAUs.png

We can look at the importance of choice of decision variables by simple example. A problem which can be solved in (at least) two ways is the SEND+MORE=MONEY puzzle. [todo: add example]

Problem to model guidelines: Reveal Problem Structure

  • Use few decision variables.
  • Give tight domains to the decision variables.
  • Avoid division and power constraints (div,mod,pow).
  • Avoid the disjunction of constraints (\/,<-,->,<->).
  • Express the problem concisely (use predicates).
  • Precompute solutions to a sub-problem into a table.
  • Use implied constraints.
  • Use different viewpoints.
  • Exploit symmetries.

There are exceptions to these guidelines. Models should be empirically tested with solvers and solving technology.

  • Using few decision variables is preferred over many.
  • Try to avoid var int; and tighten the domain by giving strict definitions
  • Avoice disjunctive constraints (slow):
constraint x = 0 \/ x = 9; is logically equivalent to constraint x in {0,9}; and, even better, var {0,9}: x;
  • Not may also introduce a disjunction.

YeCXqEa.png

Viewpoints