Questions tagged [integer-programming]

Integer programming regards optimization problems, where one seeks to find integer values for a set of unknowns, that optimizes the objective function. A common subset of this type of problems are integer linear programming problems, where all inequalities, equalities and the objective function are linear in the unknowns.

Filter by
Sorted by
Tagged with
8
votes
0answers
177 views

What is the probability of interpolating the Tutte polynomial of a planar graph from the values at the two hyperbolas?

The Tutte polynomial is a bivariate polynomial with positive integer coefficient which is a graph invariant and can be defined recursively. Evaluating it is $\#P$-complete even when restricted to (...
3
votes
1answer
195 views

Sufficient condition for solvability of linear diophantine system

I would like to know under what conditions does an integer solution exist to the under-determined linear system: Ax = b. (without constraints) Where A is m x n matrix with positive integers entries (...
5
votes
1answer
276 views

Maximize the determinant of Boolean combinations of positive definite matrices

I have the following optimization problem. $$\begin{array}{ll} \text{maximize} & \det \left(\sum^n_{i=1}z_i W_i \right)\\ \text{subject to} & \sum_{i=1}^n z_i = N\\ & z_i \in \{0,1\}\end{...
4
votes
2answers
1k views

Simplified knapsack problem

There is a problem that I can not solve. Given a set of items (each item has some integer weight) we have to fill bag with some number of copies of these items, with the only restriction that the ...