Questions tagged [bounds]

For questions about obtaining upper or lower bounds for certain values, usually for an optimization objective.

29 questions
Filter by
Sorted by
Tagged with
79 views

Understanding the condition of the bounded variable algorithm in the linear programming

Following is the section 7.3 of Operation Research An Introduction by Hamdy A. Taha, Define the upper-bounded LP model as, $$\max z=\{CX|(A,I)X=b,0\leq X\leq U\}$$ The bounded algorithm uses only the ...
• 121
74 views

Find projection onto implicitly defined set

I think this is a problem a lot of people have in minimization but I couldn't find algorithmic approaches to it. Given a closed domain $D\subset R^n$ over which a function $f$ is supposed to be ...
1 vote
51 views

Get objective upper bound in a callback (cplex)

I wonder if there is a way to retrieve the global objective upper bound in a callback in Cplex (in cpp)? I tried several context/IloCplex/IloModel... methods but nothing worked.
46 views

Deriving a lower bound for a two-stage stochastic problem

Assume an inventory stochastic optimization problem in the following form: $$\min\limits_{x\in X} c^\top x + \mathbb{E}_{\mathbb{\xi}}[\mathcal{Q}(x, \xi)]$$ Demand is the uncertain parameter, and is ...
• 2,086
333 views

Upper bound on length of solution of linear program

Consider the linear program: $$\text{maximize} ~~ c\cdot x \\ \text{subject to} ~~ A\cdot x\leq b, ~~x\geq 0.$$ Suppose $A$ is an $m\times n$ matrix, $b$ an $m\times 1$ vector and $c$ an $n\times 1$ ...
145 views

Reduced cost fixing for binary programs

Consider the binary program $$\min_{ x \in \{0,1\}^N } \left\{ c^T x \mid Ax \leq b \right\}$$ where $A$ and $b$ are real matrices with appropriate dimensions. I am interested in solving large binary ...
258 views

Binary decision variable to indicate whether a continous decision variable is equal to its upper bound

Given a continuous nonnegative decision variable $x\in [0,T]$ bounded by $T$, how can we enforce a relation between $x$ and another binary decision variable $y$ such that when $x$ is equal to its ...
• 147
239 views

Improving best bound within B&B process

Here is an extract from the BnB solution process of my problem. The solver determines a value of 2627.452494 as being the best bound of the optimal solution. The value for the best bound remains the ...
• 2,180
188 views

What is the role of computation lower bounds for exact methods, heuristics, and hybrid of exact and heuristics?

I'm struggling with this question for weeks: What is the main difference between the role of computation lower bounds for exact methods, heuristics, and hybrid of exact and heuristics? I try to answer ...
• 21
127 views

926 views

Which is better to minimize w.r.t a lower bound or an upper bound of an objective function?

Suppose there is a optimization problem that aims at minimizing an objective function $X$ but we can't develop a mathematical model for minimizing $X$. However, there are two objective functions $Y$ ...
• 489
1k views

How do Quadratic Programming solvers handle variables without bounds?

Solvers for non-convex QPs generally do the McCormick relaxation of the term $xy=z$ and then do spatial branch and bound. This requires that $x$ and $y$ have given bounds, how do they handle the case ...
• 3,635
79 views

Heuristic to compute upper bound for the simple assembly line balancing problem type 2?

I am currently working on SALBP-2 described as: Given the number m of assembly stations, minimize the cicle time c. I have done a bit of research and found the following approach to solve it: The ...
• 121
757 views

How to use tight upper and lower bounds to get to the optimal value via branch and bound?

I have algorithms that get me a tight upper (UB) and lower (LB) bound to a maximization binary integer program (a routing problem). My formulation is non-compact and requires the addition of sub-tour ...
193 views

Ways to improve lower bounds while solving MIPs

What are the ways to improve lower bounds while solving a minimization problem (MILP)?
• 21
241 views

How to exploit known solution in MILP

I have an MILP model to which I get an integer feasible solution as a result of a heuristic search. In this particular example, the initial solution turns out to be the optimal solution, which I prove ...
• 2,180
82 views

An upper-bound on the value of $S$ in $(s,S)$ policy

I recently have come across a problem which can be categorized as a stochastic optimization. The problem seems simple, but I haven't been able to solve it yet. It has a major impact on algorithm ...
468 views

Solving a variant of multiple knapsack problem/ generalized assignment problem

Consider $m$ knapsack and $n$ items. With each knapsack $j$ associated a capacity $c(j)$ and with each item $i$ associated a profit $p(i,j)$ (that depends on the knapsack, so it's not exactly the ...
• 943
1k views

Variable fixing based on a good feasible solution

Suppose you have a combinatorial optimization problem that is formulated as a mixed integer linear program (minimization). The problem size is denoted $n$ and the expected $n$ is around $100$. The ...
• 2,140
384 views

Proof of bound on optimal TSP tour length in rectangular region

Lemma 3 in Haimovich and Rinnooy Kan (1985) (Math of OR 10(4):527–542) says: If $X$ [the set of nodes] is contained in a rectangle with sides $a$ and $b$, then  T^*(X) \le \sqrt{2(n-1)ab} + 2(a+...
• 13.1k
2k views

How to compare two different formulations of a problem?

I somewhat know how to compare two MILP formulations of a problem that both use the same set of decision variables (as in the classical MTZ vs DFJ formulations of the TSP). I was wondering how two ...
• 2,140
1k views

Prove that these linear programming problems are bounded by $O(k^{1/2})$

Prove that these linear programming problems are bounded by $O(k^{1/2})$ Conjecturally the expanded partial sums of the Möbius transform of the Harmonic numbers have two out of three properties in ...
• 281
632 views

Tightness of an LP relaxation without using objective function

How can we measure the tightness of a linear programming relaxation for a mixed integer linear program without using the objective value? I would like to get a measure in terms of the feasible set and ...