Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

0
votes
1answer
13 views

Solution of the LP relaxation - always round to the nearest integer?

If an optimal solution to the LP relaxation of an IP is not integer, can we always get a feasible IP solution by rounding it to the nearest integer? Or can we generalize this process by saying, if we ...
1
vote
2answers
101 views

Linear programming: expressing the fact that precisely $k$ variables are nonzero

Given some variables $x_1,\ldots,x_n$ is it possible to somehow express in a linear program the fact that precisely $k$ of them are non-zero? I suspect this would already be enough to simulate ...
2
votes
1answer
50 views

On/off variables in MILPs with infinite bounds

I have an LP defined by $$A x = b$$ $$0 \leq x \leq U$$ and would like to extend it to an MILP through introduction of binary on/off variables $z$ such that $$z_i = 0 \implies x_i = 0.$$ This ...
1
vote
0answers
15 views

Is there any general algorithm to solve such a 3D cutting problem?

Suppose a cuboid $\mathbb{A}$ has $L$,$M$ and $N$ as its length, width and height respectively, where $L\ge{M}\ge{N}>0$; Now we want to cut $\mathbb{A}$ into smaller cuboids with length $x$, width ...
1
vote
0answers
172 views

Global and local maxima in a weighted sum of logarithms of linear functionals?

Is is possible to describe, and locate efficiently, the maxima of the function below in the parameters $\mathbf{x}$ $$\sum_{i} p_i \log( N + \sum_j x_j[B_j +(A_j-B_j)\delta_{ij} + min(A_j,B_j) ]) ...
0
votes
0answers
14 views

minimising multivariate quadratic function over integer variables

I have a quadratic function $x_1^2+x_2^2-(u_1x_1+u_2x_2)^2$ which I need to minimise over integer $x_1$ and $x_2$; also, the coefficients $u_1,u_2<1$. In other word, assuming coefficients ...
-1
votes
1answer
17 views

Linear Programming constraint equivalent of conditional

I would like to use the following conditional in my linear program: if(A == 1) then B = C + 1 A = binary, B and C are continuous. In the else case, any relation ...
0
votes
1answer
332 views

general formula for an orthogonal projection of a point onto a line

Could someone confirm this or correct the mistakes because this seems somehow wrong although I double checked it. $(m_x,m_y)$ are coordinates of a point , $(p_x,p_y),(k_x,k_y)$ are coordinates of a ...
3
votes
0answers
140 views

Binary optimization

Let me first make my background clear. I am a PhD student with not much knowledge in optimization but I need to do some optimization as a part of my research work. My problem is as follows: There are ...
0
votes
0answers
13 views

Binary variable and constraint help

Was trying to solve a Integer programming model that goes like this. A bread company is deciding whether to set up factories that cater to outlets. Each factory has a certain set up cost tagged to ...
0
votes
0answers
8 views

optimization of formulas involving binomial coefficients

I encountered such a problem. We need to find the min value and max value of $f(x,y)$. $x$ and $y$ are integers $\in[0,n]\times[0,n]$ and $(x,y)\neq (0,0)$ or $(n,n)$. $$ ...
2
votes
2answers
335 views

Linear Programming: Breaking Variables Product

Given two sets of binary variables $x_{i...N} \in X$ and $y_{i...M} \in Y$ and another binary variable $\alpha$ how can I linearize the following constraint, i.e break the product of variables? ...
1
vote
0answers
16 views
4
votes
1answer
46 views

Is the optimal solution of a strictly convex function over $\mathbb{Z}^d$ a rounded version of its optimal solution over $\mathbb{R}^d$

Consider a strictly convex function $f: \mathbb{R}^d \rightarrow \mathbb{R}$. Let $x^* = \min_{\mathbb{R}^d} f(x)$ denote the (unique) minimum of this function over $\mathbb{R}^d$. Similarly, let ...
7
votes
1answer
64 views

Integer programming feasibility is NP-what

What is the complexity class of the general problem of integer programming feasibility? The sources I've looked at are, in my opinion, very confusing. Some say NP-hard, some say NP-complete. Some ...
0
votes
1answer
56 views

convertion into integer linear program

I am trying to model the Ising spin state problem into Integer linear program and find the optimal ground state using lp_solve. (This is just a miniature version of Ising state problem) $$ maximise: ...
1
vote
1answer
6 views

How to think about minors of the rectangular matrix in the context of a system of Diophantine linear equations

