Programmation linéaire mixte: comment générer des contraintes?

Question

J'ai une fonction objectif tel que

(pour plus de simplicité, je les coefficients omis).

Je veux minimiser cette fonction à l'aide intlinprog avec les contraintes suivantes:

et

avec tous binaire x. Ces sommes donnent lieu à ces 4 inégalités:

Il est clair que la matrice de constaints est

Cela fonctionne bien si je crée cette matrice manuellement. Supposons maintenant que j'ai 6 ou 8 ou 10 variables au lieu de 4 dans ma fonction objectif et dans les contraintes (même schéma). Comment puis-je utiliser Matlab pour générer cette matrice de contraintes pour ces problèmes plus importants?

Answer 1

Je recommande d'écrire quelques autres cas. Il semble donc que vous voulez contrainte toutes les lignes checksums et toutes les colonnes checksums:

Pour N = 3, il y a 9 vars (je suppose une affaire carrée ici, vous n'avez pas fourni d'information complète):

x00 x01 x02 
x10 x11 x12 
x20 x21 x22 

maintenant, la matrice contrainte ressemble à:

x00 x01 x02 | x10 x11 x12 | x20 x21 x22 
--------------------------------------- 
1 1 1 
       1 1 1 
          1 1 1 
1    1    1 
    1    1    1 
     1    1    1 

C'est assez régulier. Il n'est pas temps de vérifier les fonctions de création de matrice de matlab.Malheureusement, je ne suis pas beaucoup plus d'un Matlab-utilisateur, mais:

la moitié inférieure de lignes se composent de:

• empilement horizontal de matrices d'identité-N chacun de taille N

la moitié supérieure des rangées se composent de:

• matrice diagonale par blocs de N-1 vecteur-ligne s chacune de taille N

la matrice finale est un empilement vertical des deux composants

Un exemple python-plein de matrice creuse (désolé, pas de Matlab ici; mais il devrait y avoir près d'un mapping 1: 1), pour être plus clair ressemblerait à ceci:

import numpy as np 
import scipy.sparse as sp 

N = 3 
component_a = sp.hstack([sp.eye(N) for i in range(N)]) 
row_full_1 = sp.csr_matrix(np.ones(N)) 
component_b = sp.block_diag([row_full_1 for i in range(N)]) # matlab: blkdiag? 
matrix = sp.vstack((component_b, component_a)) 

print(matrix.todense()) 

Sortie:

[[ 1. 1. 1. 0. 0. 0. 0. 0. 0.] 
[ 0. 0. 0. 1. 1. 1. 0. 0. 0.] 
[ 0. 0. 0. 0. 0. 0. 1. 1. 1.] 
[ 1. 0. 0. 1. 0. 0. 1. 0. 0.] 
[ 0. 1. 0. 0. 1. 0. 0. 1. 0.] 
[ 0. 0. 1. 0. 0. 1. 0. 0. 1.]] 

Remarque: selon N, vous devez penser à utiliser matrices denses ou éparses. Compte tenu de N, le rapport des non-zéros dans la matrice sera 1/N.