English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

It is important to design separation algorithms of low computationalcomplexity in mixed integer programming. We study the separation problems ofthe two continuous knapsack polyhedra with divisible capacities. The twopolyhedra are the convex hulls of the sets which consist of $ n $ nonnegativeinteger variables, one unbounded continuous, $ m $ bounded continuousvariables, and one linear constraint in either $ \geq $ or $ \leq $ form wherethe coefficients of integer variables are integer and divisible. Wolsey andYaman (Math Program 156: 1--20, 2016) have shown that the polyhedra can bedescribed by adding the two closely related families of partition inequalities.However, no combinatorial separation algorithm is known yet for the polyhedra.In this paper, for each polyhedron, we provide a combinatorial separationalgorithm with the complexity of $ \mathcal{O}(nm+m\log m ) $. In particular,we solve the separation problem for the continuous $ \geq $-knapsack polyhedronby presenting a polynomial-time separation algorithm for the family of $ \geq$-partition inequalities. For the continuous $ \leq $-knapsack polyhedron, wederive the complemented partition inequalities, which dominate the $ \leq$-partition inequalities. The continuous $ \leq $-knapsack polyhedron iscompletely described with the addition of the proposed inequalities. We againshow that the family of the proposed inequalities can be separated inpolynomial time.

Combinatorial separation algorithms for the continuous knapsack polyhedra with divisible capacities