My question is related to my previous question How to prove existence of solutions to the system of Diophantine linear equations. In particular, to the theorem which I've used to prove some subset of ...
1
vote
1answer
54 views

Can you generate math problems that are solveable?

If you take Linear Programming, it problems are formulated like this: You know that Cabinet X costs 10 cents per unit, requires 6 square feet of floor space, and holds 8 cubic feet of files. ...
1
vote
2answers
39 views

Fog of War Influence Map

I'm in the process of making an RTS game and I've ran into a problem I could use help with. I want to create a fog of war system that reveals an area around a unit that belongs to you like how it's ...
1
vote
0answers
73 views

Traverse resultant 2D array after integer partition

I have used the solution of integer partitioning using dynamic programming explained in this post and in this article. Following is the resultant matrix when $N$ is equal to $6$: $$\begin{bmatrix} ...
0
votes
1answer
16 views

Replacing a max constraint in a binary program

For $x \in \{0,1\}$, I want to express $x = 1 \Leftrightarrow \exists k: y_k = 2$ where $y_k \in \{0,1,2\}$, i.e. $x \leq 0.5\max_k\{y_k\}$ using binary decision variables but I can't figure out how ...
2
votes
1answer
374 views

A variation of the Assignment Problem

In the following Wikipedia article about the Assignment Problem in the Example section, it says: Similar tricks can be played in order to allow more tasks than agents, tasks to which multiple ...
0
votes
1answer
22 views

Integer linear programming problem

There is an integer linear programming problem with this constraint: $$\left|X1 - X2\right|= 5\text{ or }10\text{ or }20$$ How it can be solved with adding auxiliary variable $y$? Main problem is ...
0
votes
1answer
40 views

Mixed Integer Linear Programming: Construction Rods

I have an interesting problem involving linear programming. The problem is the following, I have 4 different kinds of rods (rod sized found in the local market): 9m rod 11m rod 12m rod 15m rod ...
0
votes
0answers
29 views

Indicator Variable, Mixed Integer Linear Programming

Assume $x$ is a real variable, and $0\leq x \leq1$. Besides, $y$ is a binary random variable. I need a linear program that: if $y$ is $1$: $x>0$, if $y$ is $0$: $x=0$ I know the following ...
0
votes
1answer
29 views

Wrong ILP solution with LPSolve (simple example)

I added the following example into LPSolve and found a strange issue. I don't want S1 and S2 to overlap within certain margins. ...
0
votes
1answer
52 views

Solution techniques for optimization problems

I am very new to solving such optimization problems. Following is the problem, I need to know the various methods (preferably advanced machine learning techniques) that I can use to solve this. ...
2
votes
2answers
55 views

Integer Linear Programming

Without using a computer, I have to solve the following integer linear programming:$$\min \quad x_1+x_2+x_3$$ $$\operatorname{sub} ...
2
votes
1answer
74 views

What kind of algorithm might solve this type of optimization problem?

I am trading futures contracts in baskets at ratios that I compute by some method. Suppose there are $n$ contracts in a basket, and the ratio is given by $\mathbf{r}\in \mathbb{Z}^n$, so that the ...
0
votes
0answers
8 views

Number of satisfied constraints in unsolved ILP

I have ILP constraints as follow: $\forall l \in L_i \exists t \in T^l_i : \sum_j w_j(t) \geq r_i^l(t)$ For unsolved case, how can I compute the number satisfied $l$? Does it depend on the solver I ...
-1
votes
4answers
59 views

Can I find solutions to $a^4 + a^2 + a = b^2 + b$, $a,b \in \mathbb{Z}$ and $ 1 < a < b$?

I was wondering if anyone could point me in the correct direction for either finding a solution to my problem or proving that it does not exist. $$a^4 + a^2 + a = b^2 + b \;\text{ for }\; a,b \in ...
0
votes
0answers
25 views

A good enough solution for the 0-1 multiple knapsack problem

Can you please explain, or point to an easy explanation of a good enough solution to the 0-1 multiple knapsack problem? This is a single constraint problem so only one-dimensional weights are to be ...
0
votes
1answer
79 views

Show both relaxations of boolean LP give equal lower bounds

Given the boolean LP: $$\text{Minimize}\;\; c^Tx$$ $$\text{Subject to}\;\; Ax \leq b$$ $$\hspace{57mm} x_i(1-x_i)=0\;\; i=1,...,n$$ Show that the LP relaxation: $$\text{Minimize}\;\; c^Tx$$ ...
0
votes
0answers
26 views

