# Questions tagged [discrete-optimization]

For questions about discrete optimization, which is a branch of optimization with discrete variables, opposed to continuous optimization in applied mathematics and computer science.

668 questions
Filter by
Sorted by
Tagged with
19 views

### Min cost max flow optimization problem

Let $I$ be the set of customers and let $J_i \subseteq J$ be the set of items from which customer $i \in I$ wants to buy only one, where $J$ are the items. Denote $w(i,j) \geq 0$ as the price customer ...
9 views

### Create MST by removing maximum weight edges in all cycles?

Let G be an undirected graph with distinct positive weights. Is it possible to create a minimum spanning tree by just finding all the cycles in G and removing the edges with the maximum weights in ...
11 views

### Maximize number of edges in a directed graph with vertex degrees bounded by one

Given a finite simple directed graph $G = (V, A)$, I am looking for a subgraph $G' = (V', A')$ of $G$ such that, for each vertex $v'$ of $V'$, the in-degree and the out-degree of $v'$ are at most one, ...
27 views

### split a number sequence into balanced groups [closed]

Given a sequence of real numbers, ${a_1,a_2,...,a_n}$, I want to split them into $\textbf{m}$ groups ($\textbf{m}$ is fixed and $m<n$). If the sum of each group is termed as $s_j$, how to setup the ...
44 views

22 views

### Solving linear programming problems with consecutive 1s in restriction matrix.

Let $A \in \{0, 1\}^{m \times n}$ be a matrix with consecutive ones in either the rows or columns. Then apparently solving an linear programming problem of the form ...
24 views

### Maximisation subject to an integer constraint

I am trying to solve an unconstrained maximisation problem. The objective function is quadratic in the (single) choice variable. Annoyingly, the choice variable must be an integer. Is there some ...
24 views

### strategy to find all spanning trees of a given weight

Given a graph and its weight function, is there a general strategy to compute all of its spanning trees of a given weight? Maybe we can write a program to sort out all the combinations of edges which ...
66 views

### Find minimum $n$ that satisfies $\frac{1}{a_1}+\frac{1}{a_2}+\cdots+\frac{1}{a_n}=\frac{12}{13}$

From the test: We have the following equation: \begin{equation} \frac{1}{a_1}+\frac{1}{a_2}+\cdots+\frac{1}{a_n}=\frac{12}{13} \end{equation} where $a_i$ are distinct natural numbers not equal to $13$....
60 views

### Find minimum number of figures needed , so that no additional figure can be added?

I have a $6\times 12$ rectangle, which I need to fill by the following figure: What is the minimum number of figures I need to use, so that no additional figure can be added? The figure can be ...
28 views

### How to solve $\mathop{max}_\limits{F} \ Tr(F^TAF)$, where $A=A^T$, $F \in \Bbb \{1, 0\}^{n \times c}$ is an indicator matrix?

For indicator matrix $F$, each row of $F$ has only one 1 and each column of $F$ has at least one 1. An example in python is as follow ...
20 views

### What is the definition of “augmenting path capacity”?

I am reading the text "Combinatorial Optimization: Networks and Matroids" by Eugene Lawler. Notation/Definitions: \begin{align} s, \quad &\text{source vertex} \\ t, \quad &\text{sink ...
16 views

### VRP with multiple locations for the same customer?

I am looking into the vehicle routing problem, and am looking for a specific case where a vehicle can visit a costumer at multiple locations, the vehicle only have to visit one of the locations. Does ...