# Questions tagged [integer-programming]

Questions on optimization constrained to integer variables.

963 questions
Filter by
Sorted by
Tagged with
4 views

### How to solve an Integer Programming problem using Gomory's Cutting Plane method, without using the Dual?

How to solve an Integer Programming problem using Gomory's Cutting Plane method, without using the Dual? This is a concept question. Im not opposed to using the dual in practice. Im just curious why ...
• 329
36 views

### Polynomial Curve Fit without floating point

big math dummy here hoping to get some advice. I'm working on a closed loop servo system that requires a curve fit on some feedback. The controller for this system is $16$-bit. With the help of excel ...
16 views

### Integer linear Programming - CVRP

I am dealing with a CVRP with multiple vehicles. I am struggling to come up with a formula for the constraint that each node with a non zero demand must be visited by one vehicle, once. Im trying to ...
62 views

1 vote
30 views

### Select a subset to Minimize a continuous unimodal function

I want to find an approximation algorithm for the following problem. $\qquad$ Find a $S\subseteq N$ such that $\rho(S) = \frac{\sum_{i\in S}\ V_i}{(1+\sum_{i\in S}\ V_i)(4+\sum_{i\in S}\ V_i)}$ is ...
• 11
1 vote
26 views

• 97
1 vote
103 views

### Primal Dual algorithm for set cover

I am having trouble understanding the approximation algorithm for set cover using primal dual. The entire approximation algorithm in a nutshell. A set cover problem is given Form the integer linear ...
• 169
1 vote
12 views

### Combining multiple binary variable combinations in sum statement

I have a question regarding how to formulate a constraint of an MILP. I have 2 platforms p and v(p) which are neighbours. Depending on the state of both of these platforms a specific value is chosen. ...
1 vote
31 views

### Consecutive ones property fails to agree partition condition

I have the matrix below: $A=\begin{pmatrix} 0&1&0&0&0 \\ 0&1&1&1&1\\ 1&0&1&1&1\\ 1&0&0&1&0\\ 1&0&0&0&0\\ \end{pmatrix}.$ ...
63 views

### Given that the positive integers $x>1$ and $y$ satisfy $2007x-21y=1923$. Find sum of digits of minimum value of $2x+3y$.

Given that the positive integers $x>1$ and $y$ satisfy $2007x-21y=1923$. Find sum of digits of minimum value of $2x+3y$. Here we have to solve for two variables using only one equation. How is ...
1 vote
55 views

### Edge Interdiction Clique Problem seperation of inequalities

I am currently working on the paper A branch-and-cut algrithm for the Edge Inderdiction Clique Problem. Basically, the problem asks to find a subset of at most $k$ edges to remove from a graph $G$, so ...
68 views

61 views

### Finding parameters of a linear programming problem

I have the following programming problem: $\min c_1x_1+c_2x_2$ such that $$x_2 \leq x_1$$$$x_1 \leq 2x_2+2$$$$x_1, x_2 \geq 0$$ How do I show that this problem is feasible and how do i find the ...
92 views

### Solving a linear system to infer damage values in an RPG

Background. In an RPG game, I've found that the weapon can destroy each object $i$ in a characteristic number of hits. When upgraded, the weapon can destroy each object $i$ in fewer hits. I am trying ...
• 15.8k
110 views

### Find an optimal allocation of groups in an array

Say we have an $n\times m$ array with $n$ and $m$ are odd, and a list of positive integers $(a_1,\dots, a_k)$. Each $a_i$ represents a number of elements which are to be allocated together in a row of ...
• 5,991
1 vote
72 views

• 352
1 vote
24 views

### Numerical non-convex integer optimization algorithms

Could you please suggest algorithms for solving non-convex integer optimization with constraints? The search space is very large, so branch and bound does not seem practical. A few methods I have ...
43 views

### Can clustering be implemented as Linear Programming?

When considering Gaussian mixture models (GMM) one efficient algorithm is the Expectation-Minimization (EM) algorithm. The E-step famously determines the degree of membership. For example, given a GMM ...
• 2,119
142 views

### Maximize $z=(3100y_1 -2850x_1)+(3250y_2-3050x_2)+(2950y_3-2900x_3)$

A company buys and sells grain in cash. The company has a warehouse with a capacity of $5000$ tons. On the first day of March , the stock balance is $1000$ tons and the account balance is $500$ ...
• 868
1 vote
41 views

### Hat manufacturing company and maximizing $z=8y_1+5y_2$

A hat manufacturing company produces two types of hats. The time required to produce the first type of hat is twice the time required to produce the second type. If all the hats are only of the second ...
• 868
1 vote
41 views

### How to maximize quadratic form with a integer variables or its relaxation

Let $A$ be a positive semidefinite matrix. Also, let $\forall i\in [1,n], x_i \in \{-1,1\}$. And finally, for some of indices $I\subset \{1,\ldots,n\}$, values of $x_i\in \{-1,1\}$ are known. ...
• 803
52 views

### Find the $6$-tuples $(x_1,x_2,x_3,x_4,x_5,x_6)$ to determine the least number of needed nurses

A simple examination in a hospital shows that the hospital needs the following number of nurses at different times of the day: \begin{array}{|c|} \hline \text{course} & \text{time} & \text{...
• 868
1 vote
Consider the problem: $$maximize: Z = x_1+2x_2$$ subject to: $$x_1+x_2 \leq 8$$ $$-x_1+2x_2 \leq 2$$ $$x_1-x_2 \leq 4$$ I know that this problem can be solved by using Branch-and-Bound ...