How is D.Knuth MMIX instruction MXOR useful for finite field multiplication?

Knuths TAOCP, Fascicle 1, exercise 37 (page 26) - http://mmix.cs.hm.edu/doc/fasc1.pdf: Explain how to use MXOR for arithmetic in a field of 256 elements; each element of the field should be ...
1
vote
0answers
26 views

How do you calculate Up and Down Penalties on a Branch and Bound algorithm of a MILP?

My notes really don't explain this clearly at all, so I have no idea what to do. If I have the following MILP: In which I've been told to solve it using: (a) Rule 1 (choose the variable with the ...
0
votes
0answers
9 views

Help on Binary Integer Programming

I am about to do a paper about distributing subjects to students with the constraints on: number of subjects that the student need, number of students whom these subjects will be distributed to, and ...
2
votes
0answers
23 views

What decides the structure of the dual variables taken in designing min-max type combinatorial optimization algorithms?

There are a bunch of combinatorial optimization problems like min cost flows and min weight perfect matchings that invoke duality and complimentary slackness to improve the primal feasible solution. ...
0
votes
0answers
16 views

Linearization bounds on 0-1 quadratic problems

What are the best linearization methods for approximating the following constrained 0-1 Quadratic problem, where $Q \in \mathbb{R}^{n\times n}$ and $k$ is an integer $1\leq k \leq n$ $$ \max ...
0
votes
0answers
44 views

Solution of a linearly constrained quadratic programming problem

What is the solution of the following optimization problem: \begin{align} &\min{\mathbf{p}^\mathrm{T} \mathbf{B} \mathbf{p}}\\ &\text{subject to}: \mathbf{0}\leq{\mathbf{p}}\leq \mathbf{1}. ...
3
votes
3answers
210 views

How to divide natural number N into M nearly equal summands?

How to divide natural number N into M nearly equal summands? For example, to divide 20 by 13, in geometric representation, I should get How to generate the sequence above? What is the name of ...
1
vote
1answer
24 views

Job scheduling to minimise squared completion times using mixed 0-1 quadratic program

I have come across an Optimization question as follows: There are $n$ jobs that have to be processed on a machine. The machine can process only one job at a time. The time taken to process job ...
11
votes
0answers
235 views

Determining information in minimum trials (combinatorics problem)

A student has to pass a exam, with $k2^{k-1}$ questions to be answered by yes or no, on a subject he knows nothing about. The student is allowed to pass mock exams who have the same questions as the ...
2
votes
1answer
44 views

Description of a constraint for a mixed integer program.

Suppose we have 100 items that are labelled from the set $P = \{A, B, C, D, E\}$. My constraints are as follows: I want to choose exactly seven items. The choice should have at least one item of ...
0
votes
1answer
50 views

matlab MINLP optimization with ga

I have written a program for optimizing a set of generators. I have hourly price and cost data and need to figure out when a generator should run or just stay off. There are additional constraints but ...
0
votes
1answer
78 views

integer linear programing in matlab with the symbolic toolbox

I am writing a program to optimize a set of generators. I have hourly data and but dont want to necessarily optimize the whole time series. For a similar problem in the past I used the symbolic ...
0
votes
1answer
83 views

A binary min-max optimization problem

I encountered a very special optimization problem for a practical application. We have a variable $$\mathbf{s}=(s_1,s_2,s_3, s_4)^T$$, where $s_i$ can only take $1$ or $-1$, and we also have a ...
1
vote
2answers
51 views

Escaping from a point in linear programming

Is there a trick for explaining the following constraint as a set of linear (in)equalities? $$ \sum_{i=1}^n|x_i-a_i|>0, $$ where $a_i$'s are real constants.
0
votes
0answers
27 views

Solution existence on $ax + by = c$

I have to produce an program which resolve the following equation: $ax + by = c$ With the following condition: $a$, $b$ and $c$ are known positive integer. $x$ and $y$ are positive ...
0
votes
1answer
50 views

Which algorithms are commonly used to solve this kind of Binary Integer Programming problem?

I want to solve the problem of minimizing $$\mathbf{c}^T\mathbf{x}$$ subject to the condition that $$A\mathbf{x} = \mathbf{b}\text{,}$$ where $\mathbf{b},\mathbf{c}$ are given vectors in ...
1
vote
2answers
39 views

How to find smallest integer which is greater than N positive primes

I know this can't be computed exactly, but I just need a rough estimate. I know one can compute a rough estimate of the number of primes less than N using the famous formula: ...